Coined Quantum Walk vs Classical Random Walk

Probability spreading on a line — quadratic speedup in hitting time

Quantum walk Classical walk Target (hit!)
Step t: 0
QW std σ: 0.00
CW std σ: 0.00
QW σ/t: —
CW σ/√t: —
The discrete-time coined quantum walk uses a Hadamard coin to create superposition. Quantum spreading is ballistic: σQW ~ t (not √t). The hitting time to reach ±N/2 from origin scales as O(N) classically but O(N) quantum too — but with quadratic improvement in the probability of success per step. The bimodal distribution (peaks near ±t/√2) is a quantum signature with no classical analog. Phase of coin (θ) controls the bias of the distribution.