Volume 1 (2005) Article 2 pp. 29-36
Quantum Lower Bound for the Collision Problem with Small Range
We extend Aaronson and Shi's quantum lower bound for the $r$-to-one collision problem. An $r$-to-one function is one where every element of the image has exactly $r$ preimages. The $r$-to-one collision problem is to distinguish between one-to-one functions and $r$-to-one functions over an $n$-element domain.
Recently, Aaronson and Shi proved a lower bound of $\Omega((n/r)^{1/3})$ quantum queries for the $r$-to-one collision problem. Their bound is tight, but their proof applies only when the range has size at least $3n/2$. We give a modified version of their argument that removes this restriction.