The quantum analogue of the PCP theorem for QMA remains wide open. A central obstacle is the local indistinguishability of quantum codes: every sufficiently small view of an encoded witness is independent of the witness, seemingly preventing a local verifier from distinguishing YES from NO instances. One approach to this apparent paradox in the work of Anshu, Breuckmann and Nguyen, is to encode the witness in a quantum code and compute on it fault-tolerantly, successively reducing the encoding length until the answer is revealed. We study a classical relaxation of this approach based on the equivalent view of quantum codes as private randomized encodings from multiparty computation. Specifically, we ask whether one can construct circuits that compute on a private encoding of an NP witness, such that every sufficiently small fractional view of the honest computation transcript is independent of the witness (i.e. has quantum distance) and the computation remains correct despite a small fraction of adversarial bit-flip or X-errors in every layer.
We construct such circuits and use the classical Cook--Levin theorem to obtain private PCPs for NP: the prescribed PCP encoding is randomized, and for each instance every view below the privacy threshold has the same distribution for all assignments, whether satisfying or not. For Circuit-SAT instances of size $n$, we get $\sqrt{n}$-query private PCPs of size $O(n\log n)$ over alphabet size $\mathrm{poly}(n)$, fractional privacy $\Omega(1/\log n)$ and constant soundness gap. Furthermore, conditional on a high-dimensional product expansion conjecture for Reed-Solomon codes, our PCPs have length $n^{1+o(1)}$, use $n^{o(1)}$ queries, and have fractional privacy and soundness gap $n^{-o(1)}$.
Our construction is based on a new family of small-alphabet quantum codes which have near-linear rate, sparse $X$-checks that enable local testability for $X$-errors, support for multiplication (or transversal CCZ gates on the full logical space) and near-linear quantum distance using product expansion. The codes are obtained using tensor products of Reed--Solomon codes, and our key innovation is to choose the evaluation domains as multiplicative subgroups of pairwise coprime orders of $\mathbb{F}_q^\star$. A proof obtained by ChatGPT 5.6 Sol establishes constant 2-dimensional product expansion whenever both rates are bounded away from one, crossing the tight sum-of-rates-below-one barrier in the product expansion theorem of Polishchuk and Spielman. We conjecture the analogous statement in higher dimensions.
