# Hamiltonian complexity
**Hamiltonian complexity** is the field of theoretical computer science and quantum many-body physics that studies the computational complexity of problems posed in terms of quantum Hamiltonians, above all the problem of estimating the ground-state energy of a local Hamiltonian. Its landmark result is the QMA-completeness of the local Hamiltonian problem, the quantum analog of the Cook-Levin theorem for Boolean satisfiability[1](https://arxiv.org/abs/1401.3916) • [2](https://arxiv.org/pdf/2407.15499).
| Key fact | Detail |
|---|---|
| Central problem | Given a k-local Hamiltonian, decide whether its ground-state energy lies below one threshold or above another separated by a promise gap[3](https://citeseerx.ist.psu.edu/document?doi=e66c2488db9cd957691e0f2e04f7673ba7fa88bb&repid=rep1&type=pdf) |
| Founding result | Alexei Kitaev proved in 1999 that k-local Hamiltonian is in QMA for k ≥ 1 and QMA-hard for k ≥ 5, the "quantum Cook-Levin theorem"[1](https://arxiv.org/abs/1401.3916) |
| Locality thresholds | 3-local was shown QMA-complete by Kempe and Regev; 2-local by Kempe, Kitaev, and Regev (SIAM Journal on Computing, 2004); 1-local is in P[4](https://arxiv.org/abs/quant-ph/0406180) |
| Classical analog | The problem is similar in spirit to MAX-k-SAT, which is NP-complete for k ≥ 2[4](https://arxiv.org/abs/quant-ph/0406180) |
| Stoquastic case | Stoquastic local Hamiltonian is StoqMA-complete, a class between AM and MA; stoquastic k-SAT is MA-complete[5](https://arxiv.org/abs/quant-ph/0606140) • [6](https://arxiv.org/abs/0806.1746) |
| Open frontier | The quantum PCP conjecture, whether constant-factor approximations to the ground energy remain QMA-hard, is unresolved[7](https://arxiv.org/abs/1309.7495) |
| Related theorem | The NLTS conjecture of Freedman and Hastings was proved in 2022 using constant-rate, linear-distance quantum LDPC codes[8](https://arxiv.org/abs/2206.13228) |
## The local Hamiltonian problem
A Hamiltonian is the operator that generates time evolution in quantum mechanics; its smallest eigenvalue, the ground-state energy, determines the low-temperature behavior of the physical system it describes. A Hamiltonian on n qubits is k-local if it is a sum of terms, each acting nontrivially on at most k qubits. The k-local Hamiltonian problem asks, given such a description and two thresholds a and b at least a constant apart, whether the ground-state energy is at most a or at least b[3](https://citeseerx.ist.psu.edu/document?doi=e66c2488db9cd957691e0f2e04f7673ba7fa88bb&repid=rep1&type=pdf).
The problem is the quantum generalization of constraint satisfaction. Each classical clause of MAX-k-SAT can be represented by a diagonal Hamiltonian that penalizes assignments violating the clause by raising their eigenvalue, so the lowest eigenvalue of the sum corresponds to the maximum number of clauses satisfiable simultaneously; this embedding shows 2-local Hamiltonian is NP-hard[3](https://citeseerx.ist.psu.edu/document?doi=e66c2488db9cd957691e0f2e04f7673ba7fa88bb&repid=rep1&type=pdf). The quantum version is harder to verify because a satisfying assignment is replaced by a quantum state, an entangled object that a classical verifier cannot inspect term by term. The class capturing this power is QMA, the quantum analog of NP, in which a quantum verifier checks a polynomial-size quantum witness[1](https://arxiv.org/abs/1401.3916).
## The quantum Cook-Levin theorem and locality thresholds
In 1999 [Alexei Kitaev](https://www.edgepedia.org/alexei-kitaev), building on Richard Feynman's idea of encoding a quantum computation in the evolution of a fixed Hamiltonian, defined the local Hamiltonian problem and proved it QMA-complete for k ≥ 5[1](https://arxiv.org/abs/1401.3916) • [9](https://windowsontheory.org/2018/12/20/quantum-hamiltonian-complexity/). The proof combines the ideas behind the classical Cook-Levin theorem with Feynman's circuit-to-Hamiltonian construction: the ground space encodes a uniform superposition over snapshots of the verifier's computation, the so-called history state, with propagation terms penalizing states in which the circuit does not evolve correctly[1](https://arxiv.org/abs/1401.3916).
**Locality was then pushed down.** Kempe and Regev showed 3-local Hamiltonian is QMA-complete, and Kempe, Kitaev, and Regev settled the long-outstanding case of 2-local Hamiltonian in 2004, giving two independent proofs, one using only elementary linear algebra and one based on a perturbation-theoretic technique for analyzing sums of two Hamiltonians[4](https://arxiv.org/abs/quant-ph/0406180). At the other end, 1-local Hamiltonian is in P, since each term can be optimized independently[4](https://arxiv.org/abs/quant-ph/0406180). The same paper showed that adiabatic computation with two-local interactions on qubits is equivalent in power to standard quantum computation[4](https://arxiv.org/abs/quant-ph/0406180).
A closely related problem is Quantum k-SAT, which asks whether a set of k-local projectors has a common zero-eigenvector, that is, a frustration-free ground state. It is in P for k = 2 and QMA1-complete, QMA with perfect completeness, for k ≥ 3[10](https://www.cs.umd.edu/~amchilds/talks/simons15.pdf).
## Geometric restrictions
From a physicist's perspective, the Hamiltonians produced in the QMA-hardness reductions above are arguably not physical, that is, not of the kind occurring in nature. A line of work therefore re-proved hardness under geometric constraints. Oliveira and Terhal showed that 2-local Hamiltonian with nearest-neighbor interactions on a two-dimensional grid is still QMA-complete[1](https://arxiv.org/abs/1401.3916).
**One dimension is enough.** In stark contrast to the classical case, where MAX-2-CSP on a line is in P, Aharonov, Gottesman, Irani, and Kempe showed that 2-local Hamiltonian with nearest-neighbor interactions on a line is QMA-complete when the local systems have dimension at least 12; this threshold was improved to 11 and subsequently to 8[1](https://arxiv.org/abs/1401.3916). Gottesman and Irani obtained related results for translationally invariant one-dimensional systems[1](https://arxiv.org/abs/1401.3916). Cubitt and Montanaro later gave a quantum generalization of Schaefer's Dichotomy Theorem for 2-local Hamiltonian, classifying interaction types by complexity[1](https://arxiv.org/abs/1401.3916).
## Stoquastic Hamiltonians and the sign problem
A Hamiltonian is **stoquastic** if all off-diagonal matrix elements in the standard basis are real and non-positive, the condition under which the Perron-Frobenius theorem applies; an equivalent characterization is that the Gibbs density matrix is entry-wise non-negative at any temperature. Such Hamiltonians, which are common in the natural world, avoid the sign problem that obstructs quantum [Monte Carlo](https://www.edgepedia.org/monte-carlo) simulation[5](https://arxiv.org/abs/quant-ph/0606140).
Stoquasticity lowers the complexity. Bravyi, DiVincenzo, Oliveira, and Terhal proved that the stoquastic local Hamiltonian problem belongs to AM, a probabilistic version of NP with two rounds of communication between prover and verifier, and that 2-local stoquastic LH-MIN is hard for MA; with the additional promise of a polynomial spectral gap the problem lies in PostBPP, a generalization of BPP allowing post-selection, which also places any adiabatic computation using stoquastic Hamiltonians in PostBPP[5](https://arxiv.org/abs/quant-ph/0606140). The two-local stoquastic Hamiltonian problem is complete for StoqMA, a class intermediate between AM and MA that sits strictly inside QMA in the expected classification[11](https://pmc.ncbi.nlm.nih.gov/articles/PMC7428338/).
Bravyi and Terhal generalized the Cook-Levin theorem to MA by defining stoquastic k-SAT: stoquastic k-SAT is in MA for any constant k, and any promise problem in MA reduces to stoquastic 6-SAT, giving the first nontrivial example of an MA-complete promise problem. They also identified stoquastic frustration-free local Hamiltonians, where the ground state of the full Hamiltonian is a ground state of every term, as a class whose adiabatic evolution can be efficiently simulated on a classical probabilistic computer[6](https://arxiv.org/abs/0806.1746). Hardness persists under geometric constraints: the 2-local stoquastic Hamiltonian problem on a two-dimensional square qubit lattice is StoqMA-complete, shown by Waite and Bremner using stoquastic-preserving perturbative gadgets that reduce locality and planarize interaction graphs without increasing particle dimension[12](https://quantum-journal.org/papers/q-2026-05-06-2097/). Related work shows that geometrically local stoquastic Hamiltonians in one and two dimensions remain MA-hard with sufficiently large qudit dimension[2](https://arxiv.org/pdf/2407.15499).
## The quantum PCP conjecture
The classical [PCP theorem](https://www.edgepedia.org/pcp-theorem) states that local constraint satisfaction problems exhibit hardness of approximation: deciding whether all constraints can be satisfied or at most a constant fraction below that is NP-hard. The quantum PCP conjecture asks whether the analogous statement holds for local Hamiltonians, that is, whether approximating the ground-state energy to within a constant fraction of the Hamiltonian's norm remains QMA-hard, even though the inverse-polynomial-gap version is QMA-complete[7](https://arxiv.org/abs/1309.7495) • [13](https://www.weizmann.ac.il/math/vidick/research-activities/hamiltonian-complexity). The conjecture remains open[7](https://arxiv.org/abs/1309.7495).
**NLTS was the main obstacle, and it fell.** The No Low-Energy Trivial States conjecture of Freedman and Hastings (2014) posits the existence of local Hamiltonian families for which every low-energy state has nontrivial quantum circuit complexity; it identifies a fundamental obstacle to resolving the quantum PCP conjecture, since a quantum PCP theorem would imply it. Anshu, Breuckmann, and Nirkhe proved the conjecture in 2022 by showing that recently discovered families of constant-rate and linear-distance quantum LDPC codes correspond to NLTS local Hamiltonians[8](https://arxiv.org/abs/2206.13228). Earlier partial results included the NLETS theorem of Eldar and Harrow and combinatorial versions proved against states violating a constant fraction of local terms[14](https://arxiv.org/abs/2206.02741).
## Why the field matters
Hamiltonian complexity connects two questions that look separate: how hard is it to predict the behavior of quantum matter, and what can be efficiently verified quantumly. The QMA-completeness of the local Hamiltonian problem implies that no efficient algorithm, classical or quantum, is expected to approximate ground-state energies of general local Hamiltonians to inverse-polynomial precision, which bounds what methods such as density functional theory or generic variational approaches can achieve in the worst case[1](https://arxiv.org/abs/1401.3916). At the same time, the classification of restricted families, such as stoquastic, frustration-free, commuting, or geometrically local Hamiltonians, maps out exactly where classical simulation techniques like quantum Monte Carlo retain their power and where they fail[5](https://arxiv.org/abs/quant-ph/0606140) • [11](https://pmc.ncbi.nlm.nih.gov/articles/PMC7428338/).
## References
1. [Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin (2014). Quantum Hamiltonian Complexity. arXiv:1401.3916; Foundations and Trends in Theoretical Computer Science 10, 159–282 (2015).](https://arxiv.org/abs/1401.3916)
2. [Asad Raza, Jens Eisert, Alex B. Grilo (2024). Complexity of geometrically local stoquastic Hamiltonians. arXiv:2407.15499.](https://arxiv.org/pdf/2407.15499)
3. [Julia Kempe, Alexei Kitaev, Oded Regev. The Complexity of the Local Hamiltonian Problem (full text, CiteSeerX).](https://citeseerx.ist.psu.edu/document?doi=e66c2488db9cd957691e0f2e04f7673ba7fa88bb&repid=rep1&type=pdf)
4. [Julia Kempe, Alexei Kitaev, Oded Regev (2004). The Complexity of the Local Hamiltonian Problem. arXiv:quant-ph/0406180; SIAM Journal on Computing 35(5), 1070–1097 (2006).](https://arxiv.org/abs/quant-ph/0406180)
5. [Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, Barbara M. Terhal (2006). The Complexity of Stoquastic Local Hamiltonian Problems. arXiv:quant-ph/0606140; Quantum Information and Computation 8, 361–385 (2008).](https://arxiv.org/abs/quant-ph/0606140)
6. [Sergey Bravyi, Barbara Terhal (2008). Complexity of stoquastic frustration-free Hamiltonians. arXiv:0806.1746; SIAM Journal on Computing.](https://arxiv.org/abs/0806.1746)
7. [Dorit Aharonov, Itai Arad, Thomas Vidick (2013). The Quantum PCP Conjecture. arXiv:1309.7495; ACM SIGACT News 44(2), 47–79.](https://arxiv.org/abs/1309.7495)
8. [Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe (2022). NLTS Hamiltonians from good quantum codes. arXiv:2206.13228; STOC 2023.](https://arxiv.org/abs/2206.13228)
9. [Sevag Gharibian (2018). What is Quantum Hamiltonian Complexity? Windows on Theory.](https://windowsontheory.org/2018/12/20/quantum-hamiltonian-complexity/)
10. [Andrew Childs (2015). Complexity of ground energy problems (talk slides), Simons Institute.](https://www.cs.umd.edu/~amchilds/talks/simons15.pdf)
11. [Easing the Monte Carlo sign problem. PMC (Science Advances).](https://pmc.ncbi.nlm.nih.gov/articles/PMC7428338/)
12. [Gabriel Waite, Michael J. Bremner (2026). The Complexity of Local Stoquastic Hamiltonians on 2D Lattices. Quantum 10, 2097.](https://quantum-journal.org/papers/q-2026-05-06-2097/)
13. [Thomas Vidick. Hamiltonian Complexity, research overview, Weizmann Institute of Science.](https://www.weizmann.ac.il/math/vidick/research-activities/hamiltonian-complexity)
14. [Anurag Anshu, Nikolas P. Breuckmann (2022). A construction of Combinatorial NLTS. arXiv:2206.02741.](https://arxiv.org/abs/2206.02741)
---
*Topic: Encyclopedia › Physical world and mathematics › Physics › Quantum physics › Quantum information science › Quantum computing and algorithms › Quantum complexity theory › Hamiltonian complexity and quantum PCP*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 11, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license