1302.3143 (Aleksandrs Belovs)

Quantum Walks and Electric Networks    [PDF]

Aleksandrs Belovs

We prove that a quantum walk can detect the presence of a marked element in a graph in $O(\sqrt{WR})$ steps for any initial probability distribution on vertices. Here, $W$ is the total weight of the graph, and $R$ is the effective resistance. This generalizes the result by Szegedy that is only applicable if the initial distribution is stationary. We describe a time-efficient quantum algorithm for 3-distinctness based on these ideas.

View original: http://arxiv.org/abs/1302.3143