ABSTRACT Quantum Lower Bound for the Collision Problem

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 boun