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.