Quantum lower bound for the collision problem

(MATH) 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.

Authors

• Scott Aaronson

Keywords

No keywords are indexed for this paper.