Ballistic Spreading

The most striking difference between a classical random walk and a quantum walk is how fast the walker spreads from its starting position. Classically the spread is diffusive — the standard deviation grows as $\sqrt{t}$ . A quantum walk spreading is ballistic — the standard deviation grows linearly with $t$ . This quadratic speedup in spreading rate is the engine behind several quantum algorithmic advantages.

Classical diffusion: a recap

In a classical random walk on a line, each step adds an independent $\pm 1$ displacement. Writing step $i$ as $S_i \in \{-1, +1\}$ with equal probability, the position after $t$ steps is

$X_t = S_1 + S_2 + \cdots + S_t.$

Because the steps are independent and identically distributed with $\mathbb{E}[S_i] = 0$ and $\text{Var}(S_i) = 1$ , the variance of $X_t$ is

$\text{Var}(X_t) = \sum_{i=1}^{t} \text{Var}(S_i) = t,$

giving a standard deviation $\sigma_{\text{classical}}(t) = \sqrt{t}$ . The probability distribution converges to a Gaussian of width $\sim \sqrt{t}$ centered at the origin.

Quantum walk: ballistic growth

A discrete-time quantum walk on a line uses a two-dimensional coin register to keep track of direction. The state of the system at step $t$ is

$|\psi_t\rangle = \sum_{x,c} \alpha_{x,c}^{(t)}\, |x\rangle \otimes |c\rangle,$

where $|x\rangle$ is the position and $|c\rangle \in \{|\uparrow\rangle, |\downarrow\rangle\}$ is the coin state. Each step applies a unitary coin (e.g. the Hadamard coin $H_{\text{coin}}$ ) followed by a conditional shift:

$S\,|\,x, \uparrow\rangle = |\,x+1, \uparrow\rangle, \qquad S\,|\,x, \downarrow\rangle = |\,x-1, \downarrow\rangle.$

Because the overall evolution is unitary, the amplitudes $\alpha_{x,c}^{(t)}$ interfere coherently rather than mixing probabilistically. The two counter-propagating wave packets — moving left and right — develop a systematic phase relationship that causes constructive interference near the edges of the reachable region and destructive interference near the center.

The $\sigma \sim t$ scaling

For a Hadamard-coined walk starting in the symmetric coin superposition

$|0\rangle \otimes \tfrac{1}{\sqrt{2}}(|\uparrow\rangle + i|\downarrow\rangle),$

the standard deviation of the position distribution after $t$ steps satisfies (Kempe 2003):

$\sigma_{\text{quantum}}(t) \approx \frac{t}{\sqrt{2}}.$

This is $O(t)$ — linear rather than $\sqrt{t}$ . Comparing the two:

| Walk type | $\sigma$ after $t$ steps | Asymptotic shape | |-----------|--------------------------|------------------| | Classical (fair coin) | $\sqrt{t}$ | Gaussian (bell curve) | | Quantum (Hadamard coin) | $\approx t/\sqrt{2}$ | Two-peaked, flat in center |

The factor $1/\sqrt{2}$ comes from the effective "speed" of the quantum walk; the peak probability concentrates near $x \approx \pm t/\sqrt{2}$ , not at the origin.

Shape of the quantum distribution

While a classical walk gives a symmetric bell curve with a maximum at $x = 0$ , the quantum distribution is almost the opposite: it has two pronounced peaks near the extremes $x \approx \pm t/\sqrt{2}$ and a relatively flat (but nonzero) middle. This unusual shape is a direct consequence of quantum interference:

Constructive interference near the edges: probability amplitude arriving from both coin states adds.
Destructive interference near the center: the two propagating components partially cancel.

The exact profile depends on the initial coin state. Choosing the symmetric state above produces a roughly symmetric double-peak; an asymmetric coin start (e.g. $|\uparrow\rangle$ alone) shifts both peaks toward one side.

Why it matters algorithmically

Ballistic spreading gives quantum walks a quadratic advantage over classical random walks for graph-search tasks. On a path of $n$ nodes:

A classical random walk needs $O(n^2)$ steps to travel from one end to the other (hitting time scales as $n^2$ ).
A quantum walk traverses the same path in $O(n)$ steps, because its spread reaches distance $n$ after only $O(n)$ steps rather than $O(n^2)$ .

This speedup carries over to higher-dimensional grids and irregular graphs, and underpins quantum speedups for element distinctness (Ambainis 2004) and spatial search (Childs and Goldstone 2004).

Comparing the two in numbers

After $t = 100$ steps:

Classical: $\sigma = \sqrt{100} = 10$ , so the walker is typically within $\pm 10$ of the origin.
Quantum: $\sigma \approx 100/\sqrt{2} \approx 70.7$ , so the quantum walker has spread $\approx 7\times$ farther in the same number of steps.

The advantage grows with $t$ : after $t = 10{,}000$ steps the classical spread is $100$ , while the quantum spread is $\approx 7{,}071$ — roughly $70\times$ wider.