The Coin Operator

In a classical random walk a coin flip at each step decides whether to move left or right. The quantum walk replaces that coin flip with a unitary operator acting on a dedicated coin qubit. The coin operator does not collapse the direction to a single outcome; instead it spreads the walker into a superposition of left and right before the shift step moves it.

The coin register

The coin qubit encodes the walker's direction. We adopt the convention

$|0\rangle \equiv |\!\leftarrow\rangle, \qquad |1\rangle \equiv |\!\rightarrow\rangle.$

A walker that has just started is initialised in $|0\rangle$ — pointing left. Applying a coin operator then creates a superposition:

$C\,|0\rangle = \alpha\,|0\rangle + \beta\,|1\rangle.$

The subsequent shift step reads this superposition and moves the position register coherently in both directions at once.

The Hadamard coin

The most widely studied coin is the Hadamard coin $C = H$ :

H|1\rangle = \tfrac{1}{\sqrt{2}}\!\left(|0\rangle - |1\rangle\right).$$ Starting from $|0\rangle$, one application gives an equal superposition of left and right with identical magnitudes $\tfrac{1}{\sqrt{2}}$ and a relative phase of $+1$ between the two terms. Starting from $|1\rangle$, the same gate gives an equal superposition but with a relative phase of $-1$. That phase difference is invisible in a single measurement but accumulates over many steps and produces the characteristic interference pattern of the quantum walk distribution. <Callout type="tip"> Any $2\times 2$ unitary matrix is a valid coin. The Grover coin, the DFT coin, and biased coins (e.g., a rotation $R_y(\theta)$) all produce different spreading and interference behaviours. The Hadamard coin is special because it maximises the spreading speed along a line. </Callout> ## One walk step A single step of the discrete-time coined quantum walk decomposes into exactly two operations applied in sequence: 1. **Coin toss** — apply $C$ to the coin qubit. After this step the coin is in a superposition; the position has not changed yet. 2. **Conditional shift** — move the position register left if the coin is $|0\rangle$ and right if the coin is $|1\rangle$. In circuit form the coin toss is simply $H$ (or whichever unitary you choose) acting on a single qubit. The entire complexity of the walk comes from repeating this two-part step many times and letting the position register accumulate interference. ## Try it The coin qubit starts in $|0\rangle$. Apply the Hadamard coin so the walker is in an equal superposition of left and right before the shift. The grader checks the **statevector** after the coin toss — the correct state is $\tfrac{1}{\sqrt{2}}\!\left(|0\rangle + |1\rangle\right)$. <RunnableExample /> After pressing **Run** you should see both amplitudes equal to $\approx 0.707 = \tfrac{1}{\sqrt{2}}$ and both probabilities equal to $0.5$. This balanced superposition is exactly what makes quantum walks spread quadratically faster than classical random walks along a line.