Does Not Relativize
In the authors' words
We construct an oracle relative to which , resolving a long-standing open question in quantum complexity theory. Together with recent work due to Aaronson et al., our work also gives the first oracle separation between and , answering a question dating back to Fortnow's thesis. Our separation is based on the Forrelation problem, where given Boolean functions and , the goal is to determine if is correlated with the Fourier spectrum of . While this task is solvable by a query-efficient quantum algorithm, we show that it admits no classical interactive protocol with polynomial communication and a polynomial-query verifier. Our proof is based on (i) a new structural result showing how to approximate Avg-Max circuits (which are well-known to capture the power of interactive proofs in the oracular setting) by convex functions with small first and second derivatives and (ii) a novel analysis establishing that the Forrelation distribution suggested by Aaronson and Ambainis fools such functions. Our results imply that any prover-efficient classical interactive protocol for must rely on non-relativizing techniques. This might serve as a partial explanation for the lack of progress towards doubly-efficient, unconditionally sound classical verification of quantum computation.
Appeared: Wednesday, September 23. arXiv. Preprint, not yet peer-reviewed.