This study addresses the minor-embedding problem, which involves mapping the variables of an Ising model onto a quantum annealing processor. The primary motivation stems from the observed performance disparity of quantum annealers when solving problems suited to the processor's architecture versus those with non-hardware-native topologies. Our research has two main objectives: i) to analyze the impact of embedding quality on the performance of D-Wave Systems quantum annealers, and ii) to evaluate the quality of the embeddings generated by Minorminer, the standard minor-embedding technique in the quantum annealing literature, provided by D-Wave. Regarding the first objective, our experiments reveal a clear correlation between the average chain length of embeddings and the relative errors of the solutions sampled. This underscores the critical influence of embedding quality on quantum annealing performance. For the second objective, we evaluate Minorminer's embedding capabilities, the quality and robustness of its embeddings, and its execution-time performance on Erdös-Rényi graphs. We also compare its performance with Clique Embedding, another algorithm developed by D-Wave, which is deterministic and designed to embed fully connected Ising models into quantum annealing processors, serving as a worst-case scenario. The results demonstrate that there is significant room for improvement for Minorminer, suggesting that more effective embedding strategies could lead to meaningful gains in quantum annealing performance.
In this paper, we study the potential capability of quantum annealing in solving the phase unwrapping problem, an instance of hard computational problems. To solve the phase unwrapping problem using quantum annealing, we deploy the D-Wave Advantage machine which is currently the largest available quantum annealer. The structure of this machine, however, is not compatible with our problem graph structure. Consequently, the problem graph needs to be mapped into the target (Pegasus) graph, and this minor embedding significantly affects the quality of the results. Based on our experiment and also D-Wave's reports, the lower chain lengths can result in a better performance of quantum annealing. In this paper, we propose a new minor embedding algorithm that has the lowest possible chain length for minor embedding the graph of the phase unwrapping problem onto the Pegasus graph. The obtained results using this embedding strongly outperform the results of Auto-embedding provided by the D- Wave's minorminer tool both in the quality of the solution obtained and in the length of the chain.
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 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 (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.
Minor embedding is essential for mapping largescale combinatorial problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently accommodates complete bipartite graphs onto the hardware topology of quantum annealers. By leveraging the inherent topographical periodicity of the physical quantum adiabatic annealer processor, our method systematically reduces qubit chain lengths, resulting in enhanced stability, computational efficiency, and scalability of quantum annealing. We benchmark our embedding framework against Minorminer, the default heuristic embedding algorithm, for the Pegasus topology, demonstrating that our approach significantly improves embedding quality. Our empirical results show a 99.98% reduction in embedding time for a 120 x 120 complete bipartite graphs. Additionally, our method eliminates long qubit chains, which primarily cause decoherence and computational errors in quantum annealing. These findings advance the scalability of quantum embeddings, particularly for quantum generative models, anomaly detection, and large-scale optimization tasks. Our results establish a foundation for integrating efficient quantum-classical hybrid solutions, paving the way for practical applications in quantum-enhanced machine learning and optimization.
Quantum annealing is a quantum algorithm to solve combinatorial optimization problems. In the current quantum annealing devices, the dynamic range of the input Ising Hamiltonian, defined as the ratio of the largest to the smallest coefficient, significantly affects the quality of the output solution due to limited hardware precision. Several methods have been proposed to reduce the dynamic range by reducing large coefficients in the Ising Hamiltonian. However, existing studies do not take into account minor-embedding, which is an essential process in current quantum annealers. In this study, we revisit three existing coefficient-reduction methods under the constraints of minor-embedding. We evaluate to what extent these methods reduce the dynamic range of the minor-embedded Hamiltonian and improve the sample quality obtained from the D-Wave Advantage quantum annealer. The results show that, on the set of problems tested in this study, the interaction-extension method effectively improves the sample quality by reducing the dynamic range, while the bounded-coefficient integer encoding and the augmented Lagrangian method have only limited effects. Furthermore, we empirically show that reducing external field coefficients at the logical Hamiltonian level is not required in practice, since minor-embedding automatically has the role of reducing them. These findings suggest future directions for enhancing the sample quality of quantum annealers by suppressing hardware errors through preprocessing of the input problem.