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       : https://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.