OpenFrontiers
Join
← Back to the index
OP-3011OpenQuantum information

Quantum PCP conjecture

For H=m−1∑i=1mhiH=m^{-1}\sum_{i=1}^{m}h_i, with fixed locality and local dimension and 0≤hi≤I0\le h_i\le I, prove or disprove that distinguishing λmin⁡(H)≤a\lambda_{\min}(H)\le a from λmin⁡(H)≥b\lambda_{\min}(H)\ge b is QMA\mathsf{QMA}-hard for some constant promise gap b−a>0b-a>0.

Source-reported statusAs of 2026-09-04Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

For H=m−1∑i=1mhiH=m^{-1}\sum_{i=1}^{m}h_i, with fixed locality and local dimension and 0≤hi≤I0\le h_i\le I, prove or disprove that distinguishing λmin⁡(H)≤a\lambda_{\min}(H)\le a from λmin⁡(H)≥b\lambda_{\min}(H)\ge b is QMA\mathsf{QMA}-hard for some constant promise gap b−a>0b-a>0.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

The normalization makes this a constant energy-density approximation problem, or equivalently a constant extensive error for the unnormalized sum. The local terms have finite efficiently specified descriptions. This is the Hamiltonian formulation of quantum PCP; variants of probabilistically checkable quantum proofs require care about the verifier and reduction model.

What is known: The ordinary local-Hamiltonian promise problem is QMA-complete at inverse-polynomial precision, not for exact real-valued energy output. Anshu–Breuckmann–Nirkhe proved NLTS: there are bounded-locality Hamiltonian families whose sufficiently low-energy states cannot be prepared by constant-depth local circuits. Good quantum codes enable that result, but NLTS is weaker than quantum PCP and does not exclude every succinct classical description of a low-energy state.

Published 2025 work clarifies quantum-PCP definitions. A separate October 2025 preprint develops derandomized tensor-product gap amplification under its stated hypotheses. Neither supplies the complete constant-gap QMA-hardness reduction. Related: A7, A8.

Progress & source assessment

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

published: NLTS is proved; excluding constant-depth circuit preparation is not the full quantum PCP conjecture. Evidence

preprint: Derandomized tensor-product gap amplification advances the amplification toolkit without resolving quantum PCP. Evidence

References
  1. [1]Anshu, Breuckmann & Nirkhe, 'NLTS Hamiltonians from good quantum codes', STOC 2023 link
  2. [2]Buhrman, Helsen & Weggemans, 'Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians', Quantum 9, 1791 (2025) link
  3. [3]'Derandomised tensor product gap amplification for quantum Hamiltonians' (2025 preprint) link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.