  Given a function f as an oracle, the collision problem is to find two
distinct inputs i and j such that f(i)=f(j), under the promise that such inputs
exist. Since the security of many fundamental cryptographic primitives depends
on the hardness of finding collisions, quantum lower bounds for the collision
problem would provide evidence for the existence of cryptographic primitives
that are immune to quantum cryptanalysis.
  In this paper, we prove that any quantum algorithm for finding a collision in
an r-to-one function must evaluate the function Omega((n/r)^{1/3}) times, where
n is the size of the domain and r|n. This improves the previous best lower
bound of Omega((n/r)^{1/5}) evaluations due to Aaronson [quant-ph/0111102], and
is tight up to a constant factor.
  Our result also implies a quantum lower bound of Omega(n^{2/3}) queries to
the inputs for the element distinctness problem, which is to determine whether
or not the given n real numbers are distinct. The previous best lower bound is
Omega(sqrt{n}} queries in the black-box model; and Omega(sqrt{n}log{n})
comparisons in the comparisons-only model, due to H{\o}yer, Neerbek, and Shi
[ICALP'01, quant-ph/0102078].
