Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

The paper in detail

Verification of quantum computation is known in modified settings: with a verifier that handles a few qubits, with two entangled provers, or with one prover under the hardness of learning with errors. With one quantum prover, a classical verifier and no assumption, only particular problems have protocols: factoring and other \(\mathsf{NP}\cap\mathsf{coNP}\) problems with one message, the order of a solvable black-box group in AM, circuits with two basis changes in MA, and McKague’s protocol for recursive Fourier sampling, a problem excluded from MA relative to an oracle. Such a protocol for all of BQP cannot relativize, since Forrelation has no interactive proof at all relative to some oracle.

Each node of the instance hides a secret \(s\in\mathbb F_2^m\). Its code table has entries \(L_x=s\cdot x\), its data table \(R\) is unconstrained, and its value is \(R_s\); every table entry is itself the value of a smaller subtree, and only the leaves are stored in the oracle. Dimensions shrink by a factor of about 16 per level and the height is at most \(\lfloor\log n/8\rfloor\). The quantum algorithm evaluates a node with three recursive calls: querying the code children in superposition prepares the phase state of the codeword, a Hadamard transform yields \(\ket s\) exactly, one call adds \(R_s\), and a final call uncomputes \(s\). The total is \(3^h\) leaf queries with zero error.

To check a claimed value, the prover sends the claimed secret, and the verifier tests three fresh random code entries against its codeword and the data entry at that secret against the claimed value, recursively. All claims of one height are sent in one message before the verifier draws its challenges, so the protocol uses \(2h\) messages, \(h\) from each side. An induction shows that from a list with \(F\) false claims the verifier accepts with probability at most \(4^{-F}\), independent of the height. The oracle must not answer queries that test a proposed internal secret; with such equality tests the problem would fall into \(\mathsf{NP}\cap\mathsf{coNP}\).

For the exclusion from PH, two instances that share all random choices and differ only in the root value differ in exactly one leaf. Theorem 1.7 shows that a circuit of constant depth \(D\) and size \(2^{n^A}\) changes its output on this pair with probability at most \(2^{-cn}\) once the height exceeds a constant \(h_0(D,A)\); translating alternating quantifiers into such circuits and diagonalizing over machines builds the oracle. Håstad’s switching lemma does not apply, because the secret both fixes the code bits and chooses which leaf stays free, and a single level can turn a narrow CNF into an AND of many free variables. The proof instead bounds the first satisfied term of a DNF by a rank argument, converts this into sensitivity and certificate bounds, and switches several levels at once. A separate argument shows that distinguishing the root values needs DNF width \(n^{\Omega(h)}\), so any proof system needs a constant fraction of \(h\) messages.

Transferable methods

1. Recursive spot-checks with a height-independent soundness invariant

   The verifier checks a claimed secret against a few random codeword entries and recurses into the children it tested. An invariant bounding acceptance by \(4^{-F}\), where \(F\) counts false claims, makes soundness independent of the depth, and it fixes how many checks per level are needed.

   For the Hadamard code, distinct secrets \(s\ne s^\prime\) have codewords that differ on exactly half the entries, since \(x\mapsto(s\oplus s^\prime)\cdot x\) is balanced. If a false value claim comes with the true secret, the data child at \(s\) carries a false claim. If it comes with a wrong secret, each of three fresh random code entries is a false claim with probability \(1/2\), so the number \(Y\) of false child claims is Binomial(3, 1/2). By induction, acceptance is at most \(\mathbb E[4^{-Y}]\), and \[\mathbb E[4^{-Y}]=\Bigl(\frac{1+1/4}{2}\Bigr)^3=\Bigl(\frac58\Bigr)^3\approx0.244\le\frac14,\] while the true-secret case gives exactly \(1/4\).

   Editorial note: with two code checks the same computation gives \((5/8)^2\approx0.39>1/4\) and the induction fails, which is why the protocol uses three. Because the bound conditions on the whole history and on the prover’s message of claimed secrets, it survives batching all claims of one height into a single message and holds for any prover memory.

   How to reuse it

   When a verifier checks claims recursively, choose the number of spot checks per level so that the expected value of \(c^{-(\text{false children})}\) is at most \(c^{-1}\); soundness then holds at every depth without repetition. The same computation, with the code’s relative distance in place of \(1/2\), sets the number of checks for other codes.

2. Switching under correlated projections via a rank bound

   Håstad’s switching lemma needs restrictions that fix coordinates independently. Here the secret both fixes the code bits and chooses which leaf stays free, so the paper instead bounds how often the first satisfied term of a DNF can depend on the free leaves of many nodes, using a rank argument over low-degree polynomials in the secret.

   Order the terms of a width-\(W\) DNF and fix a random data table. For each surviving term that tests at most \(t\) code entries of a node and is first satisfied at some secret, choose one such secret. The matrix whose \((\lambda,\xi)\) entry records whether term \(\lambda\)’s code literals hold at the secret chosen for term \(\xi\) is lower triangular with unit diagonal, so its rank equals its number of rows, while each row is a polynomial of degree at most \(dt\) in the secret. Hence at most \(\binom{m}{\le dt}\) terms qualify, whatever the size of the DNF, and the probability that \(\ell\) of \(K\) nodes are light for the first satisfied term is at most \[\binom{K}{\ell}\Bigl(\frac{2W}{\ell}\Bigr)^{\ell}\binom{m}{\le dt}^{\ell}2^{-m\ell}.\]

   One level does not suffice: the CNF \(\Gamma(L,R)=\bigwedge_{y}\bigl(\bigvee_i[L_{e_i}\ne y_i]\vee R_y\bigr)\) has width \(m+1\), and under the projection every clause except the one for \(y=s\) is satisfied, so it becomes exactly the free variable \(R_s\). The proof therefore applies \(\lfloor\alpha\rfloor+1\) levels per switching step for width \(n^\alpha\), turns the rank bound into a sensitivity bound and then a tail bound on certificate complexity, and composes errors at each fixed input over a constant number \(h_0\) of levels.

   How to reuse it

   When random restrictions are correlated with the values they fix, count first satisfied terms by a rank argument over the low-degree polynomials that describe when each term fires. This removes any dependence on the number of terms and can replace independence in switching arguments for structured or code-based restrictions.

Source: Sections 1.3 and 2 (proof outline); Section 5 (Theorem 5.1, Protocols 5.2–5.3, Claim 5.4, Theorem 5.5); Section 6 (Theorems 6.1, 6.5, 6.9, 6.15, 1.7); Appendix B. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. Efficient classical verification of quantum computation is compatible, relative to an oracle, with quantum power beyond every level of PH, so any proof that verifiable problems lie in PH must be nonrelativizing. The main technical tool, a switching theorem for random projections in which the same secret fixes the code bits and selects the free coordinate, extends Håstad’s method to correlated restrictions and may be useful for other lower bounds.

Limitations. The result holds relative to an oracle that stores only the leaves of the recursion and says nothing directly about unrelativized BQP. The language is a purpose-built recursive construction, not a natural task, and the honest prover makes \(4^h-3^h\) queries. The proof of the circuit lower bound is long and new; the author states that AI models contributed substantially to developing it, and it has not yet been independently checked. Whether the number of quantifier alternations used is necessary is open.

Description based on the full text of the linked arXiv version, read 2026-10-28; equations follow the paper’s notation.