# P42: Quantum PCP conjecture

- ID: `P42`
- Reference: `quantum-pcp-conjecture`
- Page: https://theoremdb.org/statements/P42
- Record maturity: Reviewed problem with recorded work

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

### Context

The conjecture asks whether quantum ground-state energy remains maximally hard to approximate even at constant precision.

### Problem setup

- **Definition (A k-local Hamiltonian).** A k-local Hamiltonian is a sum of terms, each acting on at most k quantum subsystems.
- **Definition (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.** The conjecture asks whether quantum ground-state energy remains maximally hard to approximate even at constant precision.

### What 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.

## Status

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](#reference-1) [2](#reference-2) [3](#reference-3)

## Work

### Evidence for the current status

**Claim 1 (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.

The packet's cited sources and equivalent formulations were checked in the dated review recorded below.

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.

### Background and intake notes

- 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-22. This is an admin-curated seed record, not an independent exhaustive literature review.
- The Hamiltonian formulation and status were checked against the cited paper on 2026-07-22.
- The games formulation changed after MIP* = RE and must be stated with care. This record uses the standard constant-gap local-Hamiltonian version.

### Open directions

- **Route 1** (reported): 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. [1](#reference-1)

### Computational notes

- Finite Hamiltonian experiments cannot establish a complexity-class hardness theorem.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `quantum-pcp-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://arxiv.org/abs/2403.04841
   - Also cited at Abstract and status discussion
   - Also cited at Editorial research route recorded 2026-07-31
   - preprint; primary source; arXiv:2403.04841, checked 2026-07-31; checked 2026-07-31
   - Source 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.
   - 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.
2. <a id="reference-2"></a>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 https://arxiv.org/abs/1309.7495
   - preprint; primary source; arXiv:1309.7495v1; checked 2026-08-01
   - Source use: original_summary
   - Standard formulation and survey.
3. <a id="reference-3"></a>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 https://arxiv.org/abs/2206.13228
   - preprint; primary source; arXiv:2206.13228v4; checked 2026-08-01
   - Source use: original_summary
   - Proof of the NLTS conjecture.