Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-072 | 12th November 2002 00:00

Quantum Lower Bound for Recursive Fourier Sampling

RSS-Feed




TR02-072
Authors: Scott Aaronson
Publication: 23rd December 2002 16:38
Downloads: 1163
Keywords: 


Abstract:

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 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.



ISSN 1433-8092 | Imprint