Published: May 13, 2005
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.