Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range

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\ge N$. Therefore, if we have a quantum lower bound for some (possibly, quite large) range $M$ which is shown using polynomials method, we immediately get the same lower bound for all ranges $M\ge 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.

9 pages, LaTeX, v2 new result on degree lower bound for AND-OR added, v3 many small changes

References in corpus (3)

• Quantum walk algorithm for element distinctness
• A quantum lower bound for the collision problem
• Quantum Algorithms for the Triangle Problem

Cited by in corpus (2)

• The quantum query complexity of read-many formulas
• Element Distinctness Revisited