Discrete quantum walk on a cycle vs classical random walk — quadratic speedup
Discrete quantum walk on a cycle of N nodes uses a coin operator (Hadamard)
followed by a conditional shift. The walker's state is |ψ⟩ = Σ (α_j|↑⟩ + β_j|↓⟩)|j⟩.
After t steps from node 0, probability concentrates at ±N/2 (quadratic ballistic spreading
vs classical √t diffusion). Hitting time to reach the antipodal node:
quantum O(N) vs classical O(N²) — quadratic speedup.
The Grover search algorithm is a quantum walk on the complete graph. Childs et al. (2003)
showed exponential speedup for graph traversal problems. The coin matrix here is Hadamard:
H = ½[[1,1],[1,−1]], giving balanced left/right amplitudes with interference.