Quantum Walk Search on Graphs
Using quantum walks to find marked vertices faster than classical random walks, generalizing Grover search to graph structure.
From random walks to quantum walks
A classical random walker on a graph moves to a random neighbor each step; finding a marked vertex takes time related to the walk's hitting time. A quantum walk replaces the probabilistic step with a unitary coin-and-shift or a reflection operator, allowing amplitudes to interfere. For many graphs this yields a quadratic speedup in the number of steps needed to locate a marked vertex.
Search framework
The general recipe alternates two operations: a walk step that spreads amplitude according to the graph, and an oracle that marks target vertices by a phase flip. Repeating this alternation concentrates amplitude on the marked set, analogous to amplitude amplification. The number of repetitions scales with the square root of a quantity related to the graph's spectral gap and the fraction of marked vertices.
Cost measures
- Setup cost: preparing the walk's stationary distribution as a quantum state.
- Update cost: applying one walk step.
- Checking cost: applying the marking oracle.
- The total is setup + (1/sqrt(delta*epsilon))(update + check), with delta the spectral gap and epsilon the marked fraction.
Model choices
Two main formulations exist. Discrete-time quantum walks use a coin register and a shift operator (see discrete-time quantum walk). Continuous-time quantum walks evolve under a Hamiltonian derived from the graph's adjacency or Laplacian matrix (see continuous-time quantum walk). The Szegedy walk connects a discrete walk to any classical Markov chain and underlies the general search speedup.
Applications
Quantum walk search underlies algorithms for element distinctness, triangle finding, spatial search on lattices, and subset-sum-style problems. On well-connected graphs the quadratic speedup over classical search is provable. On poorly connected graphs the advantage can shrink, so graph structure matters. Quantum walks are also universal for computation, making them both an algorithmic tool and a model of quantum computing.