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

Sign-curing local Hamiltonians: termwise versus global stoquasticity and the use of Clifford transformations.

Marios Ioannou, Stephen Piddock, Milad Marvian, Joel Klassen, Barbara M. Terhal

Published Jul 23, 2020• 3 citations
OpenAlex

Abstract

We elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We prove coNP-hardness of deciding global stoquasticity in a fixed basis and $\Sigma_2^p$-hardness of deciding global stoquasticity under single-qubit transformations. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZ Hamiltonians.

Related papers

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

Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians

Joel Klassen, Milad Marvian, Stephen Piddock +3 more

We examine the problem of determining whether a multiqubit two-local Hamiltonian can be made stoquastic by single-qubit unitary transformations. We prove that when such a Hamiltonian contains one-local terms, then this task can be NP-hard. This is shown by constructing a class of Hamiltonians for which performing this task is equivalent to deciding 3-SAT. In contrast, we show that when such a Hamiltonian contains no one-local terms then this task is easy; namely, we present an algorithm which decides, in a number of arithmetic operations over $\mathbb{R}$ which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.

arXiv:1906.08800•SIAM Journal on Computing•Jan 1, 2020•24 citations

The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo, Marios Rozos

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.

cs.CCCross-listedarXiv:2605.02845•May 5, 2026•0 citations

On the computational complexity of curing non-stoquastic Hamiltonians

Milad Marvian, Daniel A. Lidar, Itay Hen

Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.

arXiv:1802.03408•Nature Communications•Apr 5, 2019•58 citations

Two-local qubit Hamiltonians: when are they stoquastic?

Joel Klassen, Barbara M. Terhal

We examine the problem of determining if a 2-local Hamiltonian is stoquastic by local basis changes. We analyze this problem for two-qubit Hamiltonians, presenting some basic tools and giving a concrete example where using unitaries beyond Clifford rotations is required in order to decide stoquasticity. We report on simple results for n -qubit Hamiltonians with identical 2-local terms on bipartite graphs. Our most significant result is that we give an efficient algorithm to determine whether an arbitrary n -qubit XYZ Heisenberg Hamiltonian is stoquastic by local basis changes.

arXiv:1806.05405•Quantum•May 6, 2019•29 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 elucidate the distinction between global and termwise stoquasticity for local Hamiltonians and prove several complexity results. We prove coNP-hardness of deciding global stoquasticity in a fixed basis and Σ2p\Sigma_2^pΣ2p​-hardness of deciding global stoquasticity under single-qubit transformations. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D XYZ Hamiltonians.
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.
We examine the problem of determining whether a multiqubit two-local Hamiltonian can be made stoquastic by single-qubit unitary transformations. We prove that when such a Hamiltonian contains one-local terms, then this task can be NP-hard. This is shown by constructing a class of Hamiltonians for which performing this task is equivalent to deciding 3-SAT. In contrast, we show that when such a Hamiltonian contains no one-local terms then this task is easy; namely, we present an algorithm which decides, in a number of arithmetic operations over R\mathbb{R}R which is polynomial in the number of qubits, whether the sign problem of the Hamiltonian can be cured by single-qubit rotations.
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.
Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.
We examine the problem of determining if a 2-local Hamiltonian is stoquastic by local basis changes. We analyze this problem for two-qubit Hamiltonians, presenting some basic tools and giving a concrete example where using unitaries beyond Clifford rotations is required in order to decide stoquasticity. We report on simple results for n -qubit Hamiltonians with identical 2-local terms on bipartite graphs. Our most significant result is that we give an efficient algorithm to determine whether an arbitrary n -qubit XYZ Heisenberg Hamiltonian is stoquastic by local basis changes.
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.