Discrete-Time Quantum Walks

A classical random walk on a line is simple: at each time step, toss a fair coin; move right on heads or left on tails. The walker's position spreads diffusively — after $t$ steps the standard deviation of the position grows as $\sigma \sim \sqrt{t}$ .

A discrete-time quantum walk replaces that probabilistic coin with a quantum one. The result is profoundly different: the position spreads ballistically, with $\sigma \sim t$ , and the probability distribution develops characteristic peaks near the edges rather than the bell curve of its classical cousin.

The structure of a coined quantum walk

A coined quantum walk operates on a composite Hilbert space

$\mathcal{H} = \mathcal{H}_{\text{coin}} \otimes \mathcal{H}_{\text{position}},$

where the coin register carries a two-level system (one qubit, basis $|0\rangle$ and $|1\rangle$ ) and the position register labels the node or lattice site currently occupied.

Each time step of the walk applies two operations in sequence:

Coin operator $C$ — a unitary acting only on the coin qubit. The standard choice is the Hadamard gate:

$C = H \otimes \mathbf{1}_{\text{pos}}, \qquad H = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}.$

Unlike the classical coin flip, $H$ does not collapse the coin to a definite outcome — it creates a superposition of "move left" and "move right" simultaneously.
Conditional shift operator $S$ — moves the walker on the position register conditioned on the coin state:

$S = |0\rangle\langle 0| \otimes \hat{L} \;+\; |1\rangle\langle 1| \otimes \hat{R},$

where $\hat{L}$ shifts the walker one step to the left and $\hat{R}$ one step to the right. In ket notation on the joint state $|c\rangle|x\rangle$ :

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

One complete step of the quantum walk is the unitary $U = S \cdot (C \otimes \mathbf{1})$ .

Why it is quantum

Consider a walker starting at position $x = 0$ with the coin in $|0\rangle$ . After one step of $H$ followed by $S$ , the joint state is

$U\,|0\rangle|0\rangle = S\,\frac{|0\rangle + |1\rangle}{\sqrt{2}}\,|0\rangle = \frac{|0\rangle|-1\rangle + |1\rangle|+1\rangle}{\sqrt{2}}.$

Both sites $x = -1$ and $x = +1$ are occupied in superposition — the walker is genuinely in two places at once. After the next step, those amplitudes propagate further and begin to interfere with each other when paths cross. It is this constructive and destructive interference that produces the ballistic spreading and the non-Gaussian distribution.

The spreading law

For an unbiased classical walk, after $t$ steps the position distribution has variance $\sigma_{\text{cl}}^2 = t$ . For the Hadamard quantum walk started with a symmetric initial coin state $(|0\rangle + i|1\rangle)/\sqrt{2}$ , the variance grows as

$\sigma_{\text{qw}}^2 \approx \left(1 - \frac{1}{\sqrt{2}}\right)\,t^{\,2},$

giving $\sigma_{\text{qw}} \sim \sqrt{1 - 1/\sqrt{2}}\,t \approx 0.5412\,t$ to leading order — a linear (ballistic) growth compared with the square-root growth of the classical walk. This factor-of- $\sqrt{t}$ advantage underlies the speedups in quantum-walk-based algorithms such as element distinctness and triangle finding.

Coined vs. continuous-time quantum walks

The coined (discrete-time) model described here explicitly stores the coin qubit alongside the position. A second model, the continuous-time quantum walk, has no coin at all: the walker evolves under a Hamiltonian $H_G$ derived from the graph's adjacency matrix, governed by the Schrodinger equation. The two models have different Hilbert-space structures and different computational capabilities; later lessons will explore the continuous-time variant.

For graph search and sampling problems, the discrete-time model is often preferred because the coin provides an extra degree of freedom to tune. By choosing different coin operators — Grover coin, Fourier coin, or parameterized rotations — the walk can be steered toward different behaviours on the same graph.