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

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

2003-05-29

arxiv.org/abs/quant-ph/0305179v3

Theory of Computing, 1:37-46, 2005

Physics

Quantum Physics

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

Scientific paper

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 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 $\Omega(N^{1/3})$ and $\Omega(N^{2/3})$ quantum lower bounds for collision and element distinctness with small range.

Affiliated with

Also associated with

No associations

Rating

Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-607509