## 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 Ω(n^{1/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(n^{1/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 Ω(n^{1/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)

Edit this abstract