The quantum PCP conjecture

Unsolved ID op_bca77ec42ddd1d5c Last edited 4 September 2026

Edit

Field: Quantum algorithm
Topics: Hamiltonian complexity
Computational complexity and computability

Problem

Is the constant-relative-gap local Hamiltonian problem QMA-hard? More precisely, do there exist fixed integers \(q,k\geq2\) and constants \(0\leq a<b\leq1\) such that the following promise problem is QMA-hard? An instance consists of \(n\) subsystems of local dimension \(q\) and \(m=\operatorname{poly}(n)\) positive semidefinite terms, each specified with polynomially many bits, for which

\begin{equation} H:=\sum_{i=1}^{m}H_i, \qquad 0\preceq H_i\preceq I, \qquad \lvert\operatorname{supp}(H_i)\rvert\leq k. \tag{1} \end{equation}

Given the Hamiltonian in Eq. (1), distinguish the promised alternatives

\begin{equation} \lambda_{\min}(H)\leq am \qquad\text{and}\qquad \lambda_{\min}(H)\geq bm. \tag{2} \end{equation}

Thus the gap in Eq. (2) is a fixed positive fraction \((b-a)m\) of the number of local terms, independent of \(n\).

Source

Aharonov, Arad, and Vidick give the standard constant-relative-gap local Hamiltonian formulation as Conjecture 1.3 of their quantum-PCP survey [AAV13].

Progress

Aharonov, Arad, and Vidick review the QMA-completeness of local Hamiltonian with an inverse-polynomial promise gap and formulate the constant-gap strengthening in Eq. (2) [AAV13]. Gap amplification methods known for classical constraint systems do not establish the quantum statement.
Anshu, Breuckmann, and Nirkhe construct local Hamiltonians with the no-low-energy-trivial-states property from good quantum LDPC codes [ABN23]. This establishes the required low-energy entanglement phenomenon but does not prove QMA-hardness of the promise problem in Eqs. (1) and (2).
Buhrman, Helsen, and Weggemans prove reductions among several quantum-PCP formulations and oracle separations showing that a proof of constant-gap local-Hamiltonian hardness must use nonrelativizing techniques [BHW25]. Their results restrict possible proofs but neither prove nor refute the conjecture.

Comment

NLTS supplies a central structural prerequisite, and the known reductions clarify which formulations and proof methods are viable, but neither gives the constant-gap QMA-hardness required by Eq. (2). No algorithmic obstruction that would refute that hardness statement is known either.

References

[AAV13]: D. Aharonov, I. Arad, and T. Vidick, “Guest Column: The Quantum PCP Conjecture,” ACM SIGACT News 44(2), 47–79 (2013).DOI arXiv
[ABN23]: 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, 1090–1096 (2023).DOI arXiv
[BHW25]: H. Buhrman, J. Helsen, and J. Weggemans, “Quantum PCPs: On Adaptivity, Multiple Provers and Reductions to Local Hamiltonians,” Quantum 9, 1791 (2025).DOI arXiv

The quantum PCP conjecture

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems