Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem P via QA involves a hardware-aware circuit compilation which requires representing P as a graph GP and embedding it into the hardware connectivity graph GQ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU). Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of GP -- the logical variables of P -- to a chain of adjacent nodes in GQ by means of one of its minors, so that the arcs of GP are preserved as physical connections among qubits in GQ. The static topology of hardwired qubits can clearly lead to inefficient compilations because GQ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology GQ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise. We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map GP into a minor of GQ. Our findings, obtained through ME executed on classical, i. e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of GP, exhibiting smoother scaling of the largest embeddable GP as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.
Bifulco et al. (Wed,) studied this question.