A new computational complexity result shows that a polynomial-time classical verifier can validate arbitrary polynomial-time quantum computations, with an efficient honest prover and without cryptographic assumptions, provided one works relative to a classical oracle. The constructed protocol is public-coin, with perfect completeness and soundness error at most 1/4, and it applies to a language that lies beyond the polynomial hierarchy but is decided exactly in quantum polynomial time. According to the authors, this is the first time a language with such a proof system has been shown to lie outside AM relative to an oracle.

The work addresses an open question at the frontier between quantum computation and classical verification: whether a purely classical verifier can certify the outcome of a quantum computation without relying on computational assumptions. The constructed language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, while the verifier recursively checks the prover's secrets against random code entries.

The recursion restricts the input in a correlated way: the same secret fixes the code bits and chooses the free coordinate, which prevents applying Håstad's switching lemma. To overcome this obstacle, the authors prove a switching theorem of their own for these restrictions, which may be of independent interest. As a consequence, for instances of sufficient height, no constant-depth circuit of size 2^poly(n) changes its output with probability above 2^(-Ω(n)) when the answer of a random instance is flipped by changing a single leaf.

The protocol is also efficient in a quantitative sense: for every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, the verifier, and the honest prover are bounded by that function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many input lengths.