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 (9)

• Quantum Algorithms Revisited
• Search via Quantum Walk
• Quantum query complexity of state conversion
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Nested Quantum Walks with Quantum Data Structures
• Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
• Quantum walk based search algorithms
• Quantum algorithms for subset finding
• The Quantum Query Complexity of Algebraic Properties

Cited by in corpus (13)

• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• Quantum walk speedup of backtracking algorithms
• Quantum-accelerated constraint programming
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Weakly measured while loops: peeking at quantum states
• Variations on Quantum Adversary
• Improved quantum backtracking algorithms using effective resistance estimates
• Applications of the Adversary Method in Quantum Query Algorithms
• Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
• A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
• Quantum walk search algorithms and effective resistance
• Adversary Lower Bound for the Orthogonal Array Problem