Quantum PCP conjecture

Imagine two quantum components whose measurements give 0 or 1. A toy interaction assigns zero energy to matching outcomes and one unit to different outcomes. With many components, overlapping interactions contribute to the total energy, and their preferences can conflict. Can deciding the smallest attainable energy remain as hard as general tasks whose proposed answers a fast quantum computer can check, even with a coarse energy tolerance? To compare sizes, give every interaction the same upper energy bound and divide energy by the number of interactions; the allowed tolerance on this scale stays fixed as the system grows.[1]

Can the lowest possible energy of interacting quantum components remain computationally hard to estimate with a fixed coarse tolerance on a scale normalized for system size? The Hamiltonian is the operator assigning energy to a quantum state. Write $H=\sum_{i=1}^{m}h_i$, with each interaction acting on at most a fixed number $k$ of components, each of fixed local dimension. Shifting and rescaling bounded interactions gives the convention $0\le h_i\le I$. A state's expected energy is $\langle\psi|H|\psi\rangle$; minimizing over normalized states gives the ground energy $E_0(H)$. Divide by $m$ for normalized energy. QMA contains decision tasks whose yes answers have polynomial-size quantum-state evidence accepted by a polynomial-time quantum verifier, while all evidence for no answers is rejected with high probability. The conjecture predicts fixed $k$ and $\varepsilon>0$ for which distinguishing promised cases $E_0(H)/m\le a$ and $E_0(H)/m\ge b$, with $b-a\ge\varepsilon$, is QMA-hard: every QMA task reduces to it. The cited survey permits quantum polynomial-time reductions.[1]

The matching-pair example is easy and does not demonstrate hardness. The established general hardness result requires a tolerance that shrinks as the system grows. Proving the same kind of hardness with a fixed normalized tolerance is the missing step; results for selected interactions or narrower amplification tasks do not supply it.[1] [2]

Known QMA-completeness for an inverse-polynomial promise gap does not yield this constant relative gap. The July 2026 talk describes amplification of a combinatorial gap while controlling how many components each interaction touches; its abstract retains the Hamiltonian conjecture as open. The separate NLTS theorem supplies families with robust circuit-depth lower bounds for low-energy states. Neither this preparation barrier nor a result about quantum games automatically proves constant-gap hardness for estimating the ground energy here.[1] [2] [3]

Lowest-energy states help explain how interacting quantum systems organize. Quantum entanglement can make the state of the whole matter in ways that independent descriptions of its parts miss. The conjecture investigates whether coarse energy questions still require accounting for these collective relationships, placing limits on broadly applicable simplifications. It concerns worst-case systems, rather than predicting that every material is hard to study.[1]

Consider two components with measurement labels 0 and 1: 00 means both are 0, and 11 means both are 1. An interaction favouring their equal-amplitude coherent quantum combination has $H=I-|\Phi^+\rangle\langle\Phi^+|$, with $|\Phi^+\rangle=(|00\rangle+|11\rangle)/\sqrt2$. This joint state has zero energy, but 00 and the classical half-and-half mixture of 00 and 11 each have expected energy $1/2$. The larger issue is whether useful descriptions stay simple after allowing a nonzero energy density above the minimum. The proved NLTS construction uses local checks of quantum codes to require circuit depth growing with system size for every sufficiently low-energy state. A depth bound measures the number of layers of bounded-size gates, and may still permit efficient preparation. Distinguishing that structural obstruction from QMA-hard energy estimation links quantum information storage, state preparation and approximation algorithms without equating them.[1] [3]