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