Classical Random Walks

Before studying how a quantum walk differs from its classical counterpart, it is worth understanding exactly what a classical random walk is and what it can — and cannot — do efficiently.

The simplest random walk: a line

Imagine a particle sitting at position $x = 0$ on an integer number line. At each discrete time step it flips a fair coin: heads it moves right ( $x \to x + 1$ ), tails it moves left ( $x \to x - 1$ ). After $t$ steps the position $X_t$ is a random variable.

Because each step is $\pm 1$ with equal probability, the expected displacement is zero:

$\mathbb{E}[X_t] = 0.$

The variance grows linearly with time. Each step contributes an independent variance of 1, so

$\text{Var}(X_t) = t, \qquad \sigma(X_t) = \sqrt{t}.$

This $\sqrt{t}$ spread is the hallmark of diffusive transport. It means the walker typically travels only $O(\sqrt{t})$ from the origin in $t$ steps — slow compared with $O(t)$ for ballistic (straight-line) motion.

Probability distribution after many steps

By the Central Limit Theorem, the distribution of $X_t$ for large $t$ converges to a Gaussian:

$P(X_t = k) \approx \frac{1}{\sqrt{2\pi t}} \exp\!\left(-\frac{k^2}{2t}\right),$

centered at the origin, with width $\sim \sqrt{t}$ . The probability spreads outward smoothly and symmetrically, with the peak remaining at the starting point throughout.

Hitting times and cover times

Two quantities that matter when random walks are used as algorithms:

Hitting time $H(u, v)$ : the expected number of steps to reach vertex $v$ starting from vertex $u$ . On a path of $n$ nodes, $H(0, n) = O(n^2)$ — quadratically slow.
Cover time: the expected steps to visit every vertex at least once. For an $n$ -node path, this is $O(n^2)$ as well.

These quadratic scalings motivate the search for faster walks. On a complete graph of $n$ nodes the cover time is $O(n \log n)$ , and on a $d$ -dimensional hypercube it is $O(n \log n)$ as well — but even the best classical random walks cannot escape the $\sqrt{t}$ diffusive envelope entirely.

Why this matters for quantum computing

A quantum walk replaces the classical coin flip with a unitary coin operator and propagates amplitude coherently rather than probability incoherently. The key consequence is that the spread of the quantum walker grows linearly with time — $O(t)$ — rather than $\sqrt{t}$ . This quadratic speedup in the spreading rate translates into algorithmic speedups for tasks like element distinctness, triangle finding, and spatial search on graphs.

The next lessons build the quantum walk step by step, starting with the coined discrete-time model that mirrors the structure of the classical walk described here.