Finding is as easy as detecting for quantum walks

Details Finding is as easy as detecting for quantum walks Finding is as easy as detecting for quantum walks

2010-02-11

arxiv.org/abs/1002.2419v1

ICALP'10, LNCS vol. 6198, pp. 540-551 (2010)

Physics

Quantum Physics

15 pages

Scientific paper

10.1007/978-3-642-14165-2_46

We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. The number of steps of the quantum walk is quadratically smaller than the classical hitting time of any reversible random walk $P$ on the graph. Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the walk $P$ and the absorbing walk $P'$, whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of the interpolation. Contrary to previous approaches, our results remain valid when the random walk $P$ is not state-transitive, and in the presence of multiple marked vertices. As a consequence we make a progress on an open problem related to the spatial search on the 2D-grid.

Affiliated with

Also associated with

No associations

Rating

Finding is as easy as detecting for quantum walks 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 Finding is as easy as detecting for quantum walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding is as easy as detecting for quantum walks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418990