# The quantum PCP conjecture

The PCP theorem says that for constraint satisfaction problems it is NP-hard even to approximate the largest number of simultaneously satisfiable constraints, up to an error of a constant fraction of all constraints. The quantum PCP conjecture asks the same of local Hamiltonians, the quantum analogue of constraint systems: is estimating their ground-state energy, up to an error proportional to the number of terms, still as hard as any problem with efficiently checkable quantum proofs?

## Problem

A $k$-local Hamiltonian on $n$ qudits of fixed dimension $q$ is a sum

$$H=\sum_{i=1}^{m}H_i,\qquad 0\preceq H_i\preceq I,$$

of $m=\mathrm{poly}(n)$ terms, each acting on at most $k$ qudits and specified by $\mathrm{poly}(n)$ bits. For thresholds $a<b$, the local Hamiltonian problem asks whether the ground-state energy $\lambda_{\min}(H)$ is at most $a$ or at least $b$, promised that one of the two holds.

$\mathsf{QMA}$ is the class of promise problems where a polynomial-time quantum verifier, given a quantum proof of polynomially many qubits, accepts some proof with probability at least $2/3$ on yes-instances and every proof with probability at most $1/3$ on no-instances.

**Conjecture.** For some constants $k$, $q$ and $0\le\alpha<\beta\le1$, the local Hamiltonian problem with $a=\alpha m$ and $b=\beta m$ is $\mathsf{QMA}$-hard under quantum polynomial-time reductions.

## Background

Kitaev proved in 1999 that the local Hamiltonian problem is $\mathsf{QMA}$-complete when $b-a\ge 1/\mathrm{poly}(n)$, a quantum Cook–Levin theorem [6]. The quantum PCP question was first raised by Aharonov and Naveh in 2002 and formulated precisely by Aharonov, Arad, Landau and Vazirani in 2009 [1, 6]. The form above is Conjecture 1.3 of the survey by Aharonov, Arad and Vidick, which also gives an equivalent form: a verifier that reads only $O(1)$ qubits of the proof [6].

## What is known

- A quantum analogue of gap amplification, the first step of Dinur's proof of the PCP theorem, holds for Hamiltonians whose interaction graph is an expander [1].
- Brandão and Harrow showed that 2-local Hamiltonians of high degree, small expansion or low entanglement have product states of nearly optimal energy, which can be checked in $\mathsf{NP}$; Hamiltonians for a quantum PCP must avoid all three [2].
- If the conjecture holds and $\mathsf{QMA}\ne\mathsf{NP}$, the NLTS conjecture of Freedman and Hastings follows: some local Hamiltonians have no state within $cm$ of the ground energy, for a constant $c>0$, that a constant-depth circuit can prepare [6]. Anshu, Breuckmann and Nirkhe proved NLTS in 2023 using good quantum LDPC codes [3].
- Buhrman, Helsen and Weggemans gave quantum oracles relative to which some quantum PCP statements fail, so, as for the classical PCP theorem, a proof needs (quantumly) non-relativizing techniques. They also showed that a quantum PCP for $\mathsf{QMA}(k)$, for any $k\le\mathrm{poly}(n)$, would give $\mathsf{QMA}(2)=\mathsf{QMA}$ [4].
- Bergamaschi, Metger, Vidick and Zhang gave a derandomized tensor-product gap amplification for Hamiltonians, following Dinur's model with random walks on expander graphs (CCC 2026) [7].
- In October 2026, Bafna, Nguyen and Zhang gave the first template for locality-preserving gap amplification of local Hamiltonians and proved that it amplifies their combinatorial gap (to appear at FOCS 2026) [5].

## What would count as progress

- A proof: a quantum polynomial-time reduction from the inverse-polynomial-gap problem to a constant-relative-gap one. Or a refutation, for example placing the constant-gap problem in $\mathsf{NP}$, which contradicts the conjecture unless $\mathsf{QMA}=\mathsf{NP}$.
- A locality-preserving procedure that amplifies the energy gap of general local Hamiltonians, not only the combinatorial gap of [5].
- Placing the constant-gap problem in $\mathsf{QCMA}$, where proofs are classical; by [4] this would put every quantum PCP with a constant number of queries in $\mathsf{QCMA}$.

## References

1. D. Aharonov, I. Arad, Z. Landau and U. Vazirani, "The detectability lemma and quantum gap amplification", in *Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC)*, 417–426 (2009). [doi:10.1145/1536414.1536472](https://doi.org/10.1145/1536414.1536472)
2. F. G. S. L. Brandão and A. W. Harrow, "Product-state approximations to quantum ground states", in *Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC)*, 871–880 (2013). [doi:10.1145/2488608.2488719](https://doi.org/10.1145/2488608.2488719)
3. A. Anshu, N. P. Breuckmann and C. Nirkhe, "NLTS Hamiltonians from good quantum codes", in *Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC)*, 1090–1096 (2023). [doi:10.1145/3564246.3585114](https://doi.org/10.1145/3564246.3585114)
4. H. Buhrman, J. Helsen and J. Weggemans, "Quantum PCPs: on adaptivity, multiple provers and reductions to local Hamiltonians", *Quantum* 9, 1791 (2025). [doi:10.22331/q-2025-07-11-1791](https://doi.org/10.22331/q-2025-07-11-1791)
5. M. Bafna, Q. T. Nguyen and T. Zhang, "Gap amplification for local Hamiltonians with combinatorial soundness", preprint (2026), to appear at FOCS 2026. [arXiv:2610.04952](https://arxiv.org/abs/2610.04952)
6. D. Aharonov, I. Arad and T. Vidick, "The quantum PCP conjecture", *ACM SIGACT News* 44(2), 47–79 (2013). [doi:10.1145/2491533.2491549](https://doi.org/10.1145/2491533.2491549)
7. T. Bergamaschi, T. Metger, T. Vidick and T. Zhang, "Derandomised tensor product gap amplification for quantum Hamiltonians", in *41st Computational Complexity Conference (CCC 2026)*, LIPIcs, 15 (2026). [doi:10.4230/LIPIcs.CCC.2026.15](https://doi.org/10.4230/LIPIcs.CCC.2026.15)

## Source

Imported from [QIQCOP Zoo op_bca77ec42ddd1d5c](https://qiqc-op.com/problem/op_bca77ec42ddd1d5c/), curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.