pdf icon
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
Download article from ToC site:
[PDF (128K)] [PS (201K)] [Source ZIP]
Keywords: Quantum, Query, Oracle, Collision, Polynomial method, Lower bound, Small Range
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.