Preprint: classical verification of quantum computation beyond the Polynomial Hierarchy
A preprint by Atul Mantri of a Department of Computer Science (not yet peer reviewed) describes a protocol in which a classical verifier checks quantum computations for languages decidable exactly in quantum polynomial time and lying beyond the Polynomial Hierarchy, relative to an oracle. Quantum Zeitgeist reports the protocol uses public communication, has perfect completeness and a soundness error of at most 1/4. The authors say it gives an interactive proof system outside AM relative to an oracle, with message counts bounded by a polynomial in input length. They also report that no polynomially sized constant-depth circuit can alter an output with probability above 2^-Ω(n) when a single leaf node changes. The demonstration uses recursive Fourier sampling, with code tables encoding secrets that address data tables evaluated recursively.