Lower Bounds for Quantum Search and Derandomization

Details Lower Bounds for Quantum Search and Derandomization Lower Bounds for Quantum Search and Derandomization

1998-11-18

arxiv.org/abs/quant-ph/9811046v1

Physics

Quantum Physics

12 pages LaTeX. Submitted to CCC'99 (formerly Structures)

Scientific paper

We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds for Quantum Search and Derandomization 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 Lower Bounds for Quantum Search and Derandomization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds for Quantum Search and Derandomization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515689