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:2509.25821 · npj Quantum Information

On the complexity of the succinct state local Hamiltonian problem

Gabriel Waite, Karl Lin

Published Nov 10, 2026• 5 citations
arXivHTMLPDF

Abstract

Abstract We study the computational complexity of the LOCAL HAMILTONIAN problem under the promise that its ground state, or a low-energy state, is succinctly represented. We show, for qubit Hamiltonians, that the SUCCINCT LOW-ENERGY STATE 2-LOCAL HAMILTONIAN problem, is (promise) MA -hard and the SUCCINCT GROUND STATE 3-LOCAL HAMILTONIAN problem is (promise) MA -complete. Our approach combines a systematic characterisation of succinct quantum states, defined through arithmetic over specific number fields, with a refined complexity-theoretic reduction that lowers the locality of Feynman–Kitaev circuit-Hamiltonians from 6 to 2, without increasing particle dimension. Since the 1-local case is solvable in P , these results narrow the locality-parameterised complexity transition and extend the scope of known MA -complete problem instances. Our results further clarify how succinctness behaves under circuit-based constructions, and progress towards a better understanding of the boundary between efficiently describable and efficiently verifiable quantum systems.

DOI
10.1038/s41534-026-01375-z

Related papers

Local Hamiltonian Problem with Succinct Ground State is MA-Complete

Jiaqing Jiang

Finding the ground energy of a quantum system is a fundamental problem in condensed-matter physics and quantum chemistry. Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description, i.e., a poly-size classical circuit for computing the amplitude. Notable examples of succinct states encompass matrix product states, contractible projected-entangled-pair states, and states that can be represented by classical neural networks. We study the complexity of the local Hamiltonian problem (LHP) with a succinct ground state. We prove that this problem is MA - complete . The Hamiltonian that we consider is general and might not be stoquastic. The MA verification protocol is based on the fixed-node quantum Monte Carlo method, particularly the variant of the continuous-time Markov chain introduced by Bravyi, Carleo, Gosset, and Liu. Based on our work, we also introduce a notion of strong guided states and conjecture that the LHP with a strong guided state is MA - complete , which will be in contrast with the QCMA - complete result of the LHP with standard guided states.

arXiv:2309.10155•PRX Quantum•Apr 17, 2025•15 citations

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1 more

The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.

quant-pharXiv:2602.14379•Leibniz international proceedings in informatics•Feb 17, 2026•2 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.

arXiv:0806.1746•SIAM Journal on Computing•Nov 20, 2009•142 citations

On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems

Dorit Aharonov, Lior Eldar

The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.

arXiv:1102.0770•Annual Symposium on Foundations of Computer Science•Oct 1, 2011•68 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•5 citations

The Complexity of Translationally Invariant Problems Beyond Ground State Energies

James D. Watson, Johannes Bausch, Sevag Gharibian

It is known that three fundamental questions regarding local Hamiltonians -- approximating the ground state energy (the Local Hamiltonian problem), simulating local measurements on the ground space (APX-SIM), and deciding if the low energy space has an energy barrier (GSCON) -- are $\mathsf{QMA}$-hard, $\mathsf{P}^{\mathsf{QMA}[log]}$-hard and $\mathsf{QCMA}$-hard, respectively, meaning they are likely intractable even on a quantum computer. Yet while hardness for the Local Hamiltonian problem is known to hold even for translationally-invariant systems, it is not yet known whether APX-SIM and GSCON remain hard in such "simple" systems. In this work, we show that the translationally invariant versions of both APX-SIM and GSCON remain intractable, namely are $\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}$- and $\mathsf{QCMA}_{\mathsf{EXP}}$-complete, respectively. Each of these results is attained by giving a respective generic "lifting theorem" for producing hardness results. For APX-SIM, for example, we give a framework for "lifting" any abstract local circuit-to-Hamiltonian mapping $H$ (satisfying mild assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by $H$, while preserving the structural and geometric properties of $H$ (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we "compress" the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we give a hardness construction robust against highly non-local unitaries, i.e. even if the adversary acts on all but one qudit in the system in each step.

arXiv:2012.12717•Leibniz international proceedings in informatics•Dec 23, 2020•14 citations
Abstract We study the computational complexity of the LOCAL HAMILTONIAN problem under the promise that its ground state, or a low-energy state, is succinctly represented. We show, for qubit Hamiltonians, that the SUCCINCT LOW-ENERGY STATE 2-LOCAL HAMILTONIAN problem, is (promise) MA -hard and the SUCCINCT GROUND STATE 3-LOCAL HAMILTONIAN problem is (promise) MA -complete. Our approach combines a systematic characterisation of succinct quantum states, defined through arithmetic over specific number fields, with a refined complexity-theoretic reduction that lowers the locality of Feynman–Kitaev circuit-Hamiltonians from 6 to 2, without increasing particle dimension. Since the 1-local case is solvable in P , these results narrow the locality-parameterised complexity transition and extend the scope of known MA -complete problem instances. Our results further clarify how succinctness behaves under circuit-based constructions, and progress towards a better understanding of the boundary between efficiently describable and efficiently verifiable quantum systems.
Finding the ground energy of a quantum system is a fundamental problem in condensed-matter physics and quantum chemistry. Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description, i.e., a poly-size classical circuit for computing the amplitude. Notable examples of succinct states encompass matrix product states, contractible projected-entangled-pair states, and states that can be represented by classical neural networks. We study the complexity of the local Hamiltonian problem (LHP) with a succinct ground state. We prove that this problem is MA - complete . The Hamiltonian that we consider is general and might not be stoquastic. The MA verification protocol is based on the fixed-node quantum Monte Carlo method, particularly the variant of the continuous-time Markov chain introduced by Bravyi, Carleo, Gosset, and Liu. Based on our work, we also introduce a notion of strong guided states and conjecture that the LHP with a strong guided state is MA - complete , which will be in contrast with the QCMA - complete result of the LHP with standard guided states.
The local Hamiltonian (LH) problem is the canonical QMA\mathsf{QMA}QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on nnn qubits cannot be solved classically in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n) for any ε>0\varepsilon>0ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2)O(2^{(1-\varepsilon)n/2})O(2(1−ε)n/2) for any ε>0\varepsilon>0ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA\mathsf{QMA}QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n)O(\sqrt{2^n})O(2n​) time for an arbitrary 1/poly(n)1/\mathrm{poly}(n)1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a TTT-time quantum circuit acting on NNN qubits into a (d+1)(d+1)(d+1)-local Hamiltonian acting on N+O(T1/d)N+O(T^{1/d})N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T)N+O(T)N+O(T) qubits.
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 local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.
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.
It is known that three fundamental questions regarding local Hamiltonians -- approximating the ground state energy (the Local Hamiltonian problem), simulating local measurements on the ground space (APX-SIM), and deciding if the low energy space has an energy barrier (GSCON) -- are QMA\mathsf{QMA}QMA-hard, PQMA[log]\mathsf{P}^{\mathsf{QMA}[log]}PQMA[log]-hard and QCMA\mathsf{QCMA}QCMA-hard, respectively, meaning they are likely intractable even on a quantum computer. Yet while hardness for the Local Hamiltonian problem is known to hold even for translationally-invariant systems, it is not yet known whether APX-SIM and GSCON remain hard in such "simple" systems. In this work, we show that the translationally invariant versions of both APX-SIM and GSCON remain intractable, namely are PQMAEXP\mathsf{P}^{\mathsf{QMA}_{\mathsf{EXP}}}PQMAEXP​- and QCMAEXP\mathsf{QCMA}_{\mathsf{EXP}}QCMAEXP​-complete, respectively. Each of these results is attained by giving a respective generic "lifting theorem" for producing hardness results. For APX-SIM, for example, we give a framework for "lifting" any abstract local circuit-to-Hamiltonian mapping HHH (satisfying mild assumptions) to hardness of APX-SIM on the family of Hamiltonians produced by HHH, while preserving the structural and geometric properties of HHH (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we "compress" the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we give a hardness construction robust against highly non-local unitaries, i.e. even if the adversary acts on all but one qudit in the system in each step.