Volume 1 (2005) Article 3 pp. 37-46
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
Received: November 23, 2004
Published: May 13, 2005
Download article from ToC site:
[PDF (150K)]    [PS (247K)]    [PS.GZ (70K)]
[Source ZIP]
Keywords: quantum computation, quantum query algorithms, quantum lower bounds, polynomials method, complexity of Boolean functions, element distinctness
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, \ldots, N\}\to\{1, \ldots, M\}$, its polynomial degree is the same for all $M\geq 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\geq N$. In particular, we get $\Omega(N^{1/3})$ and $\Omega(N^{2/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.