Quantum computing offers a promising route for tackling hard optimization problems by encoding them as Ising models. However, sparse qubit connectivity requires the use of minor-embedding, mapping logical qubits onto chains of physical qubits, which necessitates stronger intra-chain coupling to maintain consistency. This elevated coupling strength forces a rescaling of the Hamiltonian due to hardware-imposed limits on the allowable ranges of coupling strengths, reducing the energy gaps between competing states, thus, degrading the solver's performance. Here, we introduce a theoretical model that quantifies this degradation. We show that as the connectivity degree increases, the effective temperature rises as a polynomial function, resulting in a success probability that decays exponentially. Our analysis further establishes worst-case bounds on the energy scale degradation based on the inverse conductance of chain subgraphs, revealing two most important drivers of chain strength, \textit{chain volume} and \textit{chain connectivity}. Our findings indicate that achieving quantum advantage is inherently challenging. Experiments on D-Wave quantum annealers validate these findings, highlighting the need for hardware with improved connectivity and optimized scale-aware embedding algorithms.
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 Annealers (QAs) are among the first commercially scaled quantum computing systems designed for large-scale optimization. Unlike digital systems that execute sequences of compiled instructions, QAs operate as analog single-instruction machines that directly evolve an Ising Hamiltonian toward low-energy solutions. To execute an application, the logical problem graph must first be mapped onto the hardware's sparse connectivity via embedding, where logical variables are represented by chains of connected physical qubits. As a result, embedding becomes the dominant system challenge in QAs, shaping whether and how workloads can execute on the machine. Despite its central role, embedding has largely been treated as a preprocessing step rather than a system bottleneck.
In this work, we present ChainForge, the first systems and architecture characterization of embedding in QA workloads. Using diverse workload families and graph topologies on modern QA hardware, we characterize how embedding impacts effective hardware capacity, routing overheads, runtime variability, and solution quality. Our results show that embedding inflates physical resource usage, long chains degrade annealing fidelity and scalability, and heuristic embedders may fail even when valid embeddings exist. We further show that embedding latency can become a runtime bottleneck for dynamic workloads requiring frequent remapping, while nominal qubit counts significantly overestimate the usable capacity of QAs for realistic applications. Overall, our findings establish embedding as the defining workload bottleneck and systems abstraction of QAs, providing architectural insights for future hardware topologies, runtime systems, and workload-aware annealing platforms.
Abstract A significant challenge in quantum annealing is to map a real-world problem onto a hardware graph of limited connectivity. When the problem graph is not a subgraph of the hardware graph, one might employ minor embedding in which each logical qubit is mapped to a tree of physical qubits. Pairwise interactions between physical qubits in the tree are set to be ferromagnetic with some coupling strength
F<0 F<0 . Here we address the theoretical question of what the best valueFshould be in order to achieve unbroken trees in the pre-quantum-processing. The sum of |F| for each logical qubit is defined as minor embedding energy, and the best valueFis obtained when the minor embedding energy is minimized. We also show that our new analytical lower bound on |F| is a tighter bound than that previously derived by Choi (Quantum Inf Process 7:193–209, 2008). In contrast to Choi’s work, our new method depends more delicately on minor embedding parameters, which leads to a higher computational cost.
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 provides a practical realization of adiabatic quantum computation and has emerged as a promising approach for solving large-scale combinatorial optimization problems. However, current devices remain constrained by sparse hardware connectivity, which requires embedding logical variables into chains of physical qubits. This embedding overhead limits scalability and reduces reliability as longer chains are more prone to noise-induced errors. In this work, we develop an embedding-aware baseline noise framework that connects chain-length growth to accumulated integrated-control-error variance, chain break probability (CBP), chain break fraction (CBF), and chain-strength scaling. We distinguish a moment-level uncorrelated ICE baseline, which yields a linear variance law, from a Gaussian closure that gives a closed-form erfc approximation for CBP. Experiments on the D-Wave Advantage2 Zephyr processor show that the calibrated baseline model captures the dominant growth trend of CBF with embedding size. However, the empirical critical chain-strength exponent ranges from
α=0.805 to
α=1.006 across chain-break tolerance thresholds, with 95% bootstrap confidence intervals consistently excluding the independent-noise prediction
α=0.5 ; a direct fit of a correlated-variance extension recovers
γ≈1.8 , consistent with the asymptotic relation
γ=2α . These results indicate that real-hardware variance accumulation deviates from the independent-noise reference and is consistent with a correlated component. The proposed framework offers quantitative guidance for embedding-aware chain-strength tuning and motivates more general noise models incorporating correlated and non-Gaussian hardware effects.
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