A discrete-time coined quantum walk lives on the vertices of a graph — here an N×N grid — each carrying a small "coin" register that picks a direction (up/down/left/right). One step interleaves a coin flip and a shift:
|ψ_{t+1}⟩ = S · (C ⊗ I) |ψ_t⟩
C = Grover diffusion coin at unmarked vertices:
C = 2|s⟩⟨s| − I, |s⟩ = uniform superposition over 4 directions
C' = −I (a π phase flip) at the MARKED vertex — this is the oracle
S = shift operator: move probability amplitude to the neighbor
indicated by the coin state
Unlike a classical random walk, amplitudes can interfere destructively almost everywhere and constructively at the marked vertex. The Shenvi–Kempe–Whaley / Ambainis quantum-walk search shows that, tuned correctly, the probability of finding the walker at the marked vertex rises to Θ(1) after only O(√N) steps — the same quadratic speed-up as Grover's algorithm, but built from local graph moves instead of a global oracle circuit. A classical random walk needs Θ(N) steps to reach comparable hitting probability, which the "overlay" button plots for direct comparison.
- Step / Run — advances the coined quantum walk one iteration (coin flip + shift) at a time.
- Click a grid cell — relocates the marked vertex (the oracle target) and resets the walk.
- Overlay classical walk — runs a lazy classical random walk from the same start with the same step budget, so you can see the O(N) vs O(√N) gap directly in the readouts.
Real-world relevance: quantum-walk search is one of the two canonical quadratic-speedup search primitives (with Grover's circuit model) and underlies proposed speed-ups for graph connectivity, element distinctness, and spatial-search problems on structured databases.