Coined Quantum Walk

A coined quantum walk is the quantum analogue of a classical discrete-time random walk on a graph. At each step, a classical random walker flips a coin to decide which direction to move. In the quantum version, the “coin flip” is replaced by a unitary operator that creates a superposition of directions, and the walker moves in all directions simultaneously with quantum amplitudes that interfere constructively and destructively. This interference causes the quantum walk to spread across the graph quadratically faster than its classical counterpart: after $t$ steps on a line, the quantum walker’s standard deviation is $O(t)$, compared to $O(\sqrt{t})$ for the classical walker.

The mathematical framework

A coined quantum walk on a graph with maximum degree $d$ operates on a Hilbert space that is the tensor product of two spaces:

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

• Position space $\mathcal{H}_{\text{position}}$: Spanned by basis states $|v\rangle$ for each vertex $v$ of the graph.
• Coin space $\mathcal{H}_{\text{coin}}$: Spanned by basis states $|0\rangle, |1\rangle, \ldots, |d-1\rangle$ corresponding to the possible directions of movement.

Each step of the walk consists of two operations applied in sequence:

1. Coin operator $C$: A unitary acting on the coin space (and possibly conditioned on position). It creates superpositions of directions, analogous to flipping a coin.

2. Shift operator $S$: A unitary that moves the walker along the graph edge corresponding to the coin state. If the coin state is $|j\rangle$ and the walker is at vertex $v$, the shift moves it to the $j$-th neighbor of $v$.

One step of the walk is:

$U = S \cdot (I_{\text{position}} \otimes C)$

After $t$ steps, the state is $U^t |\psi_0\rangle$ where $|\psi_0\rangle$ is the initial state.

Quantum walk on a line

The simplest example is a walk on the integer line $\mathbb{Z}$ with a two-dimensional coin space ($|L\rangle$ and $|R\rangle$ for left and right). The most common coin operator is the Hadamard coin:

$C_H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

The shift operator moves the walker left or right based on the coin state:

$S |x, L\rangle = |x-1, L\rangle, \quad S |x, R\rangle = |x+1, R\rangle$

Starting from $|0, R\rangle$ (position 0, coin state $|R\rangle$), after $t$ steps the probability distribution is asymmetric and concentrated near the edges of the distribution, unlike the Gaussian bell curve of the classical random walk. The standard deviation grows as $\sigma \sim t/\sqrt{2}$, which is linear in $t$, not $\sqrt{t}$ as in the classical case.

This quadratic speedup in spreading is the fundamental advantage of quantum walks and the basis for quantum walk algorithms.

Coin operators

The choice of coin operator significantly affects the walk’s behavior:

• Hadamard coin: $H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$. Produces an asymmetric distribution on the line (biased toward one direction depending on the initial coin state).

• Grover coin (for $d$-regular graphs): $G = \frac{2}{d}\mathbf{J} - I$ where $\mathbf{J}$ is the all-ones matrix. This is the $d$-dimensional generalization of the “fair” coin and produces a symmetric walk on regular graphs. It is closely related to Grover’s algorithm: Grover’s search can be understood as a quantum walk on a specific graph using the Grover coin.

• DFT coin: The discrete Fourier transform matrix. Useful for walks on cycles and groups with known Fourier structure.

Algorithmic applications

Coined quantum walks are the basis of several quantum algorithms:

Grover search as a quantum walk: Grover’s algorithm can be recast as a quantum walk on a “Johnson graph” or an abstract search graph. The quadratic speedup of Grover search ($O(\sqrt{N})$ queries vs $O(N)$ classically) corresponds directly to the quadratic speedup of quantum walk spreading.

Element distinctness: Ambainis’s algorithm for determining whether a list of $N$ elements contains duplicates runs in $O(N^{2/3})$ queries, beating the classical lower bound of $\Omega(N)$. It uses a quantum walk on the Johnson graph.

Spatial search: Finding a marked vertex on a graph. On a 2D grid of $N$ vertices, a quantum walk finds the marked vertex in $O(\sqrt{N} \log N)$ steps, nearly matching the $O(\sqrt{N})$ lower bound.

Graph isomorphism testing: Quantum walks have been explored as a tool for distinguishing non-isomorphic graphs, though no exponential speedup has been proven for the general problem.

Coined vs continuous-time quantum walks

There are two main formulations of quantum walks:

• Coined (discrete-time): Uses a coin operator and proceeds in discrete steps, as described above. Requires an explicit coin space.
• Continuous-time: Evolves under a Hamiltonian proportional to the adjacency matrix of the graph: $|\psi(t)\rangle = e^{-iAt}|\psi(0)\rangle$. No coin space needed, but the physics is different.

The two formulations are related but not equivalent. Coined walks are generally more natural for algorithmic applications where discrete query complexity matters. Continuous-time walks arise more naturally in physics (e.g., quantum transport in biological systems).

Why it matters for learners

Coined quantum walks provide an intuitive framework for understanding quantum speedups. The core mechanism, interference between paths, is visible in the simplest 1D example: the walker takes all paths simultaneously, and constructive interference at the edges of the distribution causes the quadratic speedup. This same mechanism, amplified and directed by clever graph constructions and coin choices, underlies some of the most important quantum algorithms. Understanding coined quantum walks also builds intuition for why quantum computers are not simply “trying all answers at once” (a common misconception) but rather exploiting the wave-like interference of quantum amplitudes.

See also

• Grover’s Algorithm
• Superposition
• Entanglement
• Quantum Circuit