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:2606.09995

Quantum resources in non-stoquastic quantum annealing

Chiara Capecci, Sebastian Nagies, Naga Dileep Varikuti, Philipp Hauke

quant-phSubmitted Jun 8, 2026• Announced Jun 10, 2026• 3 citations
arXivHTMLPDF

Abstract

Quantum annealing promises to solve combinatorial optimization problems by preparing the ground state of a target Hamiltonian. Standard annealing protocols are, however, stoquastic and can thus be simulated by sign-problem-free quantum Monte-Carlo methods. To obtain a true quantum advantage, it has been proposed to use non-stoquastic catalyst Hamiltonians. Active only at intermediate stages of the protocol, these can, for certain problems, convert first-order into second-order quantum phase transitions and thus permit an exponential speedup over the stoquastic protocol. At the same time, the non-stoquastic catalyst renders quantum Monte-Carlo methods inefficient. It remains, however, an open question how other classical computation methods are affected by the non-stoquastic terms. We address this question by computing quantum resources -- entanglement entropy and stabilizer Rényi entropy -- whose presence makes classical computations based on tensor networks and stabilizer-tableau methods exponentially hard. We compare these with the spectral gap along the annealing path for two paradigmatic benchmark models, the fully connected $p$-spin model and a geometrically local Ising model. While the exact behavior shows a subtle dependency on the underlying model and the annealing path, our numerics suggest consistently that the scaling of entanglement and non-stabilizerness is at least maintained in the deeply non-stoquastic regime and in some cases even significantly enhanced. Our results thus suggest that improvements of quantum performance in non-stoquastic annealing coincide with significant presence of quantum computational resources.

Comments
21 pages, 11 figures

Related papers

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•106 citations

Improving nonstoquastic quantum annealing with spin-reversal transformations

E. M. Lykiardopoulou, Alex Zucca, Sam A. Scivier +1 more

Nonstoquastic Hamiltonians are hard to simulate due to the sign problem in quantum Monte Carlo simulation. It is, however, unclear whether nonstoquasticity can lead to advantage in quantum annealing. Here we show that $YY$ interactions between the qubits make the adiabatic path during quantum annealing, and therefore the performance, dependent on spin-reversal transformations. With the right choice of spin-reversal transformation, a nonstoquastic Hamiltonian with $YY$ interaction can outperform stoquastic Hamiltonians with similar parameters. We introduce an optimization protocol to determine the optimal transformation and discuss the effect of suboptimality.

arXiv:2010.00065•Physical Review A•Jul 29, 2021•6 citations

Best Annealing Path of Quantum Annealing via Efficient Adiabatic Phase Transition

Kiyotaka Murashima

Quantum Annealing (QA) has already put into practical use and considered useful for solving many social issues, such as reduction of traffic congestion and delivery optimization. But in QA, when the energy difference between the ground state and the first excited state is small, the transition probability between them increases. Therefore, in order to decrease the transition, QA has to be performed at extremely low temperatures. To simulate the situation, it has the problem in that it takes much time. Many studies are underway to accelerate QA theoretically, one of which is to incorporate non-stoquastic Hamiltonian. On the other hand, I proposed Nested Simulated Annealing (NSA) inspired by Quantum Monte Carlo (QMC). I showed the computational speedup could be achieved dramatically, by considering the idea that the effect of flipping a spin preferentially influenced the spins directly interacting with it. Although NSA was based on such classical concept of causality, the hybrid computation both quantum and classical approach worked well. In this paper, in order to discuss the relationship between NSA and non-stoquastic Hamiltonian like XX-interaction, the spins are treated as continuous variables. I derive the formula to calculate the total energy in both with a problem Hamiltonian and the perturbation Hamiltonian induced by a transverse electromagnetic field. And I will show a clear relationship between local-maxima and the convergence speed when calculating it with the binary spin. More precisely, the annealing path with the smallest local-maxima converges fast, even though it consumes fewer computational resources. Therefore, it is possible to induce an optimal adiabatic phase transition by selecting NSA parameters appropriately. This paper shows an effective method to choose the parameters when simulating QMC on a classical computer.

quant-pharXiv:2608.30282•Sep 1, 2026•0 citations

Quantum speedup in stoquastic adiabatic quantum computation

Keisuke Fujii

Quantum computation provides exponential speedup for solving certain mathematical problems against classical computers. Motivated by current rapid experimental progress on quantum computing devices, various models of quantum computation have been investigated to show quantum computational supremacy. At a commercial side, quantum annealing machine realizes the quantum Ising model with a transverse field and heuristically solves combinatorial optimization problems. The computational power of this machine is closely related to adiabatic quantum computation (AQC) with a restricted type of Hamiltonians, namely stoquastic Hamiltonians, and has been thought to be relatively less powerful compared to universal quantum computers. Little is known about computational quantum speedup nor advantage in AQC with stoquastic Hamiltonians. Here we characterize computational capability of AQC with stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC model, whose lowest energy gap is lower bounded polynomially, and hence the final state can be obtained in polynomial time. Then we show that it can simulate universal quantum computation if adaptive single-qubit measurements in non-standard bases are allowed on the final state. Even if the measurements are restricted to non-adaptive measurements to respect the robustness of AQC, the proposed model exhibits quantum computational supremacy; classical simulation is impossible under complexity theoretical conjectures. Moreover, it is found that such a stoqAQC model can simulate Shor's algorithm and solve the factoring problem in polynomial time. We also propose how to overcome the measurement imperfections via quantum error correction within the stoqAQC model and also an experimentally feasible verification scheme to test whether or not stoqAQC is done faithfully.

arXiv:1803.09954•Mar 27, 2018•14 citations

Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions

Rudraksh Sharma, Ravi Katukam, Arjun Nagulapally

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.

quant-pharXiv:2602.03101•International Journal for Research in Applied Science and Engineering Technology•Feb 4, 2026•3 citations

Nonequilibrium quantum Monte Carlo algorithm for stabilizer Rényi entropy in spin systems

Zejun Liu, Bryan K. Clark

Quantum magic, or nonstabilizerness, provides a crucial characterization of quantum systems, regarding the classical simulability with stabilizer states. In this work, we propose an alternative and efficient algorithm for computing stabilizer R\'enyi entropy, one of the measures for quantum magic, in spin systems with sign-problem free Hamiltonians. This algorithm is based on the quantum Monte Carlo simulation of the path integral of the work between two partition function ensembles and it applies to all spatial dimensions and temperatures. We demonstrate this algorithm on the one- and two-dimensional transverse field Ising model at both finite and zero temperatures and show the quantitative agreements with tensor-network based algorithms. We analyze the computational cost and provide analytical and numerical evidences for it to be polynomial in system size. This work also suggests a unifying framework for calculating various types of entropy quantities including entanglement R\'enyi entropy and entanglement R\'enyi negativity.

arXiv:2405.19577•Physical review. B./Physical review. B•Feb 20, 2025•25 citations
Quantum annealing promises to solve combinatorial optimization problems by preparing the ground state of a target Hamiltonian. Standard annealing protocols are, however, stoquastic and can thus be simulated by sign-problem-free quantum Monte-Carlo methods. To obtain a true quantum advantage, it has been proposed to use non-stoquastic catalyst Hamiltonians. Active only at intermediate stages of the protocol, these can, for certain problems, convert first-order into second-order quantum phase transitions and thus permit an exponential speedup over the stoquastic protocol. At the same time, the non-stoquastic catalyst renders quantum Monte-Carlo methods inefficient. It remains, however, an open question how other classical computation methods are affected by the non-stoquastic terms. We address this question by computing quantum resources -- entanglement entropy and stabilizer Rényi entropy -- whose presence makes classical computations based on tensor networks and stabilizer-tableau methods exponentially hard. We compare these with the spectral gap along the annealing path for two paradigmatic benchmark models, the fully connected ppp-spin model and a geometrically local Ising model. While the exact behavior shows a subtle dependency on the underlying model and the annealing path, our numerics suggest consistently that the scaling of entanglement and non-stabilizerness is at least maintained in the deeply non-stoquastic regime and in some cases even significantly enhanced. Our results thus suggest that improvements of quantum performance in non-stoquastic annealing coincide with significant presence of quantum computational resources.
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.
Nonstoquastic Hamiltonians are hard to simulate due to the sign problem in quantum Monte Carlo simulation. It is, however, unclear whether nonstoquasticity can lead to advantage in quantum annealing. Here we show that YYYYYY interactions between the qubits make the adiabatic path during quantum annealing, and therefore the performance, dependent on spin-reversal transformations. With the right choice of spin-reversal transformation, a nonstoquastic Hamiltonian with YYYYYY interaction can outperform stoquastic Hamiltonians with similar parameters. We introduce an optimization protocol to determine the optimal transformation and discuss the effect of suboptimality.
Quantum Annealing (QA) has already put into practical use and considered useful for solving many social issues, such as reduction of traffic congestion and delivery optimization. But in QA, when the energy difference between the ground state and the first excited state is small, the transition probability between them increases. Therefore, in order to decrease the transition, QA has to be performed at extremely low temperatures. To simulate the situation, it has the problem in that it takes much time. Many studies are underway to accelerate QA theoretically, one of which is to incorporate non-stoquastic Hamiltonian. On the other hand, I proposed Nested Simulated Annealing (NSA) inspired by Quantum Monte Carlo (QMC). I showed the computational speedup could be achieved dramatically, by considering the idea that the effect of flipping a spin preferentially influenced the spins directly interacting with it. Although NSA was based on such classical concept of causality, the hybrid computation both quantum and classical approach worked well. In this paper, in order to discuss the relationship between NSA and non-stoquastic Hamiltonian like XX-interaction, the spins are treated as continuous variables. I derive the formula to calculate the total energy in both with a problem Hamiltonian and the perturbation Hamiltonian induced by a transverse electromagnetic field. And I will show a clear relationship between local-maxima and the convergence speed when calculating it with the binary spin. More precisely, the annealing path with the smallest local-maxima converges fast, even though it consumes fewer computational resources. Therefore, it is possible to induce an optimal adiabatic phase transition by selecting NSA parameters appropriately. This paper shows an effective method to choose the parameters when simulating QMC on a classical computer.
Quantum computation provides exponential speedup for solving certain mathematical problems against classical computers. Motivated by current rapid experimental progress on quantum computing devices, various models of quantum computation have been investigated to show quantum computational supremacy. At a commercial side, quantum annealing machine realizes the quantum Ising model with a transverse field and heuristically solves combinatorial optimization problems. The computational power of this machine is closely related to adiabatic quantum computation (AQC) with a restricted type of Hamiltonians, namely stoquastic Hamiltonians, and has been thought to be relatively less powerful compared to universal quantum computers. Little is known about computational quantum speedup nor advantage in AQC with stoquastic Hamiltonians. Here we characterize computational capability of AQC with stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC model, whose lowest energy gap is lower bounded polynomially, and hence the final state can be obtained in polynomial time. Then we show that it can simulate universal quantum computation if adaptive single-qubit measurements in non-standard bases are allowed on the final state. Even if the measurements are restricted to non-adaptive measurements to respect the robustness of AQC, the proposed model exhibits quantum computational supremacy; classical simulation is impossible under complexity theoretical conjectures. Moreover, it is found that such a stoqAQC model can simulate Shor's algorithm and solve the factoring problem in polynomial time. We also propose how to overcome the measurement imperfections via quantum error correction within the stoqAQC model and also an experimentally feasible verification scheme to test whether or not stoqAQC is done faithfully.
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 magic, or nonstabilizerness, provides a crucial characterization of quantum systems, regarding the classical simulability with stabilizer states. In this work, we propose an alternative and efficient algorithm for computing stabilizer R\'enyi entropy, one of the measures for quantum magic, in spin systems with sign-problem free Hamiltonians. This algorithm is based on the quantum Monte Carlo simulation of the path integral of the work between two partition function ensembles and it applies to all spatial dimensions and temperatures. We demonstrate this algorithm on the one- and two-dimensional transverse field Ising model at both finite and zero temperatures and show the quantitative agreements with tensor-network based algorithms. We analyze the computational cost and provide analytical and numerical evidences for it to be polynomial in system size. This work also suggests a unifying framework for calculating various types of entropy quantities including entanglement R\'enyi entropy and entanglement R\'enyi negativity.