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

The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo, Marios Rozos

cs.CCquant-phSubmitted May 4, 2026• Announced May 5, 2026• 3 citations
arXivHTMLPDF

Abstract

Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.

Related papers

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

The Complexity of Stoquastic Local Hamiltonian Problems

Sergey B. Bravyi, David Peter Divincenzo, Roberto I. Oliveira +1 more

We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM -- a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class POSTBPP=BPPpath -- a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP.

arXiv:quant-ph/0606140•Jun 16, 2006•106 citations

The complexity of stoquastic local Hamiltonian problems

Sergey B. Bravyi, David Peter Divincenzo, Roberto I. Oliveira +1 more

We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class \AM{}--- a probabilistic version of \NP{} with two rounds of communication between the prover and the verifier. We also show that $2$-local stoquastic LH-MIN is hard for the class \MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class \POSTBPP=\BPPpath --- a generalization of \BPP{} in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians is in PostBPP.

Quantum Information and Computation•May 1, 2008•205 citations

Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing

Marios Ioannou, Stephen Piddock, Milad Marvian +2 more

We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is $\textbf{StoqMA}$-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove $\textbf{coNP}$-hardness of deciding global stoquasticity in a fixed basis and $Σ_2^p$-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.

arXiv:2007.11964•Jul 23, 2020•12 citations

The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness

Itay Shalit, Mark Zhandry

The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.

quant-pharXiv:2609.38957•Oct 1, 2026•0 citations

On the complexity of estimating ground state entanglement and free energy

Sevag Gharibian, Jonas Kamminga

Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).

arXiv:2510.06796•Oct 8, 2025•3 citations
Despite having an unnatural definition, StoqMA\mathsf{StoqMA}StoqMA plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of NP\mathsf{NP}NP, MA\mathsf{MA}MA and AM\mathsf{AM}AM. Therefore, understanding the exact power of StoqMA\mathsf{StoqMA}StoqMA (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem (StoqSH\mathsf{StoqSH}StoqSH) is in StoqMA\mathsf{StoqMA}StoqMA. Since Stoquastic Local Hamiltonians are StoqMA\mathsf{StoqMA}StoqMA-hard, this implies that StoqSH\mathsf{StoqSH}StoqSH is StoqMA\mathsf{StoqMA}StoqMA-complete. We complement this result by showing that the separable version of StoqSH\mathsf{StoqSH}StoqSH is StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2)-complete, where StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2) is the version of StoqMA\mathsf{StoqMA}StoqMA that receives two unentangled proofs.
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.
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM -- a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class POSTBPP=BPPpath -- a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP.
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class \AM{}--- a probabilistic version of \NP{} with two rounds of communication between the prover and the verifier. We also show that 222-local stoquastic LH-MIN is hard for the class \MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class \POSTBPP=\BPPpath --- a generalization of \BPP{} in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians is in PostBPP.
We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We show that the stoquastic local Hamiltonian problem is StoqMA\textbf{StoqMA}StoqMA-complete even for globally stoquastic Hamiltonians. We study the complexity of deciding whether a local Hamiltonian is globally stoquastic or not. In particular, we prove coNP\textbf{coNP}coNP-hardness of deciding global stoquasticity in a fixed basis and Σ2pΣ_2^pΣ2p​-hardness of deciding global stoquasticity under single-qubit transformations. As a last result, we expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZXYZXYZ Hamiltonians.
The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in NP\mathsf{NP}NP for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is QMA\mathsf{QMA}QMA-complete. CLH is complete for the complexity class QIMA\mathsf{QIMA}QIMA, defined through quantum verifiers whose local gates commute. Therefore, CLH is QMA\mathsf{QMA}QMA-complete if and only if QIMA=QMA\mathsf{QIMA}=\mathsf{QMA}QIMA=QMA. In this work, we introduce a classical-oracle analogue QIMAO\mathsf{QIMA}^{\mathcal{O}}QIMAO and construct a classical oracle O\mathcal{O}O such that BQPO⊈QIMAO\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}BQPO⊆QIMAO. Since BQPO⊆QMAO\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}BQPO⊆QMAO for any classical oracle O\mathcal{O}O, this implies QIMAO≠QMAO\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}QIMAO=QMAO for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is BQP\mathsf{BQP}BQP-hard, and hence also against the possibility that it is QMA\mathsf{QMA}QMA-complete.
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).