Quantum Random Walk

Classical vs quantum: same walk, wildly different spread - interference changes everything

Worked example — Quantum Random Walk

Quantum / classical ratio	2.0775×
Quantum peak	0.2816

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

from random walks to quantum search 🖖

The quantum walk's quadratic speedup comes from interference, not probability. At each step the Hadamard puts the coin into superposition, so the shift operator moves amplitude left and right simultaneously. Over many steps, amplitude near the center cancels—left-moving and right-moving contributions arrive with opposite phases—while amplitude near ±N/√2 reinforces constructively. This is why the distribution peaks at the edges rather than the middle. The same mechanism drives Grover's search (a walk on a hypercube) and Childs's exponential-speedup graph traversal: quantum walks reach distant nodes far faster than any diffusive process can.

diffusion versus a ballistic sprint 🖖

A random walk is just repeated coin flips: heads step right, tails step left. Done classically, the steps blur into a bell curve — after 100 flips you rarely land more than about 10 sites from the start, because the spread grows like √N. Swap in a quantum coin and the walker stops averaging out and instead streaks outward, reaching toward ~70 sites after those same 100 steps. Physicists call this ballistic spreading: it grows linearly with N instead of as its square root.

a quantum walk never forgets 🖖

A classical random walk is a Markov process: it steadily loses track of where it began, and from the final cloud alone you can't reconstruct the starting point. The quantum walk is unitary, so every step is perfectly reversible. Run the exact Hadamard-and-shift sequence backwards and all that scattered amplitude reconverges into a single spike at the origin — no information is lost, and the walk has no equilibrium distribution to relax into. Diffusion erases history; a quantum walk merely hides it.

Problem solved in full

Spreads for 2 walkers over 10 steps 9 steps
10 steps, 2 walkers. One tosses a fair coin each step and moves ±1. The other starts in coin state |0⟩ and has the Hadamard gate applied to its coin before every move. Work out both spreads exactly, then say how many steps the classical walker needs to cover the same ground.
1. Classical steps are independent, and each one contributes a variance of exactly 1, so the variances add. That single line is the whole classical answer — and it is why the panel above prints a square root rather than a simulation.
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. The quantum walker never picks a branch. Carry 2 amplitudes at every site, one per coin value; the Hadamard replaces them with their sum and their difference, and then the |0⟩ half moves left while the |1⟩ half moves right. A site can receive from both neighbours, so amplitudes add — and a difference can come out 0.
  
  $(a_{0}, a_{1})_{x} ⟶ \frac{a _{0} + a _{1}}{2} (1, 0)_{x - 1} + \frac{a _{0} - a _{1}}{2} (0, 1)_{x + 1}$
3. Start at the origin with (1, 0) and run 2 steps. Pull the factor 1/√2 out of each step and the amplitudes stay whole numbers, so after step n the pairs below are all divided by 2^n/2.
  
  $n = 1 : (1, 0)_{- 1}, (0, 1)_{+ 1} n = 2 : (1, 0)_{- 2}, (1, 1)_{0}, (0, - 1)_{+ 2}$
4. Step 3 is where the symmetry dies. The site at the origin holds (1, 1): it sends 1 + 1 = 2 leftward and 1 − 1 = 0 rightward. The minus sign in the Hadamard's bottom row has erased that site's entire rightward contribution, and x = −1 now carries 5 times the probability of x = +1.
  
  $n = 3 : (1, 0)_{- 3}, (2, 1)_{- 1}, (- 1, 0)_{+ 1}, (0, 1)_{+ 3} ⟹ p (- 1) = \frac{5}{8}, p (+ 1) = \frac{1}{8}$
5. Keep cranking to step 10. Amplitudes are still whole numbers over 2⁵, so every probability is a whole number over 1024 — the 11 numerators below are exact, and they sum to 1024.
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. Read the largest numerator straight off the list. It is 449, and it sits at x = −6, well away from both the origin and the far edge.
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. The mean is not 0. |0⟩ is the half of the coin that moves left, and step 3 already showed it taking the larger share, so the whole distribution leans that way.
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. Variance is the mean square minus the square of the mean, and both sums come from the same 11 numerators — no new information is needed.
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. Divide by the classical spread from step 1.
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
Answer

σ_q = 4.8924 against σ_c = 3.1623 — a ratio of 1.5471 — with the quantum peak at p_q(−6) = 0.4385. Now read that variance as a step count. A classical walker's spread is √M, so matching 4.8924 takes M = σ_q² = 23.9, call it 24 steps: 2.4 times the work for the same reach after 10. The classical step count is the square of the spread ratio, and that is the part worth keeping — a 2× advantage in spread is a 4× advantage in steps.

$M = σ_{q}^{2} = 23.9 \approx 24, \frac{M}{N} = (\frac{σ _{q}}{σ _{c}})^{2} = 1.547 1^{2} = 2.394$

References (2)

Insight block 1 — the coined walk this tool steps through: Y. Aharonov, L. Davidovich and N. Zagury, "Quantum random walks." Physical Review A 48(2), 1687–1690, 1993.
And the exponential separation block 1 names: A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, "Exponential algorithmic speedup by a quantum walk." Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 59–68, 2003.

By the 42Math team · Updated 2026-05-22

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

10 steps - 10 steps — asymmetric double peaks already visible
30 steps - 30 steps — quantum spread dramatically wider than classical
50 steps - 50 steps — O(N) quantum spread vs O(√N) classical
Balanced coin - 20 steps, balanced coin — symmetric double-peaked distribution