The Polynomial Degree of Recursive Fourier Sampling

Scott Aaronson

Peter Høyer

Leo A. Harrington, Benjamin Johnson

We define a canonical version of the recursive Fourier sampling problem from quantum complexity theory, and systematically address a variety of its computational properties, including quantum query complexity, classical randomized query complexity, polynomial degree, and circuit size. Our analysis yields improvements for several of the known upper and lower bounds with regard to these complexity measures. For quantum query complexity, we define an explicit reduced-query quantum algorithm for the problem, and recursively construct a quantum circuit that implements the algorithm. For classical query complexity, we give new proofs of the known lower bounds that improve the constants, and we give complete proofs of the complexity class separations relative to oracles, that follow from these bounds. For polynomial degree, we construct an exactly representing real polynomial of extremely low degree, and extend it to representations over other Fields. We show that this degree is exactly optimal, even for a 2 weakly-representing polynomial. For circuit size, we construct a small depth-two circuit for the non-recursive version of the problem, and we show that the size is optimal even if the depth is not restricted. We also prove asymptotically matching upper and lower bounds on circuit size for the full recursive version of the problem when the depth is restricted to two. To prove the tight results for polynomial degree and circuit size we introduce and define a general notion of reduction for both polynomials and circuits that represent boolean functions on a partial domain. We also introduce and define, separately, a new measure of circuit complexity called effort.

Scott Aaronson

We revisit the oft-neglected `recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place \mathsf{BQP} outside of PH[\log] relative to an oracle, one would need to go outside the RFS framework. Our proof argues that, given any variant of RFS, either the adversary method of Ambainis yields a good quantum lower bound, or else there is an efficient classical algorithm. This technique may be of independent interest.

Christoffer Hindlycke, Niklas Johansson, Jan-Åke Larsson

Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin-Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.

Ran Raz