The Shift Operator

A discrete-time quantum walk alternates two operations: first a coin toss (the coin operator, usually a Hadamard), then a conditional shift that moves the walker left or right depending on the coin's state. This lesson focuses on the shift.

The conditional shift

Label the walker's direction qubit as $|d\rangle$ and its position as $|x\rangle$ . The conditional shift $S$ satisfies

$S\,|d\rangle\,|x\rangle = |d\rangle\,|x + (-1)^{1-d} \bmod N\rangle,$

meaning: move right ( $x \to x+1$ ) when $d = 1$ , and left ( $x \to x-1$ ) when $d = 0$ .

On a line of $N = 4$ positions we need 2 bits to label positions $0, 1, 2, 3$ . The coin qubit $q_0$ and position register $(q_1, q_2)$ give a 3-qubit system. The right-shift rule $(d=1: x \to x+1 \bmod 4)$ is a controlled binary increment:

$S_{\text{right}}: \quad q_1 \leftarrow q_1 \oplus (q_0 \land q_2), \qquad q_2 \leftarrow q_2 \oplus q_0.$

The first line propagates the carry (flip the high bit only when both the coin and the low bit are $1$ ); the second line always flips the low bit when the coin is $1$ . Together they increment the position by $1 \bmod 4$ whenever $q_0 = 1$ .

In circuit notation this is a Toffoli gate (CCX) followed by a CNOT (CX):

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

Concrete example

Start with coin $= 1$ and position $= 1$ (binary $01$ ), i.e. the state $|1\rangle|01\rangle$ :

$|1\,0\,1\rangle \xrightarrow{\text{CCX}(0,2,1)} |1\,1\,1\rangle \xrightarrow{\text{CX}(0,2)} |1\,1\,0\rangle = |1\rangle|10\rangle.$

Position $01_2 = 1$ has become $10_2 = 2$ : the walker moved one step to the right.

Conditionality is the key

The shift is coherent: when the coin is in superposition $\tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ , the walker's position entangles with the coin and spreads in both directions simultaneously. Classical random walks pick one direction per step; quantum walks create a superposition of paths, leading to the quadratically faster spreading observed in later lessons.

Try it

The circuit below starts in $|1\rangle|01\rangle$ (coin $= 1$ , position $= 1$ ). Complete the conditional shift so the final state is $|1\rangle|10\rangle$ (position $= 2$ ). The grader checks the full statevector.

Run your code to see the quantum state.

After pressing Run, the statevector should show a single amplitude of $1$ on the basis state $|110\rangle = q_0 q_1 q_2$ (with qubit 0 most significant), confirming the walker moved exactly one step to the right.