Abstract Quantum annealing solves combinatorial optimization problems by finding the energetic ground states of an embedded Hamiltonian. However, quantum annealing dynamics under the embedded Hamiltonian may violate the principles of adiabatic evolution and generate excitations that correspond to errors in the computed solution. Here we empirically benchmark the probability of chain breaks and identify sweet spots for solving a suite of embedded Hamiltonians. We further correlate the physical location of chain breaks in the quantum annealing hardware with the underlying embedding technique and use these localized rates in a tailored post-processing strategies. Our results demonstrate how to use characterization of the quantum annealing hardware to tune the embedded Hamiltonian and remove computational errors.
Abstract Quantum annealing solves combinatorial optimization problems by finding the energetic ground states of an embedded Hamiltonian. However, quantum annealing dynamics under the embedded Hamiltonian may violate the principles of adiabatic evolution and generate excitations that correspond to errors in the computed solution. Here we empirically benchmark the probability of chain breaks and identify sweet spots for solving a suite of embedded Hamiltonians. We further correlate the physical location of chain breaks in the quantum annealing hardware with the underlying embedding technique and use these localized rates in a tailored post-processing strategies. Our results demonstrate how to use characterization of the quantum annealing hardware to tune the embedded Hamiltonian and remove computational errors.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
Quantum annealing offers an approach to finding the optimal solutions for a variety of computational problems, where the quantum annealing controls influence the observed performance and error mechanisms by tuning the underlying quantum dynamics. However, the influence of the available controls is often poorly understood, and methods for evaluating the effects of these controls are necessary to tune quantum computational performance. Here we use portfolio optimization as a case study by which to benchmark quantum annealing controls and their relative effects on computational accuracy. We compare empirical results from the D-Wave 2000QTM quantum annealer to the computational ground truth for a variety of portfolio optimization instances. We evaluate both forward and reverse annealing methods and we identify control variations that yield optimal performance in terms of probability of success and probability of chain breaks.
One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.
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.
Recently, many researchers are investigating quantum annealing as a solver for real-world combinatorial optimization problems. However, due to the format of problems that quantum annealing solves and the structure of the physical annealer, these problems often require additional setup prior to solving. We study how these setup steps affect performance and provide insight into the interplay among them using the job-shop scheduling problem for our evaluation. We show that the empirical probability of success is highly sensitive to problem setup and that excess variables and large embeddings reduce performance. We then show that certain problem instances are unable to be solved without the use of additional post-processing methods. Finally, we investigate the effect of pausing during the anneal. Our results show that pausing within a certain time window can improve the probability of success, which is consistent with other work. However, we also show that the performance improvement due to pausing can be masked depending on properties of the embedding, and thus, special care must be taken for embedded problems.
Quantum annealing (QA) is a promising optimization technique used to find global optimal solution of a combinatorial optimization problem by leveraging quantum fluctuations. In QA, the problem being solved is mapped onto the quantum processing unit (QPU) composed of qubits through a procedure called minor-embedding. The qubits are connected by a network of couplers, which determine the strength of the interactions between the qubits. The strength of the couplers that connect qubits within a chain is often referred to as the chain strength. The appropriate balance of chain strength is equally imperative in enabling the qubits to interact with one another in a way that is strong enough to obtain the optimal solution, but not excessively strong so as not to bias the original problem terms. To this end, we address the problem of identifying the optimal chain strength through the utilization of Path Integral Monte Carlo (PIMC) quantum simulation algorithm. The results indicate that our judicious choice of chain strength parameter facilitates enhancements in quantum annealer performance and solution quality, thereby paving the way for QA to compete with, or potentially outperform, classical optimization algorithms.