Quantum walk search algorithms and effective resistance

Understand

We consider the problem of finding a marked vertex in a graph from an arbitrary starting distribution, using a quantum walk based algorithm.

• We work in the framework introduced by Belovs which showed how to detect the existence of a marked vertex in $O(\sqrt{RW})$ quantum walk steps, where $R$ is the effective resistance and $W$ is the total weight of the graph.
• Our algorithm outputs a marked vertex in the same runtime up to a logarithmic factor in the number of marked vertices.
• When starting in the stationary distribution, this recovers the recent results of Ambainis et al.