QUANTUM vs CLASSICAL
Quantum walk evolves via unitary:
|ψ(t+1)⟩ = U|ψ(t)⟩
U = S·(C⊗I)
C = Hadamard coin
S = shift operator
Classical: P(t+1) = A·P(t)/deg
(diffusion)
Key difference: quantum walk uses interference. Probability can concentrate at target nodes — enabling quadratic speedup for search (Grover-like).
On the 2D grid: hitting time is O(n) vs O(n log n) classical.