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

Dismantling the Stoquastic Dichotomy

Armen Karakashian, Itay Hen

quant-phcs.CCphysics.comp-phSubmitted Jul 21, 2026• Announced Jul 22, 2026• 0 citations
arXivHTMLPDF

Abstract

We challenge the notion that a stoquastic binary governs fundamental computational boundaries in quantum computing and classical simulation of quantum systems. We argue that vanishing geometric phase (VGP), a geometric condition on the Hamiltonian's transition graph, more adequately captures these boundaries. To distinguish VGP from stoquasticity, we construct VGP 3-local Hamiltonians that are formally hard to stoquastize, yet belong to a family admitting polynomial-time recognition of the VGP property. Without constructing a stoquastizing unitary, we prove that the local Hamiltonian problem is $\mathsf{StoqMA}$-complete under the promise that the input Hamiltonian has VGP, and that a frustration-free variant is in $\mathsf{MA}$ under the same promise. We use this result to argue that non-VGP is necessary for any claimed adiabatic advantage justified by escaping the $\mathsf{StoqMA}$ regime. Further, we identify natural settings where the VGP property can be recognized in polynomial time. In contrast, we show that recognition of VGP is $\mathsf{PSPACE}$-complete in general for geometrically local Hamiltonians. Our results show that the computational boundaries $\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq \mathsf{QMA}$ traditionally attributed to stoquasticity are better understood as boundaries between vanishing and non-vanishing geometric phase structure.

Comments
33 pages, 1 figure

Related papers

Stoquasticity is not enough: towards a sharper diagnostic for Quantum Monte Carlo simulability

Arman Babakhani, Karakashian, Armen

Quantum Monte Carlo (QMC) methods are powerful tools for simulating quantum many-body systems, yet their applicability is limited by the infamous sign problem. We approach this challenge through the lens of Vanishing Geometric Phases (VGP) \cite{Hen_2021}, introducing it as a `geometric' criterion for diagnosing QMC simulability. We characterize the class of VGP Hamiltonians, and analyze the complexity of recognizing this class, identifying both hard and efficiently identifiable cases. We further highlight the practical advantage of the VGP criterion by exhibiting specific Hamiltonians that are readily identified as sign-problem-free through VGP, yet whose stoquasticity is difficult to ascertain. These examples underscore the efficiency and sharpness of VGP as a diagnostic tool compared to stoquasticity-based heuristics. Beyond classification, we propose a family of VGP-inspired diagnostics that serve as quantitative indicators of sign problem severity. While exact evaluation of these quantities is generically intractable, we demonstrate their mathematical power in performing scaling analysis for the average sign under unitary transformations. Our results provide both a conceptual foundation and practical tools for understanding and mitigating the sign problem.

arXiv:2508.14382•Aug 20, 2025•0 citations

Non-stoquastic Hamiltonians in quantum annealing via geometric phases

Walter Vinci, Daniel A. Lidar

Abstract We argue that a complete description of quantum annealing implemented with continuous variables must take into account the non-adiabatic Aharonov-Anandan geometric phase that arises when the system Hamiltonian changes during the anneal. We show that this geometric effect leads to the appearance of non-stoquasticity in the effective quantum Ising Hamiltonians that are typically used to describe quantum annealing with flux qubits. We explicitly demonstrate the effect of this geometric non-stoquasticity when quantum annealing is performed with a system of one and two coupled flux qubits. The realization of non-stoquastic Hamiltonians has important implications from a computational complexity perspective, since it is believed that in many cases quantum annealing with stoquastic Hamiltonians can be efficiently simulated via classical algorithms such as Quantum Monte Carlo. It is well known that the direct implementation of non-stoquastic Hamiltonians with flux qubits is particularly challenging. Our results suggest an alternative path for the implementation of non-stoquasticity via geometric phases that can be exploited for computational purposes.

arXiv:1701.07494•npj Quantum Information•Sep 5, 2017•49 citations

Complexity of stoquastic frustration-free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration free" ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_a H_a$ where (1) every term $H_a$ acts non-trivially on a constant number of qubits, (2) every term $H_a$ has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of $H$ is a ground-state of every term $H_a$. Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant $k$, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.

arXiv:0806.1746•Jun 10, 2008•3 citations

Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms

Kazuki Sakamoto, Keisuke Fujii

The Berry phase is a fundamental geometric quantity for characterizing the geometry and topology of quantum many-body systems. Previous work established a super-polynomial quantum advantage in Berry phase estimation at inverse-polynomial precision, given an ansatz state approximating the initial ground state. However, whether this hardness persists for Berry phases quantized by symmetry, which can be distinguished at constant precision, remained open. In this work, we characterize the computational complexity of quantized Berry phase estimation. First, we prove that deciding whether the Berry phase is exactly $0$ or $π$ is $\mathsf{BQP}$-complete when the spectral gap is inverse-polynomially small. This result implies that distinguishing the quantized Berry phase still has a super-polynomial quantum advantage, assuming $\mathsf{BPP}\neq \mathsf{BQP}$. To prove this result, we introduce an encoding that maps the output of any quantum computation to a Berry phase that is exactly $0$ or $π$. Second, we extend this hardness to physically motivated Hamiltonians on a 2D square lattice, including Heisenberg and XY interactions. Third, we provide a classical polynomial-time algorithm for geometrically local Hamiltonians on fixed-dimensional lattices with constant spectral gaps. Therefore we identify that the spectral gap is a key resource for the classical tractability, rather than precision. These results establish a super-polynomial quantum advantage for computing a quantized topological invariant that is unchanged under symmetry- and gap-preserving deformations, and provide new steps towards practical quantum advantage in quantum physics.

quant-pharXiv:2609.37199•Sep 30, 2026•0 citations

Complexity of Stoquastic Frustration-Free Hamiltonians

Sergey B. Bravyi, Barbara M. Terhal

We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as $H=\sum_{a}H_{a}$ where (1) every term $H_{a}$ acts nontrivially on a constant number of qubits, (2) every term $H_{a}$ has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term $H_{a}$. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.

SIAM Journal on Computing•Nov 20, 2009•124 citations

Complexity of geometrically local stoquastic Hamiltonians

Asad Raza, Jens Eisert, Alex B. Grilo

The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.

arXiv:2407.15499•Quantum•Feb 11, 2026•0 citations
We challenge the notion that a stoquastic binary governs fundamental computational boundaries in quantum computing and classical simulation of quantum systems. We argue that vanishing geometric phase (VGP), a geometric condition on the Hamiltonian's transition graph, more adequately captures these boundaries. To distinguish VGP from stoquasticity, we construct VGP 3-local Hamiltonians that are formally hard to stoquastize, yet belong to a family admitting polynomial-time recognition of the VGP property. Without constructing a stoquastizing unitary, we prove that the local Hamiltonian problem is StoqMA\mathsf{StoqMA}StoqMA-complete under the promise that the input Hamiltonian has VGP, and that a frustration-free variant is in MA\mathsf{MA}MA under the same promise. We use this result to argue that non-VGP is necessary for any claimed adiabatic advantage justified by escaping the StoqMA\mathsf{StoqMA}StoqMA regime. Further, we identify natural settings where the VGP property can be recognized in polynomial time. In contrast, we show that recognition of VGP is PSPACE\mathsf{PSPACE}PSPACE-complete in general for geometrically local Hamiltonians. Our results show that the computational boundaries MA⊆StoqMA⊆QMA\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq \mathsf{QMA}MA⊆StoqMA⊆QMA traditionally attributed to stoquasticity are better understood as boundaries between vanishing and non-vanishing geometric phase structure.
Quantum Monte Carlo (QMC) methods are powerful tools for simulating quantum many-body systems, yet their applicability is limited by the infamous sign problem. We approach this challenge through the lens of Vanishing Geometric Phases (VGP) \cite{Hen_2021}, introducing it as a `geometric' criterion for diagnosing QMC simulability. We characterize the class of VGP Hamiltonians, and analyze the complexity of recognizing this class, identifying both hard and efficiently identifiable cases. We further highlight the practical advantage of the VGP criterion by exhibiting specific Hamiltonians that are readily identified as sign-problem-free through VGP, yet whose stoquasticity is difficult to ascertain. These examples underscore the efficiency and sharpness of VGP as a diagnostic tool compared to stoquasticity-based heuristics. Beyond classification, we propose a family of VGP-inspired diagnostics that serve as quantitative indicators of sign problem severity. While exact evaluation of these quantities is generically intractable, we demonstrate their mathematical power in performing scaling analysis for the average sign under unitary transformations. Our results provide both a conceptual foundation and practical tools for understanding and mitigating the sign problem.
Abstract We argue that a complete description of quantum annealing implemented with continuous variables must take into account the non-adiabatic Aharonov-Anandan geometric phase that arises when the system Hamiltonian changes during the anneal. We show that this geometric effect leads to the appearance of non-stoquasticity in the effective quantum Ising Hamiltonians that are typically used to describe quantum annealing with flux qubits. We explicitly demonstrate the effect of this geometric non-stoquasticity when quantum annealing is performed with a system of one and two coupled flux qubits. The realization of non-stoquastic Hamiltonians has important implications from a computational complexity perspective, since it is believed that in many cases quantum annealing with stoquastic Hamiltonians can be efficiently simulated via classical algorithms such as Quantum Monte Carlo. It is well known that the direct implementation of non-stoquastic Hamiltonians with flux qubits is particularly challenging. Our results suggest an alternative path for the implementation of non-stoquasticity via geometric phases that can be exploited for computational purposes.
We study several problems related to properties of non-negative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a "frustration free" ground-state. A Hamiltonian belongs to this class iff it can be represented as H=∑aHaH=\sum_a H_aH=∑a​Ha​ where (1) every term HaH_aHa​ acts non-trivially on a constant number of qubits, (2) every term HaH_aHa​ has real non-positive off-diagonal matrix elements in the standard basis, and (3) the ground-state of HHH is a ground-state of every term HaH_aHa​. Secondly, we generalize the Cook-Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA -- a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call "stoquastic k-SAT" such that stoquastic k-SAT is contained in MA for any constant kkk, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first non-trivial example of a MA-complete promise problem.
The Berry phase is a fundamental geometric quantity for characterizing the geometry and topology of quantum many-body systems. Previous work established a super-polynomial quantum advantage in Berry phase estimation at inverse-polynomial precision, given an ansatz state approximating the initial ground state. However, whether this hardness persists for Berry phases quantized by symmetry, which can be distinguished at constant precision, remained open. In this work, we characterize the computational complexity of quantized Berry phase estimation. First, we prove that deciding whether the Berry phase is exactly 000 or πππ is BQP\mathsf{BQP}BQP-complete when the spectral gap is inverse-polynomially small. This result implies that distinguishing the quantized Berry phase still has a super-polynomial quantum advantage, assuming BPP≠BQP\mathsf{BPP}\neq \mathsf{BQP}BPP=BQP. To prove this result, we introduce an encoding that maps the output of any quantum computation to a Berry phase that is exactly 000 or πππ. Second, we extend this hardness to physically motivated Hamiltonians on a 2D square lattice, including Heisenberg and XY interactions. Third, we provide a classical polynomial-time algorithm for geometrically local Hamiltonians on fixed-dimensional lattices with constant spectral gaps. Therefore we identify that the spectral gap is a key resource for the classical tractability, rather than precision. These results establish a super-polynomial quantum advantage for computing a quantized topological invariant that is unchanged under symmetry- and gap-preserving deformations, and provide new steps towards practical quantum advantage in quantum physics.
We study several problems related to properties of nonnegative matrices that arise at the boundary between quantum and classical probabilistic computation. Our results are twofold. First, we identify a large class of quantum Hamiltonians describing systems of qubits for which the adiabatic evolution can be efficiently simulated on a classical probabilistic computer. These are stoquastic local Hamiltonians with a “frustration-free” ground-state. A Hamiltonian belongs to this class iff it can be represented as H=∑aHaH=\sum_{a}H_{a}H=∑a​Ha​ where (1) every term HaH_{a}Ha​ acts nontrivially on a constant number of qubits, (2) every term HaH_{a}Ha​ has real nonpositive off-diagonal matrix elements in the standard basis, and (3) the ground-state of H is a ground-state of every term HaH_{a}Ha​. Second, we generalize the Cook–Levin theorem proving NP-completeness of the satisfiability problem to the complexity class MA (Merlin–Arthur games)—a probabilistic analogue of NP. Specifically, we construct a quantum version of the k-SAT problem which we call “stoquastic k-SAT” such that stoquastic k-SAT is contained in MA for any constant k, and any promise problem in MA is Karp-reducible to stoquastic 6-SAT. This result provides the first nontrivial example of a MA-complete promise problem.
The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.