Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range

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} → {1,…, M}, its polynomial degree is the same for all M ≥ 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 ≥ N. In particular, we get Ω(N^1/3) and Ω(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.