Theory of Computing
-------------------
Title : Quantum Lower Bound for the Collision Problem with Small Range
Authors : Samuel Kutin
Volume : 1
Number : 2
Pages : 29-36
URL : http://www.theoryofcomputing.org/articles/v001a002
Abstract
--------
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.