Abstracts for Umesh Vazirani

The EECS Research Summary for 2003


Quantum Lower Bound for the Collision Problem

Scott Aaronson
(Professor Umesh Vazirani)
DARPA grant and NSF Graduate Fellowship

The collision problem is to decide whether a function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Ω(n1/5) on the number of queries needed by a quantum computer to solve this problem with bounded error probability. The best known upper bound is O(n1/3), but obtaining any lower bound better than Ω(1) was an open problem since 1997. Our proof uses the polynomial method augmented by some new ideas. We also give a lower bound of Ω(n1/7) for the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Finally we give implications of these results for quantum complexity theory.

[1]
S. Aaronson, "Quantum Lower Bound for the Collision Problem," Proc. ACM Proc. ACM Symp. Theory of Computing, Montreal, Canada, May 2002.

More information (http://www.cs.berkeley.edu/~aaronson) or

Send mail to the author : (aaronson@cs.berkeley.edu)

The Complexity of Recursive Fourier Sampling

Scott Aaronson
(Professor Umesh Vazirani)
DARPA and NSF Graduate Fellowship

In recent work we are revisiting the oft-neglected recursive Fourier sampling (RFS) problem, introduced by Bernstein and Vazirani [1] to prove an oracle separation between BPP and BQP. RFS seems to offer the best hope for proving that BQP is not in the polynomial hierarchy relative to an oracle. As a first step, we seek to place RFS outside a smaller complexity class such as AM or Σ2P relative to an oracle.

In previous work [2], one of us showed 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 [3] yields a good quantum lower bound, or else there is an efficient classical algorithm. This technique may be of independent interest.

[1]
E. Bernstein and U. Vazirani, "Quantum Complexity Theory," SIAM Journal on Computing, Vol. 26, No. 5, 1997.
[2]
S. Aaronson, "Quantum Lower Bound for Recursive Fourier Sampling" (submitted).
[3]
A. Ambainis, "Quantum Lower Bounds by Quantum Arguments," Journal of Computer and System Sciences, Vol. 64, 2002.

More information (http://www.cs.berkeley.edu/~aaronson) or

Send mail to the author : (aaronson@cs.berkeley.edu)