Physics – Quantum Physics
Scientific paper
2006-08-02
SIAM Journal on Computing, 40(1):142-164, 2011
Physics
Quantum Physics
21 pages. Various modifications and improvements, especially in Section 4
Scientific paper
10.1137/090745854
We propose a new method for designing quantum search algorithms for finding a "marked" element in the state space of a classical Markov chain. The algorithm is based on a quantum walk \'a la Szegedy (2004) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis (2004) and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
Magniez Frederic
Nayak Ashwin
Roland Jérémie
Santha Miklos
No associations
LandOfFree
Search via Quantum Walk 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 Search via Quantum Walk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search via Quantum Walk will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-265006