Abstract
A quantum walk algorithm can detect the presence of a marked vertex on a
graph quadratically faster than the corresponding random walk algorithm
(Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked
element quadratically faster than a classical random walk were only known for
the special case when the marked set consists of just a single vertex, or in
the case of some specific graphs. We present a new quantum algorithm for
finding a marked vertex in any graph, with any set of marked vertices, that is
(up to a log factor) quadratically faster than the corresponding classical
random walk.
Users
Please
log in to take part in the discussion (add own reviews or comments).