Ballistic spreading vs classical diffusion — quantum superposition in position space
Step: 0
σ (QW): 0
σ (classical): 0
Speedup: 1.0x
Quantum walks are the quantum analog of random walks. A coin flip (unitary coin operator, typically the Hadamard gate H) acts on an internal spin degree of freedom, then a shift operator moves the walker left or right based on the spin. Because quantum mechanics allows superposition, the walker interferes with itself — spreading ballistically (σ ∝ t) rather than diffusively (σ ∝ √t). This quadratic speedup underlies quantum search algorithms (Grover ≡ coined QW on hypercube). The characteristic two-peaked distribution with depletion at center is a purely quantum interference effect. Symmetric initial state (|+⟩) gives symmetric distribution.