The Quantum PCP Conjecture

The Quantum PCP Conjecture

Definitions and mathematical statement

A $k$-local Hamiltonian on $n$ finite-dimensional sites is $H=\sum_{j=1}^m h_j$, each term acting on at most a constant $k$ sites. Fix a normalization such as $0\le h_j\le I$ and define ground energy $\lambda_{\min}(H)$. The quantum PCP assertion asks for constants $k$ and $0\le a<b\le1$ for which \[ \lambda_{\min}(H)\le am\quad\text{versus}\quad\lambda_{\min}(H)\ge bm \] is QMA-hard, under the standard efficient reductions. The separation $(b-a)m$ is a constant fraction of the number of normalized terms, not an inverse-polynomial absolute gap. The exact Hamiltonian encoding and promise convention are fixed by the cited formulation.

Formulation and concept references: [S1].

Short English statement

Is estimating a normalized local quantum system's energy to constant relative precision already as hard as general quantum-witness verification?

Research attempt

Current frontier.

Literature check: 27 September 2026. The target is the constant-locality, constant normalized energy promise of Aharonov--Arad--Vidick, Section 1.2, Conjecture 1.3. Neither an absolute spectral gap nor a difficult-to-prepare ground state alone supplies the required QMA-hard reduction. [S1]. The NLTS theorem of Anshu--Breuckmann--Nirkhe supplies Hamiltonians whose low-energy states require nonconstant circuit depth, but does not itself prove this Hamiltonian quantum PCP statement. [E1]. A 2025 manuscript by Bergamaschi--Metger--Vidick--Zhang gives derandomized amplification and a locality--gap tradeoff. Its introduction explicitly identifies locality reduction as the missing part of a full PCP route; its streaming construction does not have constant-locality terms. [E2]. These results are kept separate from the construction below.

Attack route.

Duplicating constraints multiplies both energy and term count and therefore does not amplify normalized energy. Applying a nonlinear spectral function can amplify small eigenvalues, but may destroy locality. A third route is to encode into a quantum code and test locally; this additionally needs a soundness theorem that rules out all entangled low-energy cheating states. We investigate the spectral route and try to repair the positivity and noncommutativity problems before confronting locality. No efficient locality-reduction theorem is assumed.

Attempt: positive word amplification without commutativity.

Let $H=\sum_{i=1}^m h_i$, $0\le h_i\le I$, and put $B=H/m$, $C_i=I-h_i$. For a word $w=(i_1,\ldots,i_t)$ define \[ W_w=C_{i_1}\cdots C_{i_t},\qquad g_w=\frac{2I-W_w-W_w^*}{4}. \tag{41.1} \] Each $C_i$ is a contraction, so $\|W_w\|\le1$. For every unit vector $v$, $-1\le\operatorname{Re}\langle v,W_wv\rangle\le1$; therefore $0\le g_w\le I$. Moreover $g_w$ is supported on the union of at most $t$ original supports, hence is at most $kt$-local. This proof does not assert that the product of positive matrices is positive or even Hermitian.

Averaging over all ordered words gives the exact operator identity \[ G_t:=\frac1{m^t}\sum_{w\in[m]^t}g_w =\frac12\left[I-(I-B)^t\right]. \tag{41.2} \] Indeed expansion of $(\sum_i C_i)^t$ includes all ordered products in exactly their original order; commutation is never used. The adjoint sum is identical because reversing words permutes the word set. By the spectral theorem and monotonicity on $[0,1]$, \[ \lambda_{\min}(G_t)=f_t(e),\qquad e=\lambda_{\min}(H)/m,\qquad f_t(u)=\tfrac12[1-(1-u)^t]. \tag{41.3} \] The unnormalized Hamiltonian $\sum_wg_w$ has $m^t$ terms, so $41.3$ really is its energy divided by its term count, as required by the original normalization.

Suppose a hard input family had normalized thresholds $0\le a\le b/100$ and $0<b\le1$. With $t=\lceil1/b\rceil$, \[ f_t(a)\le\frac{ta}{2}\le\frac1{100},\qquad f_t(b)\ge\frac{1-e^{-1}}2. \tag{41.4} \] Here $t\le2/b$, $1-(1-a)^t\le ta$, and $(1-b)^t\le e^{-tb}\le e^{-1}$. Thus the spectral transformation has an absolute normalized separation exceeding $0.30$ in this parameter regime. This is an exact mathematical amplification lemma, not yet an efficient reduction. The small-completeness-energy condition is stated rather than replaced by perfect completeness, which would be an additional assumption on a general QMA verification problem.

For arbitrary $a<b$, the output separation is instead \[ f_t(b)-f_t(a)=\tfrac12[(1-a)^t-(1-b)^t]. \tag{41.5} \] If $a>0$ is fixed this tends to zero as $t\to\infty$. Thus "take a large power" is not by itself a gap-amplification theorem for every promised input. Threshold placement matters.

Attempt: can locality be recovered for free?

We next test the strongest naive hope: perhaps the operator in $41.2$ always admits some other bounded-locality decomposition on the same qubits. This is false, already for commuting one-local terms. Take $n\ge t$ qubits and \[ h_i=|1\rangle\langle1|_i,\qquad B=\frac1n\sum_{i=1}^n h_i. \] On a computational basis vector $x\in\{0,1\}^n$, $G_t$ has diagonal entry $f_t(|x|/n)$. In the unique multilinear polynomial representing this function on the Boolean cube, the coefficient of $x_{i_1}\cdots x_{i_t}$, for distinct indices, is \[ c_t=\frac{(-1)^{t+1}t!}{2n^t}\ne0. \tag{41.6} \] To see this, expand $f_t(u)$ as a degree-$t$ polynomial. Only its leading term can produce a monomial with $t$ distinct indices in $(\sum x_i)^t$; there are $t!$ contributing orders.

The diagonal entries of an operator supported on at most $k$ qubits depend on at most $k$ Boolean coordinates and have multilinear degree at most $k$. A sum of such operators has the same degree bound. Taking $t=k+1$ in $41.6$ therefore proves that no sum of $k$-local operators, positive or otherwise, equals $G_t$ on the same Hilbert space. Off-diagonal entries of a proposed decomposition cannot change this diagonal obstruction.

Equivalently the Pauli coefficient of $Z_{i_1}\cdots Z_{i_t}$ is \[ -\frac{t!}{2^{t+1}n^t}. \tag{41.7} \] Consequently any $k$-local $K$ on the same qubits, for $k<t$, satisfies \[ \|G_t-K\|\ge \frac{t!}{2^{t+1}n^t}. \] This follows from $2^{-n}|\operatorname{Tr}(Z_{i_1}\cdots Z_{i_t}(G_t-K))| \le\|G_t-K\|$. The lower bound is not asserted to stay constant as the parameters grow. It is an obstruction to exact locality recovery, not a theorem ruling out useful approximate gadget constructions with additional qubits.

Stress test: size, locality, and encodings.

There are two independent efficiency failures. When $b$ is inverse polynomial, $t$ is polynomial rather than constant, and $kt$ need not be bounded. Also $m^t$ is generally exponential. A short symbolic expression for $41.2$ is not the polynomial-length list of bounded-locality matrices required by the target. Iterating the full-word construction at constant $t$ does not cure the size problem: after $r$ rounds the number of terms is $m^{t^r}$. This is why the derandomized construction in the recent literature supplies genuine additional work. [E2].

The finite tests accompanying this entry use the noncommuting rational projectors $|0\rangle\langle0|$ and $|+\rangle\langle+|$. They verify $41.2$ exactly for short words and check positivity of every summand. For three commuting one-qubit terms they verify the weight-three coefficient $-1/72$ when $t=n=3$. These are sanity checks of identities already proved above, not hardness experiments.

An ancilla construction could evade $41.6$, because the effective energy on a subspace or after minimizing over extra qubits is not a literal $k$-local operator on the original register. It would, however, need all of the following in one deterministic polynomial-time reduction: constant final locality, a polynomial explicit term list with norms at most one, completeness below a fixed threshold, and soundness above a strictly larger fixed threshold for every enlarged-system state. An error estimate in an unnormalized low-energy effective Hamiltonian is insufficient if dividing by the gadget's total term count erases the gap. No such reduction is proved here.

Finally, QMA-hardness itself is not a separation from BQP. If a separate argument put the promised approximation problem in BQP, quantum PCP would imply QMA$=$BQP rather than a formal contradiction. This is the relevant dependency on UnsolvedMath problem 30006695. Conversely, the NLTS theorem concerns preparation depth and cannot simply be substituted for a decision-class lower bound. [S1], [E1].

Outcome.

Outcome: Exploratory approach with unresolved gap. The positive-word identity provides a fully verified spectral amplification calculation for noncommuting constraints. The Boolean-degree test proves that exact locality recovery on the unchanged register fails even in a simple commuting example. Neither lemma is presented as a new historical result or as quantum PCP. The unresolved step is a polynomial, constant-locality realization with a surviving normalized promise gap; the explicit construction here has neither the necessary term-count bound nor the necessary locality bound.

Sources

• S1 Aharonov, Arad, and Vidick, The Quantum PCP Conjecture, Section 1.2, Conjecture 1.3 $2013$. https://arxiv.org/html/1309.7495v1. Catalogue formulation source.
• S2 Private PCPs from Product Expansion. https://eccc.weizmann.ac.il/report/2026/150/. Catalogue research/status reference; not a proof endorsement.
• E1 Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe, NLTS Hamiltonians from good quantum codes, arXiv:2206.13228, STOC 2023, pp. 1090--1096; main NLTS theorem. https://arxiv.org/abs/2206.13228. Established partial result, not a quantum PCP theorem; consulted 27 September 2026.
• E2 Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang, Derandomised tensor product gap amplification for quantum Hamiltonians, arXiv:2510.01333v1, 1 October 2025. Section 1, Theorems 1.2--1.4, Definition 1.6, and the locality-increase discussion. https://arxiv.org/html/2510.01333v1. Research manuscript; the notebook uses its stated scope and obstructions, not an unverified assertion of quantum PCP. Consulted 27 September 2026.