Quantum Walk
A classical random walker flips a coin and steps left or right. After N steps, they're typically √N from the start — bell-curve distribution centered at 0. A quantum walker carries a coin qubit instead, applies Hadamard each step, and steps both ways at once. After N steps, the distribution is bimodal with peaks at ±N/√2 and ballistic spread. Same recipe, quadratically faster.
why quantum spreads quadratically faster
A classical walker on the integer line has state (position, coin). Each step: flip the coin → move ±1. After N steps:
• Position is sum of N iid ±1 increments.
• Variance = N → standard deviation = √N.
• Distribution converges to N(0, N) (Gaussian centered at 0).
A quantum walker has a position register and a coin qubit. Each step is a unitary: Hadamard the coin (creating superposition of ±1), then translate based on coin state. The walker doesn't actually choose left or right — it does both, with amplitudes that interfere.
Key difference: classical walks have independent random coin flips. Quantum walks have coherently superposed coin states. The amplitudes at position x come from many paths that ended at x — and these amplitudes interfere, mostly destructively in the middle, constructively at the wings. Result: bimodal distribution with ballistic spread.
Applications: Grover's quantum search uses a quantum walk — gives O(√N) instead of O(N) for unstructured database lookup. Quantum walk algorithms also speed up: element distinctness (O(N^(2/3))), triangle finding, NAND tree evaluation. The ballistic spread of the quantum walk is the underlying engine of these speedups.
Compare the histograms above: classical (gold) is a tight bell around 0. Quantum (purple) is bimodal with most probability near ±N/√2. Same algorithm complexity (N coin flips, N translations), wildly different probability profile.