Published: May 13, 2005

**Keywords:**quantum computation, quantum query algorithms, quantum lower bounds, polynomials method, complexity of Boolean functions, element distinctness

**Categories:**quantum computing, 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, \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.