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:0905.4755 · Physical Review A

Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices

Stephen P. Jordan, David Gosset, Peter J. Love

Published Mar 29, 2010• 41 citations
arXivHTMLPDF

Abstract

We show that finding the lowest eigenvalue of a $3$-local symmetric stochastic matrix is Quantum-Merlin-Arthur-complete (QMA-complete). We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration-free Hamiltonian is universal. Our results give a QMA-complete problem arising in the classical setting of Markov chains and adiabatically universal Hamiltonians that arise in many physical systems.

DOI
10.1103/physreva.81.032331

Related papers

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

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

The Complexity of the Consistency and N-representability Problems for Quantum States

Liu, Yi-Kai

QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices'': given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian'' and ``N-representability,'' are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960's, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic'' systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.

arXiv:0712.3041•Dec 18, 2007•19 citations

Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems

Alastair Kay

Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and $O\mathbf{(}\mathrm{log}(N)\mathbf{)}$-body local terms, or local dimension $N$ and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.

arXiv:0704.3142•Physical Review A•Sep 20, 2007•21 citations

Merlin-Arthur Games and Stoquastic Complexity

Sergey B. Bravyi, Arvid J. Bessen, Barbara M. Terhal

MA is a class of decision problems for which `yes'-instances have a proof that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem which we call the stoquastic k-SAT problem. This is a matrix-valued analogue of the satisfiability problem in which clauses are k-qubit projectors with non-negative matrix elements, while a satisfying assignment is a vector that belongs to the space spanned by these projectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete problem. We also study the minimum eigenvalue problem for local stoquastic Hamiltonians that was introduced in quant-ph/0606140, stoquastic LH-MIN. A new complexity class StoqMA is introduced so that stoquastic LH-MIN is StoqMA-complete. Lastly, we consider the average LH-MIN problem for local stoquastic Hamiltonians that depend on a random or `quenched disorder' parameter, stoquastic AV-LH-MIN. We prove that stoquastic AV-LH-MIN is contained in the complexity class \AM, the class of decision problems for which yes-instances have a randomized interactive proof with two-way communication between prover and verifier.

arXiv:quant-ph/0611021•Nov 2, 2006•40 citations
We show that finding the lowest eigenvalue of a 333-local symmetric stochastic matrix is Quantum-Merlin-Arthur-complete (QMA-complete). We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration-free Hamiltonian is universal. Our results give a QMA-complete problem arising in the classical setting of Markov chains and adiabatically universal Hamiltonians that arise in many physical systems.
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.
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 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.
QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices'': given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian'' and ``N-representability,'' are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960's, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic'' systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.
Here we present a problem related to the local Hamiltonian problem (identifying whether the ground-state energy falls within one of two ranges) which is restricted to being translationally invariant. We prove that for Hamiltonians with a fixed local dimension and O(log(N))O\mathbf{(}\mathrm{log}(N)\mathbf{)}O(log(N))-body local terms, or local dimension NNN and two-body terms, there are instances where finding the ground-state energy is quantum-Merlin-Arthur-complete and simulating the dynamics is BQP-complete (BQP denotes ``bounded error, quantum polynomial time''). We discuss the implications for the computational complexity of finding ground states of these systems and hence for any classical approximation techniques that one could apply including density-matrix renormalization group, matrix product states, and multiscale entanglement renormalization ansatz. One important example is a one-dimensional lattice of bosons with nearest-neighbor hopping at constant filling fraction---i.e., a generalization of the Bose-Hubbard model.
MA is a class of decision problems for which `yes'-instances have a proof that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem which we call the stoquastic k-SAT problem. This is a matrix-valued analogue of the satisfiability problem in which clauses are k-qubit projectors with non-negative matrix elements, while a satisfying assignment is a vector that belongs to the space spanned by these projectors. Stoquastic k-SAT is the first non-trivial example of a MA-complete problem. We also study the minimum eigenvalue problem for local stoquastic Hamiltonians that was introduced in quant-ph/0606140, stoquastic LH-MIN. A new complexity class StoqMA is introduced so that stoquastic LH-MIN is StoqMA-complete. Lastly, we consider the average LH-MIN problem for local stoquastic Hamiltonians that depend on a random or `quenched disorder' parameter, stoquastic AV-LH-MIN. We prove that stoquastic AV-LH-MIN is contained in the complexity class \AM, the class of decision problems for which yes-instances have a randomized interactive proof with two-way communication between prover and verifier.