Walk on a Line

A quantum walk is the quantum analogue of a classical random walk. Where a classical walker flips a coin to decide left or right, a quantum walker applies a unitary to its coin register and then performs a coherent conditional shift — keeping the superposition intact so that both directions evolve in parallel and their amplitudes interfere.

The classical picture

Start a classical random walker at position $x = 0$ . At each step flip a fair coin: heads, move to $x-1$ ; tails, move to $x+1$ . After $t$ steps the position probability distribution is a binomial centred at 0 with standard deviation $\sigma_{\text{cl}} = \sqrt{t}$ . The walk diffuses slowly.

The quantum walk on a line

The Hilbert space is the tensor product of a coin register and a position register:

$|\psi\rangle \in \mathcal{H}_{\text{coin}} \otimes \mathcal{H}_{\text{pos}}.$

A single step consists of two operations applied in sequence.

Coin operator $C$ : a unitary on the coin register alone. The standard choice is the Hadamard:

$H|0\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle), \qquad H|1\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle).$

Shift operator $S$ : moves the walker left when the coin reads $|0\rangle$ and right when it reads $|1\rangle$ :

$S = \sum_{x} \bigl(|0\rangle\langle 0| \otimes |x-1\rangle\langle x| + |1\rangle\langle 1| \otimes |x+1\rangle\langle x|\bigr).$

One full step is $U = S(C \otimes I_{\text{pos}})$ .

Interference leads to ballistic spreading

Because the walker stays in superposition, the amplitudes for different positions can add constructively or destructively. Starting with coin $|0\rangle$ at position $x = 0$ , the probability distribution after $t$ steps has a characteristic two-peaked shape with tails near $\pm t/\sqrt{2}$ . The standard deviation grows as

$\sigma_{\text{qu}} \approx \frac{t}{\sqrt{2}},$

which is linear in $t$ rather than $\sqrt{t}$ . This quadratic speed-up over classical diffusion is the reason quantum walks appear as subroutines in several quantum algorithms (element distinctness, graph search, NAND-formula evaluation).

Encoding for a small circuit

To build an exact circuit we encode a finite segment of the line. Use a 2-qubit position register ( $q_1 q_2$ , with $q_1$ as the most significant bit) for positions $\{0, 1, 2, 3\}$ , and a single coin qubit $q_0$ . Three qubits in total.

Starting at the centre position $1 = |01\rangle$ with coin $|0\rangle$ , one step proceeds:

Coin toss: $H$ on $q_0$ .
Conditional decrement (move left when coin $= |0\rangle$ ): invert $q_0$ , apply the controlled-decrement circuit $\text{CX}(q_0, q_2);\, \text{CCX}(q_0, q_2, q_1)$ , then invert $q_0$ again. The binary borrow-ripple decrement on $q_1 q_2$ triggers only when $q_0 = 1$ after the flip, i.e., originally $q_0 = 0$ . Note the order: CX before CCX (the LSB is flipped first so that the carry check sees the updated LSB, implementing $-1$ rather than $+1$ ).
Conditional increment (move right when coin $= |1\rangle$ ): apply $\text{CCX}(q_0, q_2, q_1);\, \text{CX}(q_0, q_2)$ directly (no flips needed).

After the coin toss the state is $\tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|01\rangle$ . The decrement takes the $|0\rangle$ branch from position $|01\rangle$ to $|00\rangle$ , and the increment takes the $|1\rangle$ branch from $|01\rangle$ to $|10\rangle$ . The final state before measurement is

$\frac{1}{\sqrt{2}}\bigl(|0\rangle|00\rangle + |1\rangle|10\rangle\bigr).$

Measuring all three qubits yields bitstrings 000 and 110 with equal probability $\tfrac{1}{2}$ — the walker has spread from the centre to positions 0 and 2.

Try it

Complete the one-step walk circuit. The grader checks the output distribution — you should see equal weight on the two displaced positions.

Run your code to see the quantum state.