Abstract
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 G_P and embedding it into the hardware connectivity graph G_Q 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 G_P -- the logical variables of P -- to a chain of adjacent nodes in G_Q by means of one of its minors, so that the arcs of G_P are preserved as physical connections among qubits in G_Q. The static topology of hardwired qubits can clearly lead to inefficient compilations because G_Q cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology G_Q 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 G_P into a minor of G_Q. 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 G_P, exhibiting smoother scaling of the largest embeddable G_P as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.