Volume 1 (2005)
Article 2 pp. 29-36
Quantum Lower Bound for the Collision Problem with Small Range
Received: December 8, 2004
Published: April 14, 2005
Published: April 14, 2005
Keywords: Quantum, Query, Oracle, Collision, Polynomial method, Lower bound, Small Range
Categories: quantum computing, short, query complexity, lower bounds, complexity theory, polynomial method
ACM Classification: F.1.2
AMS Classification: 81P68, 68Q17
Abstract: [Plain Text Version]
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.