Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a two-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with ``planted'' (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems but also when minor embedding is used to extend the connectivity of physical devices.
Quantum annealing is a quantum algorithm for computing solutions to combinatorial optimization problems. This study proposes a method for minor embedding optimization problems onto sparse quantum annealing hardware graphs called 4-clique network minor embedding. This method is in contrast to the standard minor embedding technique of using a path of linearly connected qubits in order to represent a logical variable state. The 4-clique minor embedding is possible on Pegasus graph connectivity, which is the native hardware graph for some of the current D-Wave quantum annealers. The Pegasus hardware graph contains many cliques of size 4, making it possible to form a graph composed entirely of paths of connected 4-cliques on which a problem can be minor-embedded. The 4-clique chains come at the cost of additional qubit usage on the hardware graph, but they allow for stronger coupling within each chain, thereby increasing chain integrity, reducing chain breaks, and allow for greater usage of the available energy scale for programming logical problem coefficients on current quantum annealers. The 4-clique minor embedding technique is compared with the standard linear path minor embedding with experiments on two D-Wave quantum annealing processors with Pegasus hardware graphs. We show proof-of-concept experiments where the 4-clique minor embeddings can use weak chain strengths while successfully carrying out the computation of minimizing random all-to-all spin glass problem instances. Published by the American Physical Society 2024
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.
Quantum Annealing (QA) is a quantum computing paradigm for solving combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. An essential step in QA is minor embedding, which maps the problem graph onto the sparse topology of the quantum processor and then adjusts the problem weights. The process of mapping the problem variables to the hardware is computationally expensive and scales poorly with increasing problem size and hardware complexity. Existing heuristics are often developed for specific problem graphs or hardware topologies and are difficult to generalize. To address this limitation, we explore the use of machine learning methods, which would allow a much greater degree of flexibility, in particular of Reinforcement Learning (RL). RL offers a promising alternative by treating minor embedding as a sequential decision-making problem, where an agent learns to construct minor embeddings by iteratively mapping the problem variables to the hardware qubits. We propose a RL-based approach to minor embedding using a Proximal Policy Optimization agent, testing its ability to embed both fully connected and randomly generated problem graphs on two hardware topologies, Chimera and Zephyr. The results show that our agent consistently produces valid minor embeddings even when they span over more than a thousand qubits, in particular on the more modern Zephyr topology. Our proposed approach is also able to scale to moderate problem sizes and adapts well to different graph structures, highlighting RL’s potential as a flexible and general-purpose framework for minor embedding in QA but also pointing to limitations that will need to be addressed, for example in reducing the number of qubits required.
The current generation of D-Wave quantum annealing processor is designed to minimize the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a {\em Chimera} graph
CM,N,L. In order to solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor-embedded into a Chimera graph. We define a combinatorial class of {\em native clique minors} in Chimera graphs with vertex images of uniform, near minimal size, and provide a polynomial-time algorithm that finds a maximum native clique minor in a given induced subgraph of a Chimera graph. These minors allow improvement over recent work and have immediate practical applications in the field of quantum annealing.
An important challenge in superconducting quantum computing is the need to physically couple many devices using quasi-two-dimensional fabrication processes. Recent advances in the design and fabrication of quantum annealing processors have enabled an increase in pairwise connectivity among thousands of qubits. One benefit of this is the ability to minor-embed optimization problems using fewer physical qubits for each logical spin. Here we demonstrate the benefit of this progress in the problem of minimizing the energy of three-dimensional spin glasses. Comparing the previous generation D-Wave 2000Q system to the new Advantage system, we observe improved scaling of solution time and improved consistency over multiple graph embeddings.