Quantum PCP: constant-relative-gap k-local Hamiltonian is QMA-hard (NLTS now proved; qLTCs open)

Necessary conditions. The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (2014), a necessary consequence of qPCP, was proved by Anshu, Breuckmann and Nirkhe (arXiv:2206.13228, 2022; STOC 2023), using the good quantum LDPC codes of Panteleev and Kalachev (arXiv:2111.03654, 2021): there are local Hamiltonians for which every state of energy $\le\varepsilon m$ requires circuits of super-constant depth. NLTS is much weaker than qPCP, since low-energy states may still be efficiently verifiable.

Further evidence and obstructions. Brandão and Harrow (STOC 2013) showed that product states approximate the ground energy of Hamiltonians on dense or high-degree graphs well, so qPCP cannot hold for such instances. Eldar and Harrow (arXiv:1510.02082, FOCS 2017) introduced and proved the weaker NLETS property (no low-error trivial states) for Hamiltonians whose ground states are hard to approximate by shallow circuits. Quantum locally testable codes (qLTCs) are a natural route to qPCP. Cross, He, Natarajan, Szegedy and Zhu (arXiv:2209.11405; Quantum 2024) built qLTCs with constant soundness but weak distance; Dinur, Lin and Vidick (arXiv:2402.07476, 2024) built almost-good qLTCs with constant rate and inverse-polylogarithmic distance and soundness; and Bafna, Li and Nguyen (arXiv:2609.26735, ECCC TR26-204, September 2026, preprint) construct qLTCs with constant rate, distance, soundness and locality assuming a variant of a Reed–Solomon product-expansion conjecture. Even good qLTCs are not known to imply qPCP. Gap-amplification routes in the style of Dinur's classical PCP proof have not been found. As of October 2026 no resolution or credible claim was found, including in the October 2026 OpenAI manuscript list.

A proof would give hardness of approximation for ground-state energies of local Hamiltonians and a quantum analogue of the PCP theorem, with consequences for the entanglement structure of low-energy states (NLTS, already proved, is the first of these). A refutation would yield new constant-factor approximation algorithms for ground energies. There are no near-term applications.

A proof of QMA-hardness of the $k$-local Hamiltonian problem with relative promise gap $\Delta\ge\varepsilon m$ for some constant $k$ and $\varepsilon>0$, or a proof that this promise problem lies in a class below QMA (for example NP or MA), or an unconditional proof that it cannot be QMA-hard under reductions of the standard types. Partial progress: constructing qLTCs with constant rate, distance and soundness.