We investigate the performance of penalty-based quantum annealing (PQA) and constrained quantum annealing (CQA) in solving the graph partitioning problem under various noise models, including depolarizing, bit-flip, and phase-flip noise. We found that even in the absence of noise, the relative superiority of PQA or CQA is highly problem-dependent. PQA generally demonstrates relatively stable success probabilities, while CQA's performance varies significantly across problem instances. Notably, CQA experiences leakage from the constraint-satisfying subspace under most noise models, with the exception of phase-flip noise, where no leakage occurs exactly. The dependence of success probability on noise strength reveals that PQA consistently outperforms CQA in the weak noise regime, whereas CQA achieves higher success probabilities under strong phase-flip noise. However, even in this case, the overall success probability remains low, suggesting that CQA is not yet practical for noisy quantum annealers without the development of error-corrected quantum annealing and autonomous error correction techniques to address leakage from the constraint-satisfying subspace. To confine the system within the constraint subspace in CQA, error correction methods and cat code encoding will likely be required, both of which can suppress bit-flip errors.
We investigate the performance of penalty-based quantum annealing (PQA) and constrained quantum annealing (CQA) in solving the graph partitioning problem under various noise models, including depolarizing, bit-flip, and phase-flip noise. We found that even in the absence of noise, the relative superiority of PQA or CQA is highly problem-dependent. PQA generally demonstrates relatively stable success probabilities, while CQA's performance varies significantly across problem instances. Notably, CQA experiences leakage from the constraint-satisfying subspace under most noise models, with the exception of phase-flip noise, where no leakage occurs exactly. The dependence of success probability on noise strength reveals that PQA consistently outperforms CQA in the weak noise regime, whereas CQA achieves higher success probabilities under strong phase-flip noise. However, even in this case, the overall success probability remains low, suggesting that CQA is not yet practical for noisy quantum annealers without the development of error-corrected quantum annealing and autonomous error correction techniques to address leakage from the constraint-satisfying subspace. To confine the system within the constraint subspace in CQA, error correction methods and cat code encoding will likely be required, both of which can suppress bit-flip errors.
Quantum annealing generally samples degenerate ground states with nonuniform probabilities. This unfair sampling depends on how the driver Hamiltonian couples these states near the end of annealing. For combinatorial optimization problems with a cardinality constraint, the penalty method and constrained quantum annealing (CQA) differ in these couplings. The transverse-field driver of the penalty method does not directly couple feasible ground states, whereas the fully connected XY driver of CQA couples pairs of them related by a single spin exchange. We investigate how this difference affects ground-state sampling, using closed-system simulations of random graph bipartitioning instances together with degenerate perturbation theory. For the instances studied, the conditional ground-state distribution of penalty-based quantum annealing approaches that of CQA at sufficiently large penalties and long annealing times. This convergence can be explained by the effective Hamiltonian of penalty-based quantum annealing, in which virtual single-spin flips to infeasible states generate a second-order interaction proportional to the CQA driver projected onto the feasible ground-state manifold, which is the leading term of the effective Hamiltonian of CQA. In the numerical simulations, the Jensen--Shannon divergence between the conditional ground-state distributions of penalty-based quantum annealing and CQA decreases approximately as the inverse square of the penalty-to-objective energy ratio, consistent with the perturbative analysis. This correspondence between the effective Hamiltonians extends to equal-weight fixed-magnetization constraints under the same perturbative conditions, providing a common mechanism for sampling bias in the two implementations.
Constrained quantum annealing (CQA) is a quantum annealing approach that is designed so that constraints are satisfied without penalty terms. There is an analogy between the model for the CQA of graph coloring and a set of disordered spin chains. In the model for the CQA of graph coloring, disorder corresponds to the fluctuation of effective local fields that increase in a CQA process. Numerical simulations of effective fields and entanglement demonstrate how localization appears in the CQA. Some notable features appear in the concurrence, which is a measure of entanglement, plotted as a function of the fluctuation of effective fields.
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 offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.
Quantum annealing (QA) is a promising approach for solving combinatorial optimization problems; however, it is known to exhibit unfair sampling, in which degenerate ground states are not sampled with equal probability even for sufficiently long annealing times. Fair sampling is important in applications such as solution diversity assessment and combinatorial counting, yet the mechanism of unfair sampling remains poorly understood, particularly in constrained combinatorial optimization problems. In this work, we investigate unfair sampling of QA in weighted graph bipartitioning problems (GBP), a representative constrained optimization problem. We study how the penalty coefficient in the penalty method affects sampling fairness. Through numerical simulations and experiments on the D-Wave Advantage2 system, we show that increasing the penalty coefficient reduces unfair sampling in a representative single instance, and that this qualitative behavior is also observed on actual hardware. A scaling analysis over randomly generated instances with up to 12 spins reveals that, while this trend does not hold universally, more than 70% of instances exhibit monotonically increasing sampling fairness as the penalty coefficient increases, even at the largest system size studied. These results show that increasing the penalty coefficient improves sampling fairness, though at the cost of ground-state probability under practical annealing conditions, and call for a deeper theoretical understanding of unfair sampling in constrained optimization problems.
One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.