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 : https://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.