Theoretical computer science · quantum complexity · local Hamiltonians · quantum information

Quantum PCP Conjecture

Collaboration beta

Does approximating the ground energy of a quantum many-body system remain QMA-hard when both interaction locality and the YES/NO energy gap are fixed constants?

λ_{\min} (H) \leq a versus λ_{\min} (H) \geq b, b - a > 0

Known results and sources

Many bounded local interactions probe one globally entangled state while the fixed-gap hardness endpoint remains open.

Research problem

Exact mathematical statement

For a normalized local Hamiltonian

H=\sum_i w_i h_i,\qquad 0\preceq h_i\preceq I,\qquad w_i\ge 0,\qquad \sum_i w_i=1,

does there exist a universal constant locality $k$ and universal constants $0\le a<b\le 1$ , with $b-a>0$ , such that it is QMA-hard to distinguish normalized $k$ -local Hamiltonians satisfying

\lambda_{\min}(H)\le a

from those satisfying

\lambda_{\min}(H)\ge b?

The conjecture remains open. Results about NLTS, quantum locally testable codes, structured Hamiltonians, and other amplification settings are nearby but do not by themselves prove this exact constant-locality, constant-additive-gap hardness statement.

Problem infographic

Problem at a glance

Scientific explainer for the Quantum PCP Conjecture showing a normalized local Hamiltonian, its ground-energy YES and NO thresholds, the shrinking promise gap of standard Local Hamiltonian, amplification with growing locality, and the open constant-locality constant-gap QMA-hardness target. — Quantum PCP asks for QMA-hardness with both constant interaction locality and a fixed additive energy gap; known neighboring advances do not yet establish that endpoint.

Current mathematical picture

Where work on Quantum PCP Conjecture stands

Open conjecture

The current research follows the normalized Quantum PCP formulation, two unverified structured-input and amplification interfaces, the conditional exponent-budget reduction, packet-supplied arguments for common CSS decoding, nearest-sector synchronization, causal source cover, influence-weighted soundness, abrupt-cut resistance, private-proof cleaning, and correctable-sector composition, and the current low-influence branch-switch design target. It also records construction-specific barriers, discarded routes, reported but unreproduced finite checks, and eight concrete work orders. The central shared-state transfer, low-congestion repair, common good/bad sector theorem, coherent completeness, external interfaces, and full recursion remain open. These mathematical assertions are source-reported, not independently established results.

Strongest supported footholdSeveral soundness and consistency modules are isolated

The current work supplies arguments for a common CSS decoder, nearest-sector synchronization, abrupt-cut resistance, causal source cover, influence-weighted arbitrary-state soundness, and correctable-sector min-scale composition.

Evidence posture · Reported result

Leading routeLow-influence correctable-sector branch switch

The active mainline combines one global encoded witness, term-local checked histories, low-congestion causal repair, one common sector decoder, a square-root-scale bad-sector penalty, and coherent completeness. None of the load-bearing construction obligations is yet completed.

Route status · Active route

Useful failureStatic encoded private-proof route

The source closes the static below-distance encoded-proof route through the private-proof cleaning theorem. A revival must explicitly leave the static code subspace or escape the data-support hypothesis.

Route status · Eliminated route

Main reductionConditional exponent budget isolates the quantitative threshold

The current work derives the sufficient reset condition L(K)/delta(K) <= K^(1-eta), equivalently alpha+beta<1 for power-law locality and energy retention, subject to all closure and completeness hypotheses.

Evidence posture · Reported reduction

Completed special caseGeneralized Bacon–Shor conflict-volume barrier

In the current work's generalized Bacon–Shor conflict-cell construction, N_C >= Kd, so the subsystem distance divided by materialized conflict volume is at most 1/K. This blocks a distance-over-volume proof for that construction but is not a universal subsystem-code no-go.

Evidence posture · Source-reported route statement

Priority open bridgeProve one common good/bad sector theorem

Choose a sector algebra in which both basis verifiers use one correction in each good sector and every bad sector pays consistency energy at least K^(-1/2-o(1)).

Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Quantum PCP Conjecture in numbers

1.7kretained lines of mathematical investigation1,702 in the current working snapshot

Argument development: 1,396 · 82%
Explored or eliminated routes: 29 · 2%
Computational analysis: 72 · 4%
Open obligations: 82 · 5%
Definitions and setup: 123 · 7%

15selected mapped statements5routes investigated6reported milestones7open questions6contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byDorit Aharonov, Tomer NavehProposed2002Status checkedAug 6, 2026

Source recordedAug 6, 2026

Recommended next task

Prove one common good/bad sector theorem

Choose a sector algebra in which both basis verifiers use one correction in each good sector and every bad sector pays consistency energy at least K^(-1/2-o(1)).

Suggested move: Define the sector projectors and one correction map per good sector, then prove the bad-sector spectral lower bound.

What would count as progress

one common block decomposition
same logical correction for Z and X readouts in every good sector
bad-sector penalty at the target scale

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

25 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeLow-influence correctable-sector branch switch

Route status · Active route

Active routeCommon-decoder causal soundness modules

The current work supplies source-asserted common CSS decoding, nearest-sector synchronization, causal source cover, influence weighting, abrupt-cut resistance, and min-scale sector composition. Their use in the mainline remains conditional on one concrete shared construction.

Route status · Active route

Explored alternatives

Other routes

3 recorded

Eliminated routeStatic encoded private-proof route

Route status · Eliminated route

Narrowed routeGeneralized Bacon–Shor conflict cells

The exact affine-view construction remains useful as a structural model, but literal conflict-cell materialization reaches only the 1/K distance-over-volume boundary. Compressed dynamic or collective encodings remain open.

Route status · Narrowed route

Narrowed routeCoded-parity amplification before locality reset

The current work derives a structured constant-gap amplifier with two commuting high-weight layers, but its output still requires a verified locality reset and closure under recursive use.

Route status · Narrowed route

Route statements and reductions

Statements the next route can inspect and build on

Route statementCommon CSS decoder for complementary basis layers

Under the stated CSS assumptions, one fixed recovery channel sends logical Z-diagonal and X-diagonal observables to the corresponding physical diagonal algebras. Its two classical readouts are shadows of the same decoder, and pointwise verifier inequalities lift to arbitrary coherent states.

Source-reported route statement

Route statementNearest-sector synchronization

For logical sectors separated by distance d and a deterministic nearest-sector decoder D, the distance from any point y to the union of accepting sectors is at least (d/2) times the rejection predicate B(D(y)); the factor one-half is sharp.

Source-reported route statement

Route statementParallel encoded-cut resistance

Across one parallel reversible layer of gates of width at most q, splicing the encoded input from one codeword to the output computed from a different distance-d codeword violates at least ceil(d/q) local gate checks.

Source-reported route statement

Route statementCausal source-cover inequality

For a deterministic acyclic basis-classical computation, each disagreement in a rejection record traces backward to a repaired input or violated gate. This yields a pointwise rejection certificate after explicit repair charges are supplied.

Source-reported route statement

Route statementInfluence-weighted overlap soundness

Given the pointwise causal certificates, weighting each term by w_j/d_j yields verifier soundness 1/Xi_W, where Xi_W is the weighted causal-influence mass. The number and overlap pattern of input terms introduce no separate factor, and the basiswise inequality lifts through the common decoder to arbitrary coherent states.

Source-reported route statement

Route statementCorrectable-sector min-scale composition

When the consistency and verifier Hamiltonians share one block decomposition, good sectors have one decoder with verifier scale mu, and bad sectors pay consistency scale Delta, their normalized mixture retains at least half the smaller of mu and Delta rather than multiplying the scales.

Source-reported route statement

Route statementLow-influence correctable-sector branch-switch target

The current design target asks for a polynomial-time constant-local, constant-color branch/history Hamiltonian built from one shared encoded witness, one common sector correction, good-sector causal influence Xi_Z,Xi_X <= K^(1/2+o(1)), bad-sector penalty at least K^(-1/2-o(1)), coherent completeness, and polynomial recursive costs.

Source-reported route statement · dependencies incomplete

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

7 featured tasks

Prove one common good/bad sector theorem

Choose a sector algebra in which both basis verifiers use one correction in each good sector and every bad sector pays consistency energy at least K^(-1/2-o(1)).

Suggested move: Define the sector projectors and one correction map per good sector, then prove the bad-sector spectral lower bound.

Ready to work on

Prove the low-influence causal certificate

For the concrete deterministic basis computation, construct input-repair coefficients and prove Xi_Z,Xi_X <= K^(1/2+o(1)) with a matching adversarial stress test.

Suggested move: List every source and future record cone, construct u_jq, and compute Xi before claiming soundness.

Ready to work on

Construct coherent two-basis completeness

Build one honest branch history for every logical witness, show where it leaves the static code subspace and how it coherently decodes back, and compute every energy contribution with negligible total excess.

Suggested move: Construct completeness in parallel with the branch Hamiltonian rather than after soundness is fixed.

Ready to work on

Specify one concrete branch-switch Hamiltonian

Give exact registers, local terms, coefficients, commuting colors, transfer and propagation checks, and total normalization for H_con, C_Z, and C_X.

Suggested move: Write one formula-level candidate before further asymptotic soundness claims.

Ready to work on

Solve shared-state transfer

Load each term's relevant K logical degrees from one global encoded witness into protected term-local work histories with bounded degree and repair cost depending on K rather than the full witness length n.

Suggested move: Construct a bounded-degree transfer mechanism and attack it with independent-copy, transparent-fanout, and global-length-leak counterexamples.

Ready to work on

Verify the exact structured amplification interface

Bind primary-source theorems for the negligible-YES/inverse-polynomial-NO input, commuting or two-basis layers, amplification locality and completeness costs, and closure under re-amplification.

Suggested move: Open the primary sources, state exact theorem numbers and hypotheses, and translate every normalization, locality, completeness, and family-closure condition into the current work's convention.

Ready to work on

Complete normalization, recursion, and adversarial audit

After the construction is concrete, optimize the mixing weight and recompute size, locality, colors, precision, YES loss, NO retention, future amplification cost, and all eighteen adversarial tests.

Suggested move: Wait for a formula-level construction and concrete mu, Delta, and error terms, then execute the full normalization and attack suite.

Blocked by the current route

Sourced mathematical context

The known mathematical landscape

Context collected Aug 6, 2026

Current statusOpen conjecture

The Hamiltonian Quantum PCP Conjecture remains open: no cited result proves or disproves that normalized constant-locality Local Hamiltonian is QMA-hard to approximate across a fixed constant additive gap. NLTS has been proved, quantum locally testable codes and structured Hamiltonian footholds have advanced, and new gap-amplification primitives have appeared, but none supplies the full hardness-preserving constant-locality amplification. Games-PCP and MIP*=RE results remain mathematically distinct from this statement.

[3][8][10]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026-07-23
Authoritative summaryA Simons Institute talk by Quynh T. Nguyen reported a fault-tolerant template for locality-preserving amplification and a proof of combinatorial-gap amplification. No matching archival paper was verified in this collection, and combinatorial soundness is not recorded as normalized energy-gap amplification.[12]
2026
Peer reviewedMa and Natarajan proved a two-basis Quantum-6-Sat problem complete for a gate-set-qualified QMA1 class at inverse-polynomial promise gap. The structured X/Z form is a useful hardness foothold, but neither the class nor the gap is the standard Quantum PCP endpoint.[14]
2025
PreprintBergamaschi, Metger, Vidick, and Zhang introduced derandomised tensor-product gap amplification for quantum Hamiltonians using expander walks. It is a new amplification primitive, but the preprint does not claim a full constant-locality Quantum PCP reduction.[11]
2025
Peer reviewedBuhrman, Helsen, and Weggemans clarified adaptive, non-adaptive, and multiprover quantum-PCP definitions, gave a detailed reduction from quantum proof verification to constant-gap local Hamiltonians, and proved oracle and complexity consequences. These structural results do not establish existence of a Quantum PCP for QMA.[10]

Mathematical neighborhood

Related results and reusable starting points

Current focusQuantum PCP Conjecture

Weaker or relaxed forminverse-polynomial-gap Local Hamiltonian

Ordinary constant-locality Local Hamiltonian is QMA-complete with inverse-polynomial promise gap. Quantum PCP strengthens the precision regime to a constant fraction after normalization; locality alone is already known.

[4][3]

Equivalent formulationconstant-query quantum proof verification

A constant-query quantum proof-verification formulation can be related to constant-gap Local Hamiltonian through quantum reductions. The exact direction and reduction model matter, so this equivalence does not identify classical, multiprover, or games PCP variants automatically.

[3][10]

Dependency or reductionquantum gap amplification

Locality-controlled gap amplification is a central proposed proof route. Existing results amplify under restrictions, derandomise tensor-product amplification, or amplify combinatorial soundness; none of the cited sources supplies the complete constant-locality energy-gap transformation.

[2][11]

Weaker or relaxed formNo Low-Energy Trivial States theorem

NLTS asks for local Hamiltonians whose low-energy states cannot be prepared by shallow circuits. It is a necessary structural consequence expected from Quantum PCP and is now a theorem, but it does not encode QMA-hardness.

[5][6]

Related problemquantum locally testable codes

Quantum locally testable codes connect local energy penalties to distance from a code space and motivate robust Hamiltonian constructions. Current parameter tradeoffs and code constructions do not by themselves prove hardness of approximation.

[7][19]

Related problemquantum games PCP and MIP*

Entangled-prover nonlocal games have a radically different unrestricted complexity landscape, including MIP*=RE. The games-PCP route for QMA requires efficient-prover restrictions and is not presently equivalent to Hamiltonian Quantum PCP.

[8][9]

Related problemquasi-quantum Local Hamiltonian toy model

The quasi-quantum-state Local Hamiltonian model is an NP-complete classical toy model designed to preserve selected quantum-like obstacles. Its own constant-relative-gap analogue remains open and it is not a restriction or proof of the quantum conjecture.

[13]

Weaker or relaxed formtwo-basis Quantum-6-Sat

Two-basis Quantum-6-Sat provides structured QMA1 hardness with an inverse-polynomial gap. It aligns with CSS-inspired approaches but does not establish QMA-hard constant-gap approximation.

[14]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal library support · partial resource linkedQuantum for Lean 4
A current Lean package formalizes general quantum information and quantum computation foundations. The package page does not claim formal definitions of QMA, Local Hamiltonian promise problems, hardness reductions, or the Quantum PCP conjecture.
[15]
formal library support · partial resource linkedLean-QIT
Lean-QIT provides kernel-checked finite-dimensional quantum states, channels, codes, and information-theoretic capacity theorems. It is reusable infrastructure rather than a formal statement or proof of Quantum PCP.
[16]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA checked finite-dimensional definition of weighted k-local Hamiltonians, operator bounds, ground energy, and the normalized constant promise gap used by the conjecture.
Formalization targetFormal promise-problem, polynomial-time quantum reduction, QMA verifier, and QMA-hardness infrastructure with explicit encoding and numerical-precision conventions.
Formalization targetMachine-checked circuit-to-Hamiltonian and gap-amplification statements whose normalization, locality, qudit dimension, size, completeness, and soundness parameters compose exactly.
Formalization targetFormal quantum coding infrastructure for CSS or subsystem codes, local testability, recovery maps, and the low-energy sector arguments used by current research routes.
Formalization targetA reviewed statement-alignment theorem connecting any constant-query verifier, games, or structured two-basis variant to the exact Hamiltonian Quantum PCP formulation.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

6 mapped milestonesretained argument map

Browse all 6 mapped stages

stage 1Normalized conjecture and external interfaces separated
stage 2Conditional exponent budget isolates the threshold
stage 3Soundness and consistency modules isolated
stage 4Static and conflict-volume routes narrowed
stage 5Low-influence branch switch becomes the mainline
stage 6Work orders and adversarial checks are specified

Normalized conjecture and external interfaces separatedThe source fixes the Quantum PCP promise problem and separates it from the structured-input and amplification hypotheses used by this program.