@annapappa

Quadratic speedup for finding marked vertices by quantum walks

, , , and . (2019)cite arxiv:1903.07493Comment: 21 pages, 7 figures.

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.

Description

Quadratic speedup for finding marked vertices by quantum walks

Links and resources

URL:
BibTeX key:
ambainis2019quadratic
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication