Coined Quantum Walk
Hitting Time on Line Graph · Quadratic Speedup · Classical vs Quantum Comparison
Grid Size N
50
Coin θ (Hadamard=π/4)
π/4
Initial state
|↑⟩
|↓⟩
(|↑⟩+i|↓⟩)/√2
Reset
Pause
Coin: C = [[cos θ, sin θ],[sin θ, −cos θ]]
Shift: S|↑,x⟩=|↑,x+1⟩ S|↓,x⟩=|↓,x-1⟩
Quantum spread: σ ∝ t (ballistic vs √t classical)
Hitting time: T_Q ~ √N vs T_C ~ N²