Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.16265

Limitation of Stoquastic Quantum Annealing: A Structural Perspective

Vicky Choi

Published Sep 18, 2025• 0 citations
arXivHTMLPDF

Abstract

We analyze the behavior of stoquastic transverse-field quantum annealing (TFQA) on a structured class of Maximum Independent Set (MIS) instances, using the same decomposition framework developed in our companion work on the DIC-DAC-DOA algorithm (Beyond Stoquasticity). For these instances, we provide a structural explanation for the anti-crossing arising from the competition between the energies associated with a set of degenerate local minima (LM) and the global minimum (GM), and analytically derive the associated exponentially small gap. Our analysis proceeds in two steps. First, we reduce the dynamics to an effective two-block Hamiltonian $H_{core}$, constructed from the bare (decoupled) subsystems associated with the LM and GM. This reduction is justified analytically using the structural decomposition. Second, we reformulate the eigenvalue problem as a generalized eigenvalue problem in a non-orthogonal basis constructed from the bare eigenstates of the subsystems. This transformation enables a clean perturbative treatment of the anti-crossing structure, independent of the transverse field, unlike standard perturbation theory approach, which requires treating the transverse field as a small parameter. This paper serves as a supplementary companion to our main work on the DIC-DAC-DOA algorithm, where we demonstrate how appropriately designed non-stoquastic drivers can bypass this tunneling-induced bottleneck.

DOI
10.48550/arxiv.2509.16265

Related papers

Beyond Stoquasticity: Structural Steering and Interference in Quantum Optimization

Vicky Choi

We present a theoretical analysis of the DIC-DAC-DOA algorithm, a non-stoquastic quantum algorithm for solving the Maximum Independent Set (MIS) problem. The algorithm runs in polynomial time and achieves exponential speedup over both transverse-field quantum annealing (TFQA) and classical algorithms on a structured family of NP-hard MIS instances, under assumptions supported by analytical and numerical evidence. The core of this speedup lies in the ability of the evolving ground state to develop both positive and negative amplitudes, enabled by the non-stoquastic XX-driver. This sign structure permits quantum interference that produces negative amplitudes in the computational basis, allowing efficient evolution paths beyond the reach of stoquastic algorithms, whose ground states remain strictly non-negative. In our analysis, the efficiency of the algorithm is measured by the presence or absence of an anti-crossing, rather than by spectral gap estimation as in traditional approaches. The key idea is to infer it from the crossing behavior of bare energy levels of relevant subsystems associated with the degenerate local minima (LM) and the global minimum (GM). The cliques of the critical LM, responsible for the anti-crossing in TFQA, can be efficiently identified to form the XX-driver graph. The resulting speedup can be attributed to two mechanisms: in the first stage, energy-guided localization within the same-sign block steers the ground state smoothly into the GM-supporting region, while in the second stage, the opposite-sign blocks are invoked and sign-generating quantum interference drives the evolution along an opposite-sign path. Finally, we derive scalable reduced models that provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.

arXiv:2509.16263•Sep 18, 2025•0 citations

Exponential Quantum Speedup on Structured Hard Instances of Maximum Independent Set

Vicky Choi

Establishing quantum speedup for computationally hard problems of practical relevance, particularly combinatorial optimization problems, remains a central challenge in quantum computation. In this work, we identify a structurally defined family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm that exploits this structure. The algorithm runs in polynomial time and achieves an exponential speedup over both transverse-field quantum annealing and state-of-the-art classical solvers on these instances, under assumptions supported by analytical and numerical evidence. We identify the essential quantum mechanism enabling the speedup as the use of a non-stoquastic XX-driver to access a larger sign-structured admissible subspace beyond the stoquastic regime, which allows sign-generating quantum interference to create smooth evolution paths that bypass tunneling. This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist. In addition, our analysis produces scalable small-scale models, derived from our structural reduction, that capture the essential dynamics of the algorithm. These models provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.

quant-pharXiv:2601.17686•Jan 27, 2026•0 citations

Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing

Vicky Choi

One of the distinct features of quantum mechanics is that the probability amplitude can have both positive and negative signs, which has no classical counterpart as the classical probability must be positive. Consequently, one possible way to achieve quantum speedup is to explicitly harness this feature. Unlike a stoquastic Hamiltonian whose ground state has only positive amplitudes (with respect to the computational basis), a non-stoquastic Hamiltonian can be eventually stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. In this paper, we describe that, for some hard instances which are characterized by the presence of an anti-crossing (AC) in a transverse-field quantum annealing (QA) algorithm, how to design an appropriate XX-driver graph (without knowing the prior problem structure) with an appropriate XX-coupler strength such that the resulting non-stoquastic QA algorithm is proper-non-stoquastic with two bridged anti-crossings (a double-AC) where the spectral gap between the first and second level is large enough such that the system can be operated diabatically in polynomial time. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size, over the stoquastic QA algorithm, and possibly the same order of speedup over the state-of-the-art classical algorithms in optimization. This work is developed based on the novel characterizations of a modified and generalized parametrization definition of an anti-crossing in the context of quantum optimization annealing introduced in [4].

arXiv:2105.02110•May 5, 2021•4 citations

Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians

Hidetoshi Nishimori, Kabuki Takada

Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like XX and XXXXX with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.

arXiv:1609.03785•Frontiers in ICT•Feb 17, 2017•97 citations

Locally suppressed transverse-field protocol for diabatic quantum annealing

Louis Fry-Bouriaux, Daniel T. O'Connor, Natasha Feinstein +1 more

Diabatic quantum annealing (DQA) is an alternative algorithm to adiabatic quantum annealing that can be used to circumvent the exponential slowdown caused by small minima in the annealing energy spectrum. We present the locally suppressed transverse-field (LSTF) protocol, a heuristic method for making stoquastic optimization problems compatible with DQA. We show that, provided an optimization problem intrinsically has magnetic frustration due to inhomogeneous local fields, a target qubit in the problem can always be manipulated to create a double minimum in the energy gap between the ground and first excited states during the evolution of the algorithm. Such a double energy minimum can be exploited to induce diabatic transitions to the first excited state and back to the ground state. In addition to its relevance to classical and quantum algorithmic speedups, the LSTF protocol enables DQA proof-of-principle and physics experiments to be performed on existing hardware, provided independent controls exist for the transverse qubit magnetization fields. We discuss the implications on the coherence requirements of the quantum annealing hardware when using the LSTF protocol, considering specifically the cases of relaxation and dephasing. We show that the relaxation rate of a large system can be made to depend only on the target qubit, presenting opportunities for the characterization of the decohering environment in a quantum annealing processor.

arXiv:2105.11163•Physical Review A•Nov 22, 2021•7 citations

Eigenvalue-Invariant Transformation of Ising Problem for Anti-Crossing Mitigation in Quantum Annealing

Tôru Fujii, Koshi Komuro, Yosuke Okudaira +1 more

We have proposed the energy landscape transformation of Ising problems (ELTIP), which changes the combination of the state and eigenvalue without changing all the original eigenvalues [arXiv:2202.05927]. We study how the ELTIP affects the anti-crossing between two levels of the ground and first excited states during quantum annealing. We use a 5-spin maximum-weighted independent set for the problem to numerically investigate the anticrossing. For comparison, we introduce a non-stoquastic Hamiltonian that adds antiferromagnetic interaction to the normal transverse magnetic field. Annealing with the non-stoquastic Hamiltonian is effective for difficult problems. The non-stoquastic Hamiltonian mitigates the anti-crossing when only the energy gap between the ground state and the first excited state of the final state is small. When the ELTIP is used, the anti-crossing disappears. For the problems investigated in this paper, the ELTIP shortens the annealing time to guarantee adiabatic change more than the non-stoquastic Hamiltonian.

arXiv:2301.10427•Journal of the Physical Society of Japan•Mar 2, 2023•6 citations
We analyze the behavior of stoquastic transverse-field quantum annealing (TFQA) on a structured class of Maximum Independent Set (MIS) instances, using the same decomposition framework developed in our companion work on the DIC-DAC-DOA algorithm (Beyond Stoquasticity). For these instances, we provide a structural explanation for the anti-crossing arising from the competition between the energies associated with a set of degenerate local minima (LM) and the global minimum (GM), and analytically derive the associated exponentially small gap. Our analysis proceeds in two steps. First, we reduce the dynamics to an effective two-block Hamiltonian HcoreH_{core}Hcore​, constructed from the bare (decoupled) subsystems associated with the LM and GM. This reduction is justified analytically using the structural decomposition. Second, we reformulate the eigenvalue problem as a generalized eigenvalue problem in a non-orthogonal basis constructed from the bare eigenstates of the subsystems. This transformation enables a clean perturbative treatment of the anti-crossing structure, independent of the transverse field, unlike standard perturbation theory approach, which requires treating the transverse field as a small parameter. This paper serves as a supplementary companion to our main work on the DIC-DAC-DOA algorithm, where we demonstrate how appropriately designed non-stoquastic drivers can bypass this tunneling-induced bottleneck.
We present a theoretical analysis of the DIC-DAC-DOA algorithm, a non-stoquastic quantum algorithm for solving the Maximum Independent Set (MIS) problem. The algorithm runs in polynomial time and achieves exponential speedup over both transverse-field quantum annealing (TFQA) and classical algorithms on a structured family of NP-hard MIS instances, under assumptions supported by analytical and numerical evidence. The core of this speedup lies in the ability of the evolving ground state to develop both positive and negative amplitudes, enabled by the non-stoquastic XX-driver. This sign structure permits quantum interference that produces negative amplitudes in the computational basis, allowing efficient evolution paths beyond the reach of stoquastic algorithms, whose ground states remain strictly non-negative. In our analysis, the efficiency of the algorithm is measured by the presence or absence of an anti-crossing, rather than by spectral gap estimation as in traditional approaches. The key idea is to infer it from the crossing behavior of bare energy levels of relevant subsystems associated with the degenerate local minima (LM) and the global minimum (GM). The cliques of the critical LM, responsible for the anti-crossing in TFQA, can be efficiently identified to form the XX-driver graph. The resulting speedup can be attributed to two mechanisms: in the first stage, energy-guided localization within the same-sign block steers the ground state smoothly into the GM-supporting region, while in the second stage, the opposite-sign blocks are invoked and sign-generating quantum interference drives the evolution along an opposite-sign path. Finally, we derive scalable reduced models that provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.
Establishing quantum speedup for computationally hard problems of practical relevance, particularly combinatorial optimization problems, remains a central challenge in quantum computation. In this work, we identify a structurally defined family of classically hard maximum independent set (MIS) instances, and design and analyze a non-stoquastic adiabatic quantum optimization algorithm that exploits this structure. The algorithm runs in polynomial time and achieves an exponential speedup over both transverse-field quantum annealing and state-of-the-art classical solvers on these instances, under assumptions supported by analytical and numerical evidence. We identify the essential quantum mechanism enabling the speedup as the use of a non-stoquastic XX-driver to access a larger sign-structured admissible subspace beyond the stoquastic regime, which allows sign-generating quantum interference to create smooth evolution paths that bypass tunneling. This identifies a distinctive quantum mechanism underlying the speedup and explains why no efficient classical analogue is likely to exist. In addition, our analysis produces scalable small-scale models, derived from our structural reduction, that capture the essential dynamics of the algorithm. These models provide a concrete opportunity for verification of the quantum advantage mechanism on currently available universal quantum computers.
One of the distinct features of quantum mechanics is that the probability amplitude can have both positive and negative signs, which has no classical counterpart as the classical probability must be positive. Consequently, one possible way to achieve quantum speedup is to explicitly harness this feature. Unlike a stoquastic Hamiltonian whose ground state has only positive amplitudes (with respect to the computational basis), a non-stoquastic Hamiltonian can be eventually stoquastic or properly non-stoquastic when its ground state has both positive and negative amplitudes. In this paper, we describe that, for some hard instances which are characterized by the presence of an anti-crossing (AC) in a transverse-field quantum annealing (QA) algorithm, how to design an appropriate XX-driver graph (without knowing the prior problem structure) with an appropriate XX-coupler strength such that the resulting non-stoquastic QA algorithm is proper-non-stoquastic with two bridged anti-crossings (a double-AC) where the spectral gap between the first and second level is large enough such that the system can be operated diabatically in polynomial time. The speedup is exponential in the original AC-distance, which can be sub-exponential or exponential in the system size, over the stoquastic QA algorithm, and possibly the same order of speedup over the state-of-the-art classical algorithms in optimization. This work is developed based on the novel characterizations of a modified and generalized parametrization definition of an anti-crossing in the context of quantum optimization annealing introduced in [4].
Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like XX and XXXXX with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.
Diabatic quantum annealing (DQA) is an alternative algorithm to adiabatic quantum annealing that can be used to circumvent the exponential slowdown caused by small minima in the annealing energy spectrum. We present the locally suppressed transverse-field (LSTF) protocol, a heuristic method for making stoquastic optimization problems compatible with DQA. We show that, provided an optimization problem intrinsically has magnetic frustration due to inhomogeneous local fields, a target qubit in the problem can always be manipulated to create a double minimum in the energy gap between the ground and first excited states during the evolution of the algorithm. Such a double energy minimum can be exploited to induce diabatic transitions to the first excited state and back to the ground state. In addition to its relevance to classical and quantum algorithmic speedups, the LSTF protocol enables DQA proof-of-principle and physics experiments to be performed on existing hardware, provided independent controls exist for the transverse qubit magnetization fields. We discuss the implications on the coherence requirements of the quantum annealing hardware when using the LSTF protocol, considering specifically the cases of relaxation and dephasing. We show that the relaxation rate of a large system can be made to depend only on the target qubit, presenting opportunities for the characterization of the decohering environment in a quantum annealing processor.
We have proposed the energy landscape transformation of Ising problems (ELTIP), which changes the combination of the state and eigenvalue without changing all the original eigenvalues [arXiv:2202.05927]. We study how the ELTIP affects the anti-crossing between two levels of the ground and first excited states during quantum annealing. We use a 5-spin maximum-weighted independent set for the problem to numerically investigate the anticrossing. For comparison, we introduce a non-stoquastic Hamiltonian that adds antiferromagnetic interaction to the normal transverse magnetic field. Annealing with the non-stoquastic Hamiltonian is effective for difficult problems. The non-stoquastic Hamiltonian mitigates the anti-crossing when only the energy gap between the ground state and the first excited state of the final state is small. When the ELTIP is used, the anti-crossing disappears. For the problems investigated in this paper, the ELTIP shortens the annealing time to guarantee adiabatic change more than the non-stoquastic Hamiltonian.