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:2309.10155 · PRX Quantum

Local Hamiltonian Problem with Succinct Ground State is MA-Complete

Jiaqing Jiang

Published Apr 17, 2025• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/prxquantum.6.020312

Related papers

On the complexity of the succinct state local Hamiltonian problem

Gabriel Waite, Karl Lin

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.

arXiv:2509.25821•npj Quantum Information•Nov 10, 2026•5 citations

Physically motivated guiding states for local Hamiltonians

Gabriel Waite, Karl Lin, Samuel J. Elman +1 more

We study the computational complexity of the Guided Local Hamiltonian problem: given a local Hamiltonian $H$ together with a classical description of a guiding state that has non-negligible overlap with the ground state of $H$, estimate the ground-state energy within inverse-polynomial precision. This setting captures real-world scenarios in quantum chemistry and many-body physics, where trial states derived from classical heuristics can be used to guide quantum algorithms. We identify families of physically-motivated guiding states for which the computational hardness of ground-state energy estimation persists in the guided setting. Extending prior results for semi-classical subset states, we prove BQP-hardness for classes including fixed-weight states, matrix product states, Gaussian states, and Fendley states. Our hardness results are obtained via refined Feynman-Kitaev circuit-to-Hamiltonian constructions that explicitly expose the structural role of the guiding state in the reduction. Complementing these results, we give a constructive proof of BQP containment when the guiding state admits a polynomial-size classical description, establishing BQP-completeness for the canonical formulation of the problem. Our results show that quantum advantage persists for the newly introduced state classes, and classical methods also remain viable when said guiding states admit appropriate descriptions. Together, our results identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, within which quantum advantage for ground-state estimation can be meaningfully assessed. We additionally formalise the Guided Fermi-Hubbard Hamiltonian problem and prove BQP-completeness on 2D square and triangular lattices, both with and without magnetic fields, when provided with an appropriate fermionic guiding state.

arXiv:2509.25815•Physical Review A•Jun 8, 2026•6 citations

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States

Chris Cade, Marten Folkertsma, Gharibian, Sevag +4 more

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

arXiv:2207.10097•Leibniz international proceedings in informatics•Jul 20, 2022•19 citations

Monte Carlo simulation of stoquastic Hamiltonians

Sergey B. Bravyi

Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).

arXiv:1402.2295•Quantum Information and Computation•Oct 1, 2015•86 citations

Improved Hardness Results for the Guided Local Hamiltonian Problem

Chris Cade, Marten Folkertsma, Sevag Gharibian +4 more

Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with $6$-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to $1/2$ with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.

arXiv:2207.10250•Jul 21, 2022•36 citations

Complexity Classification of Local Hamiltonian Problems

Toby S. Cubitt, Ashley Montanaro

The calculation of ground-state energies of physical systems can be formalized as the $k$-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set $\mathcal{S}$ and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset $\mathcal{S}$, the problem falls into one of the following categories: in $\mathsf{ P}$; $\mathsf{NP}$-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. The third of these classes has been shown to be $\mathsf{StoqMA}$-complete by Bravyi and Hastings. The characterization holds even if $\mathcal{S}$ does not contain any 1-local terms; for example, we prove for the first time $\mathsf{QMA}$-completeness of the Heisenberg and XY interactions in this setting. If $\mathcal{S}$ is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant $k$, all $k$-local qubit Hamiltonians whose terms are picked from a fixed set $\mathcal{S}$ correspond to problems either in $\mathsf{P}$; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.

arXiv:1311.3161•SIAM Journal on Computing•Jan 1, 2016•129 citations
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.
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.
We study the computational complexity of the Guided Local Hamiltonian problem: given a local Hamiltonian HHH together with a classical description of a guiding state that has non-negligible overlap with the ground state of HHH, estimate the ground-state energy within inverse-polynomial precision. This setting captures real-world scenarios in quantum chemistry and many-body physics, where trial states derived from classical heuristics can be used to guide quantum algorithms. We identify families of physically-motivated guiding states for which the computational hardness of ground-state energy estimation persists in the guided setting. Extending prior results for semi-classical subset states, we prove BQP-hardness for classes including fixed-weight states, matrix product states, Gaussian states, and Fendley states. Our hardness results are obtained via refined Feynman-Kitaev circuit-to-Hamiltonian constructions that explicitly expose the structural role of the guiding state in the reduction. Complementing these results, we give a constructive proof of BQP containment when the guiding state admits a polynomial-size classical description, establishing BQP-completeness for the canonical formulation of the problem. Our results show that quantum advantage persists for the newly introduced state classes, and classical methods also remain viable when said guiding states admit appropriate descriptions. Together, our results identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, within which quantum advantage for ground-state estimation can be meaningfully assessed. We additionally formalise the Guided Fermi-Hubbard Hamiltonian problem and prove BQP-completeness on 2D square and triangular lattices, both with and without magnetic fields, when provided with an appropriate fermionic guiding state.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian HHH with a promise that the ground state of HHH has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 666-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/21/21/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
The calculation of ground-state energies of physical systems can be formalized as the kkk-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S\mathcal{S}S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S\mathcal{S}S, the problem falls into one of the following categories: in P\mathsf{ P}P; NP\mathsf{NP}NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA\mathsf{QMA}QMA-complete. The third of these classes has been shown to be StoqMA\mathsf{StoqMA}StoqMA-complete by Bravyi and Hastings. The characterization holds even if S\mathcal{S}S does not contain any 1-local terms; for example, we prove for the first time QMA\mathsf{QMA}QMA-completeness of the Heisenberg and XY interactions in this setting. If S\mathcal{S}S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant kkk, all kkk-local qubit Hamiltonians whose terms are picked from a fixed set S\mathcal{S}S correspond to problems either in P\mathsf{P}P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA\mathsf{QMA}QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.