⚛️ quantum physics

Ground-State Sampling Correspondence between Penalty-Based and Constrained Quantum Annealing

This paper demonstrates that penalty-based quantum annealing and constrained quantum annealing (CQA) yield equivalent ground-state sampling distributions for cardinality-constrained problems because virtual transitions to infeasible states in the penalty method generate an effective second-order interaction that matches the CQA driver's coupling within the feasible manifold.

Original authors: Shunta Ide, Shu Tanaka

Published 2026-10-20

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Shunta Ide, Shu Tanaka

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, some problems are like finding a single needle in a haystack, while others are like finding every single needle hidden in a field of identical haystacks. The latter task is far more difficult, yet it is often the one that matters most in fields ranging from designing new materials to optimizing financial portfolios. To tackle these complex puzzles, scientists use a technique called quantum annealing. Imagine a landscape filled with hills and valleys, where the deepest valley represents the perfect solution to a problem. A quantum computer acts like a mist that can flow over the hills, settling into the lowest points. However, when there are many valleys of the exact same depth, the mist does not always spread out evenly. It tends to favor some valleys over others, leaving the most desirable solutions underrepresented. This uneven distribution is a major hurdle for anyone trying to find all possible answers to a difficult problem.

Researchers at Keio University and Waseda University have recently investigated how to fix this unevenness, specifically when the problem involves a strict rule about how many items must be included in the solution. They compared two different ways of programming the quantum computer to respect this rule. The first method, known as the penalty approach, adds a heavy cost to any solution that breaks the rule, effectively pushing the computer away from bad answers. The second method, called constrained quantum annealing, builds the rule directly into the machine's movement, ensuring it never leaves the valid area in the first place. While these two methods work very differently under the hood, the researchers set out to see if they would eventually lead to the same result: a fair selection of all the best possible solutions.

The team focused on a classic puzzle called graph bipartitioning, which involves splitting a network of connected points into two equal groups while minimizing the connections between them. They simulated the behavior of the quantum computer on a large number of random networks, ranging from small systems with six points to larger ones with twelve. By running these simulations over very long periods, they could watch how the computer's probability of finding the best solutions evolved. They discovered that the penalty method, when tuned with a sufficiently high penalty cost, begins to behave remarkably like the constrained method. As the penalty becomes large and the simulation runs longer, the way the penalty-based computer selects its solutions converges with the way the constrained computer selects them. Both methods end up favoring the same specific solutions and ignoring the same others, rather than distributing their choices evenly.

This convergence is not a coincidence but the result of a deep physical mechanism. When the penalty is high, the penalty-based method is forced to stay close to the valid solutions. However, to move between these valid solutions, the computer must briefly visit invalid states that break the rule. The researchers found that these brief, virtual visits to invalid states create a secondary effect that mimics the movement rules of the constrained method. It is as if the penalty method, by trying to avoid breaking the rule, accidentally learns to move in the same way as the method that was designed to never break it. Through mathematical analysis, the team showed that the strength of this mimicry depends on the ratio between the penalty cost and the energy differences in the problem. When the penalty is large enough, the difference between the two methods shrinks rapidly, following a predictable pattern where the error drops as the penalty increases.

The study confirms that while both methods can produce similar biased outcomes, neither guarantees a perfectly fair distribution of all solutions. Even with the constrained method, which is designed to stay within the valid area, the computer still shows a preference for certain solutions over others. This suggests that the bias is an inherent feature of how quantum fluctuations select states, rather than just a flaw in how the rules are written. The findings offer a new perspective for engineers building these systems: rather than viewing the penalty method as a clumsy workaround, it can be seen as a way to engineer specific quantum movements that match more sophisticated approaches. While the simulations showed this agreement clearly for the systems tested, the researchers note that larger systems might introduce new complexities. Ultimately, the work provides a clear map of how two different quantum strategies can arrive at the same destination, offering a shared foundation for understanding how to better sample the vast landscape of optimal solutions.

Technical Summary: Ground-State Sampling Correspondence between Penalty-Based and Constrained Quantum Annealing

Problem Statement
Quantum annealing (QA) is a heuristic for finding the ground state of Ising models, applicable to many combinatorial optimization problems (COPs). While finding a single optimal solution is often sufficient, certain applications require sampling from the set of degenerate ground states. Ideally, this sampling should be uniform; however, QA typically exhibits "unfair sampling," where degenerate ground states are sampled with non-uniform probabilities. This bias arises from the residual driver Hamiltonian near the end of the annealing process, which acts as a perturbation within the degenerate ground-state manifold.

For COPs with cardinality constraints (fixing the number of up spins), two primary implementation strategies exist:

Penalty-Based QA: Uses a standard transverse-field driver and adds a penalty term to the problem Hamiltonian to discourage constraint violations.
Constrained Quantum Annealing (CQA): Uses a driver Hamiltonian (e.g., a fully connected XY driver) that commutes with the constraint operator, ensuring the system remains in the feasible subspace throughout the evolution.

While these methods differ in their driver structures and transition mechanisms, it has been unclear how these differences affect the resulting conditional ground-state distributions, particularly whether the penalty method can reproduce the sampling bias of CQA under specific conditions.

Methodology
The authors investigate this correspondence using the Graph Bipartitioning Problem (GBP) with a balance constraint as a representative case study. The study employs a combination of:

Closed-system numerical simulations: Solving the Schrödinger equation for random GBP instances (generated via the Erdős–Rényi model) with system sizes $N = 6, 8, 10, 12$ . The simulations compare penalty-based QA (with varying penalty coefficients $\mu$ ) against CQA (using an XY driver) over a range of annealing times ( $T$ ).
Degenerate Perturbation Theory: Deriving effective Hamiltonians for both methods near the end of the annealing process to analytically explain the observed sampling behaviors.
Metrics: The study evaluates ground-state probability, the uniformity of the conditional distribution (measured via Jensen–Shannon divergence from a uniform distribution), and the agreement between the two methods (measured via Jensen–Shannon divergence between their respective conditional distributions).

Key Contributions and Results

Sampling Bias in Both Methods:
- Both penalty-based QA and CQA exhibit non-uniform sampling of degenerate ground states.
- In penalty-based QA, increasing the penalty coefficient generally reduces the sampling bias (making the distribution more uniform) but does not eliminate it entirely for larger systems.
- In CQA, despite ensuring feasibility, the sampling is also non-uniform, with bias increasing with system size $N$ and annealing time $T$ .
Correspondence of Distributions:
- The study finds that for sufficiently large penalty coefficients and long annealing times, the conditional ground-state distribution of penalty-based QA converges to that of CQA.
- This agreement is quantified by the Jensen–Shannon (JS) divergence between the two distributions, which decreases as the penalty increases.
Perturbative Explanation:
- The authors demonstrate that this convergence is explained by the structure of the effective Hamiltonians.
- CQA: The XY driver acts directly within the feasible ground-state manifold at first order, generating spin-exchange interactions.
- Penalty-Based QA: The transverse-field driver does not directly couple feasible ground states (first-order term vanishes). However, at second order, virtual single-spin flips to infeasible states generate an effective interaction.
- The Correspondence: In the limit of large penalties ( $\mu$ ), the second-order effective interaction in penalty-based QA becomes proportional to the projected XY driver of CQA. Specifically, the effective interaction scales as $\Gamma^2_{QA} / (2\mu)$ , matching the form of the CQA driver projected onto the feasible manifold.
- Consequently, if the projected XY operator has a unique lowest eigenstate within the relevant symmetry sector, both methods select the same ground states, leading to similar sampling biases.
Scaling of Agreement:
- The numerical results show that the JS divergence between the two methods decreases approximately as the inverse square of the ratio $r = 4\mu / \Delta_{max}$ , where $\Delta_{max}$ is the maximum energy difference between the optimal feasible state and the nearest infeasible state reachable by a single spin flip.
- This $r^{-2}$ scaling is consistent with the perturbative analysis, where relative corrections to the effective operator are of order $r^{-1}$ , leading to a divergence of order $r^{-2}$ .

Significance and Claims
The paper claims to establish a theoretical and numerical correspondence between two distinct quantum annealing implementations for constrained problems. The primary significance lies in demonstrating that:

Different microscopic mechanisms (transverse field with penalties vs. constrained XY driver) can generate the same leading-order effective interaction within a degenerate manifold.
Penalty-based QA can effectively reproduce the sampling bias of CQA when the penalty is sufficiently large, provided the annealing time is long enough to reach the ground state.
This correspondence extends to other equal-weight constraints (fixed magnetization) under the same perturbative conditions.

The authors conclude that this finding provides a concrete example of how distinct constraint implementations can yield common state selection via quantum fluctuations. They suggest this perspective could inform the design of mixers and Hamiltonians for sampling objectives beyond simple energy minimization, though they note that extending these results to gate-based algorithms or finite-depth QAOA requires further investigation into pulse ordering and variational parameters. The paper does not claim that either method achieves uniform sampling, but rather that they share a common mechanism for biased sampling.

More like this