Theory of Computing
-------------------
Title : Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
Authors : Andris Ambainis
Volume : 1
Number : 3
Pages : 37-46
URL : http://www.theoryofcomputing.org/articles/v001a003
Abstract
--------
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\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.