[#P42] Quantum PCP conjecture
Problem. There exists \(\varepsilon>0\) such that approximating the ground-state energy of a local Hamiltonian to additive error \(\varepsilon\) times the number of local terms is QMA-hard.
1Context
The conjecture asks whether quantum ground-state energy remains maximally hard to approximate even at constant precision.
2Problem setup
Definition 1 (A k-local Hamiltonian). A k-local Hamiltonian is a sum of terms, each acting on at most k quantum subsystems.
Definition 2 (The promise gap gamma). The promise gap gamma is a constant independent of the number of subsystems, and QMA is the quantum analogue of NP with quantum witnesses.
Remark 1. The conjecture asks whether quantum ground-state energy remains maximally hard to approximate even at constant precision.
3What counts as a solution
- Prove QMA-hardness of constant-gap k-local Hamiltonian for fixed constants, or refute the claim through an algorithm or complexity containment incompatible with the conjecture under clearly stated standard assumptions.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: NLTS Hamiltonians exist, proving the required low-energy entanglement phenomenon supplied by good quantum LDPC codes. Exact unresolved remainder: Prove QMA-hardness of approximating bounded-locality Local Hamiltonian ground energy with a constant relative promise gap. NLTS alone does not provide this hardness reduction.[1][2][3]
1Records
Notes and companion material
Original intake status. The cited 2024 paper treats the constant-gap local-Hamiltonian assertion as an open quantum PCP conjecture. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- The games formulation changed after MIP* = RE and must be stated with care. This record uses the standard constant-gap local-Hamiltonian version.
Computational notes
- Finite Hamiltonian experiments cannot establish a complexity-class hardness theorem.
2See also
- Complexity of equality for binary-code weight enumeratorscomputational complexity
- Unique Games conjecturecomputational complexity
- P versus NPcomputational complexity
How to cite
TheoremDB contributors, “Quantum PCP conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/quantum-pcp-conjectureThis page as plain text: quantum-pcp-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from arxiv.org[1], current as of July 31, 2026.
1References
- Packet source. Harry Buhrman, Jonas Helsen, and Jordi Weggemans, “Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians”. Quantum 9, 1791 (2025). DOI 10.22331/q-2025-07-11-1791. arXiv:2403.04841 (2024). Harry Buhrman, Jonas Helsen, and Jordi Weggemans, arXiv:2403.04841, abstract and formulations. ↗preprint · primary source · arXiv:2403.04841, checked 2026-07-31 · checked 2026-07-31Source use: original summary.The cited 2024 paper treats the constant-gap local-Hamiltonian assertion as an open quantum PCP conjecture. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Abstract and status discussion.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Packet-linked current quantum-PCP status source.Source named by the research packet.
- Dorit Aharonov, Itai Arad, and Thomas Vidick, “The Quantum PCP Conjecture”. ACM SIGACT News archive Volume 44 Issue 2, June 2013, Pages 47--79. arXiv:1309.7495 (2013). Problem formulation. ↗preprint · primary source · arXiv:1309.7495v1 · checked 2026-08-01Source use: original summary.Standard formulation and survey.
- Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe, “NLTS Hamiltonians from good quantum codes”. DOI 10.1145/3564246.3585114. arXiv:2206.13228 (2022). Abstract and main theorem. ↗preprint · primary source · arXiv:2206.13228v4 · checked 2026-08-01Source use: original summary.Proof of the NLTS conjecture.
An original CC0 restatement prepared by TheoremDB maintainers.