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

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

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

2Definitions

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.

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

Saved packet · July 31, 2026

What counts as a solution

Saved packet 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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 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] Relevance to this problem For Quantum PCP conjecture, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3 Details 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. Open full record →
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.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 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] Relevance to this problem For Quantum PCP conjecture, record quantum-pcp-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: 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. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. 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. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

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
Winner complexity of Node Kayles on subcubic treescomputational complexity
P versus NPcomputational complexity

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Quantum PCP conjecture.” TheoremDB. P42. Problem statement; statement text SHA-256 0851cf5bbfd3bd0d9d5c4b38ef575cd738adc371db51724316a6e58f4c7cadf8. https://theoremdb.org/statement/?ref=P42

BibTeX

@misc{theoremdb-problem-0851cf5bbfd3bd0d9d5c4b38ef575cd738adc371db51724316a6e58f4c7cadf8,
  title = {{Quantum PCP conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 0851cf5bbfd3bd0d9d5c4b38ef575cd738adc371db51724316a6e58f4c7cadf8},
  url = {https://theoremdb.org/statement/?ref=P42}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from arxiv.org^[1], current as of July 31, 2026.

1Lean verification

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.

[#P42] Quantum PCP conjecture

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance