Quadratic speedup in finding a marked vertex via quantum walk

Stacey Jeffery, QuSoft, Research Centre for Quantum Software

A random walk on a graph, P, with marked vertex set M, finds a marked vertex using a O(HT(P,M)) steps of the walk, where HT(P,M) is the hitting time. Previous quantum algorithms could detect the presence of a marked vertex in O(sqrt{HT(P,M)}) steps, or find a marked vertex in O(sqrt{HT(P,M)}) steps if M contained at most one vertex, but the case of finding in the presence of multiple marked vertices was left as an open problem. We close this open problem by giving a new quantum algorithm that finds a marked vertex in O(sqrt{HT(P,M)}) steps of the walk for any M. This is joint work with Andris Ambainis, András Gilyén and Martins Kokainis.