Quantum Walks and Electric Networks

Abstract

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.

10 pages

References in corpus (3)

• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Quantum walk based search algorithms
• The Quantum Query Complexity of Algebraic Properties

Cited by in corpus (2)

• A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
• Adversary Lower Bound for the Orthogonal Array Problem