Optimized quantum random-walk search algorithms

Details Optimized quantum random-walk search algorithms Optimized quantum random-walk search algorithms

2008-05-28

arxiv.org/abs/0805.4347v3

Phys. Rev. A 79, 012325 (2009)

Physics

Quantum Physics

7 pages, 2 figures. Major revision according to referee report

Scientific paper

10.1103/PhysRevA.79.012325

Shenvi, Kempe and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require $O(\sqrt N)$ number of oracle queries to find the marked element, where $N$ is the size of the search space. The overall time complexity of the SKW algorithm differs from the best achievable on a quantum computer only by a constant factor. We present improvements to the SKW algorithm which yield significant increase in success probability, and an improvement on query complexity such that the theoretical limit of a search algorithm succeeding with probability close to one is reached. We point out which improvement can be applied if there is more than one marked element to find.

Affiliated with

Also associated with

No associations

Rating

Optimized quantum random-walk search algorithms 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 Optimized quantum random-walk search algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized quantum random-walk search algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-416503