Volume 1 (2005) Article 3 pp. 37-46

Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range

by Andris Ambainis

Received: November 23, 2004
Published: May 13, 2005
DOI: 10.4086/toc.2005.v001a003

Download article from ToC site:
[PS (243K)]    [PS.GZ (70K)]    [PS.ZIP (70K)]
[PDF (144K)]    [DVI (104K)]    [TeX (28K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: quantum computation, quantum query algorithms, quantum lower bounds, polynomials method, complexity of Boolean functions, element distinctness
Categories: quantum, short, query complexity, lower bounds, complexity theory, polynomials
ACM Classification: F.1.2
AMS Classification: 81P68, 68Q17

Abstract: [Plain Text Version]

We give a general method for proving quantum lower bounds for problems with small range. Namely, we show that, for any symmetric problem defined on functions f:{1,...,N} to {1,...,M}, its polynomial degree is the same for all M≥N. Therefore, if we have a quantum query lower bound for some (possibly quite large) range M which is shown using the polynomials method, we immediately get the same lower bound for all ranges M≥N. In particular, we get Ω(N1/3) and Ω(N2/3) quantum lower bounds for collision and element distinctness with small range, respectively. As a corollary, we obtain a better lower bound on the polynomial degree of the two-level AND--OR tree.