arXiv:2610.37635
Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
Atul Mantri
Abstract
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. 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, verifier, and honest prover are bounded by this 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 lengths, with a constant depending on its verifier. The 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, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.
AI Summary
Can a classical polynomial-time verifier verify quantum computations using one efficient quantum prover, without computational assumptions? This paper addresses an oracle version: whether a decision language admitting such verification can lie beyond the polynomial hierarchy. It constructs a classical Boolean oracle $O$ and a total unary language $L\in\mathrm{EQP}^O\setminus\mathrm{PH}^O$ with a public-coin classical interactive proof, an efficient quantum honest prover, perfect completeness, and soundness error at most $1/4$ against computationally unbounded provers. For recursion height $h(n)\le\lfloor\log n/8\rfloor$, exact quantum evaluation uses $3^{h(n)}$ queries; verification uses $2h(n)$ messages and at most $4^{h(n)}$ queries. Choosing the oracle appropriately permits any polynomial-time-computable unbounded message or query bound. A further oracle construction forces every correct polynomial-time verifier to use $\Omega(h(n))$ messages infinitely often, with the constant depending on the verifier. The problem recursively composes code-based addressing: a quantum-decodable code hides the secret selecting a data-table entry. Verification checks claimed secrets recursively at random code positions. The lower bound develops switching machinery for projections whose fixed code bits and free coordinate depend on the same secret. It establishes exponentially small distinguishing advantage for constant-depth circuits of size $2^{\mathrm{poly}(n)}$, enabling diagonalization against $\mathrm{PH}$. The result is oracle-relative, not a general verification protocol for $\mathrm{BQP}$. Hardness of the fixed-predicate recursive Fourier sampling formulation remains open, as does a matching alternation lower bound. A noisy-code extension requires structured promises at every node, not arbitrary leaf corruption.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.