%0 Generic %1 ambainis2019quadratic %A Ambainis, Andris %A Gilyén, András %A Jeffery, Stacey %A Kokainis, Martins %D 2019 %K q_machine_learning %T Quadratic speedup for finding marked vertices by quantum walks %U http://arxiv.org/abs/1903.07493 %X 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.

@misc{ambainis2019quadratic, 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.}, added-at = {2019-05-15T12:19:40.000+0200}, author = {Ambainis, Andris and Gilyén, András and Jeffery, Stacey and Kokainis, Martins}, biburl = {https://www.bibsonomy.org/bibtex/2ac9b287c5e80aa4d81228ec08ce49353/annapappa}, description = {Quadratic speedup for finding marked vertices by quantum walks}, interhash = {5f7569078ae894fc92d0b5e5374ececd}, intrahash = {ac9b287c5e80aa4d81228ec08ce49353}, keywords = {q_machine_learning}, note = {cite arxiv:1903.07493Comment: 21 pages, 7 figures}, timestamp = {2019-05-15T12:19:40.000+0200}, title = {Quadratic speedup for finding marked vertices by quantum walks}, url = {http://arxiv.org/abs/1903.07493}, year = 2019 }