Math Conjectures

Quantum PCP Conjecture

OPENLandmarkConjectureProposed c. 2006 · Standard version

Canonical statement

There exist constants q∈Nq\in\mathbb N and 0≤a<b≤10\leq a<b\leq1 such that the following promise problem is QMAQMA-hard: given an nn-qubit Hamiltonian H=∑i=1mHiH=\sum_{i=1}^{m}H_i, where m=poly⁡(n)m=\operatorname{poly}(n), each HiH_i acts on at most qq qubits and 0⪯Hi⪯I0\preceq H_i\preceq I, distinguish
λmin⁡(H)≤amfromλmin⁡(H)≥bm, \lambda_{\min}(H)\leq am \quad\text{from}\quad \lambda_{\min}(H)\geq bm,
where λmin⁡(H)\lambda_{\min}(H) is the least eigenvalue of HH. Here QMAQMA is bounded-error quantum polynomial-time verification with a polynomial-size quantum witness.
View source LaTeX
There exist constants \(q\in\mathbb N\) and
\(0\leq a<b\leq1\) such that the following promise problem is
\(QMA\)-hard: given an \(n\)-qubit Hamiltonian
\(H=\sum_{i=1}^{m}H_i\), where \(m=\operatorname{poly}(n)\), each
\(H_i\) acts on at most \(q\) qubits and
\(0\preceq H_i\preceq I\), distinguish
\[
  \lambda_{\min}(H)\leq am
  \quad\text{from}\quad
  \lambda_{\min}(H)\geq bm,
\]
where \(\lambda_{\min}(H)\) is the least eigenvalue of \(H\). Here
\(QMA\) is bounded-error quantum polynomial-time verification with a
polynomial-size quantum witness.
TCS-014:[AharonovAradLandauVazirani2009][AharonovEtAl2013QPCP][NatarajanNirkhe2024QPCP]
Theoretical computer scienceMathematical physics

Notes

The quantum PCP conjecture asserts that estimating the ground-state energy of a local Hamiltonian remains QMAQMA-hard even up to constant relative precision: for some constants qq and a<ba<b, given a Hamiltonian that is a sum of mm terms each acting on at most qq qubits, distinguishing minimum eigenvalue at most amam from at least bmbm is QMAQMA-hard. It is the quantum analogue of the classical PCP theorem; the formulation crystallized around 2006 and was set out systematically by Aharonov, Arad and Vidick [AharonovEtAl2013QPCP].

What is known stops well short of the conjecture. The local Hamiltonian problem is QMAQMA-complete when the promise gap is only inverse-polynomial in the system size, and quantum analogues of gap amplification have been developed, beginning with the detectability lemma of Aharonov, Arad, Landau and Vazirani [AharonovAradLandauVazirani2009]. But entanglement and the structure of low-energy states obstruct amplifying to a constant extensive gap; the current state of the art is surveyed by Natarajan and Nirkhe [NatarajanNirkhe2024QPCP].

The conjecture is open: a resolution requires either a gap-amplification argument that survives these quantum obstructions, or a proof that constant-gap instances are genuinely easier.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.