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

Simple item page
dc.creatorAmbainis, Andris
dc.date2003-05-29
dc.date2005-04-29
dc.date.accessioned2026-07-07T09:38:06Z
dc.date.available2026-07-07T09:38:06Z
dc.descriptionWe 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 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\geq N$. In particular, we get $Ω(N^{1/3})$ and $Ω(N^{2/3})$ quantum lower bounds for collision and element distinctness with small range.
dc.description9 pages, LaTeX, v2 new result on degree lower bound for AND-OR added, v3 many small changes
dc.identifierhttps://arxiv.org/abs/quant-ph/0305179
dc.identifierhttp://arxiv.org/abs/quant-ph/0305179
dc.identifierTheory of Computing, 1:37-46, 2005
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/160685
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titlePolynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
dc.typetext

Files

Collections

arXiv