Volume 1 (2005) Article 2 pp. 29-36

Quantum Lower Bound for the Collision Problem with Small Range

by Samuel Kutin

Received: December 8, 2004
Published: April 14, 2005
DOI: 10.4086/toc.2005.v001a002

Download article from ToC site:
[PS (198K)]    [PS.GZ (63K)]    [PS.ZIP (63K)]
[PDF (122K)]    [DVI (71K)]    [TeX (17K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: Quantum, Query, Oracle, Collision, Polynomial method, Lower bound, Small Range
Categories: quantum, short, query complexity, lower bounds, complexity theory
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.