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.