Checkpoint: Simulate a Quantum Walk

This checkpoint consolidates everything from Module 8. You will build a complete one-step discrete-time quantum walk from scratch: a coin toss followed by a coherent conditional shift. The result will show the walker's position spread in a single step — the hallmark of quantum ballistic transport.

Recap: the structure of one walk step

A discrete-time quantum walk on a line operates on a joint register

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

A single step $U = S \cdot (H \otimes I_{\text{pos}})$ applies two operations in sequence.

Step 1 — Coin toss. The Hadamard gate acts on the coin qubit alone:

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

After the coin toss the walker is in a superposition of moving left and moving right. No position update has happened yet.

Step 2 — Conditional shift. The shift operator $S$ moves the position register left when the coin reads $|0\rangle$ and right when it reads $|1\rangle$ :

$S\,|d\rangle\,|x\rangle = |d\rangle\,|x + 2d - 1 \bmod N\rangle.$

For $d = 0$ this decrements the position; for $d = 1$ it increments. On a 4-node cycle ( $N = 4$ , two position bits $q_1 q_2$ ) both operations are implemented with a Toffoli and a CNOT, each conditioned on the coin qubit $q_0$ .

What the circuit does, step by step

Start with coin $|0\rangle$ at position $1 = |01\rangle$ , so the initial joint state is $|001\rangle$ .

After the Hadamard coin toss:

$|001\rangle \xrightarrow{H \otimes I} \tfrac{1}{\sqrt{2}}\bigl(|001\rangle + |101\rangle\bigr).$

The $|0\rangle$ branch still has position $|01\rangle$ (will move left); the $|1\rangle$ branch still has position $|01\rangle$ (will move right).

The conditional decrement moves the $|0\rangle$ branch from position $1$ to position $0$ :

$|0\rangle|01\rangle \xrightarrow{\text{decrement}} |0\rangle|00\rangle.$

The conditional increment moves the $|1\rangle$ branch from position $1$ to position $2$ :

$|1\rangle|01\rangle \xrightarrow{\text{increment}} |1\rangle|10\rangle.$

The final state before measurement is:

$\tfrac{1}{\sqrt{2}}\bigl(|0\rangle|00\rangle + |1\rangle|10\rangle\bigr) = \tfrac{1}{\sqrt{2}}\bigl(|000\rangle + |110\rangle\bigr).$

Measuring all three qubits yields bitstring 000 (coin $= 0$ , position $= 0$ ) and bitstring 110 (coin $= 1$ , position $= 2$ ), each with probability $\tfrac{1}{2}$ .

Encoding the shift as a controlled binary increment/decrement

For a 2-bit position register, a cyclic increment adds 1 modulo 4. The binary ripple-carry circuit is:

$q_1 \leftarrow q_1 \oplus (q_0 \land q_2), \qquad q_2 \leftarrow q_2 \oplus q_0.$

Reading left to right: first propagate the carry into the high bit with $\text{CCX}(q_0, q_2, q_1)$ , then flip the low bit with $\text{CX}(q_0, q_2)$ . Both gates trigger only when $q_0 = 1$ , so the operation is controlled on the coin.

A cyclic decrement reverses the carry order — first flip the low bit, then propagate the carry — and wraps the result in $X$ gates on the coin:

$X(q_0)\;\cdot\;\text{CX}(q_0, q_2)\;\cdot\;\text{CCX}(q_0, q_2, q_1)\;\cdot\;X(q_0).$

Flipping the coin converts "active when $q_0 = 1$ " into "active when $q_0 = 0$ ", which is precisely the left-move condition.

Try it

Complete the circuit: add the coin toss, the conditional decrement, and the conditional increment. Measure all qubits. The grader checks the output distribution — you should see equal probability on bitstrings 000 and 110 and zero probability everywhere else.

Run your code to see the quantum state.

After pressing Run, open the Probabilities tab. Two equal bars at 000 and 110 confirm that the walker has spread from position 1 to positions 0 and 2 in a single coherent step. This coherent superposition is what enables the quantum walk's ballistic spreading over many steps — a dramatic speedup over the diffusive ( $\sigma \propto \sqrt{t}$ ) spreading of its classical counterpart.