Discrete-time quantum walk on a line

A coined discrete-time quantum walk on the integer line pairs a 2-dimensional coin register with a position register. Each step applies a coin operator $C$ (Hadamard, by default) to the coin, then a conditional shift $S$ that moves the position by $-1$ if the coin reads $|0\rangle$ and $+1$ if it reads $|1\rangle$ — applied coherently, so all branches persist and can later interfere.

Long-run behavior. After $t$ steps, the position distribution of this walk spreads with standard deviation $\sigma \propto t$ (ballistic spreading), in contrast to a classical random walk's $\sigma \propto \sqrt t$ (diffusive spreading) — a quadratic gain in spreading rate that several quantum-walk-based search and graph algorithms exploit (Aharonov, Ambainis, Kempe, Vazirani, 2001).

Small worked instance. Start at position $0$ with coin $|0\rangle$. Step 1: $H$ on the coin gives $\tfrac1{\sqrt2}(|0\rangle+|1\rangle)\otimes|0\rangle_{\text{pos}}$; the shift then gives $\tfrac1{\sqrt2}|0,-1\rangle + \tfrac1{\sqrt2}|1,+1\rangle$ (coin, position) — each position $\pm1$ with probability $1/2$, matching a classical single step.

Step 2 applies $H$ to the coin in each branch: $H|0\rangle=\tfrac1{\sqrt2}(|0\rangle+|1\rangle)$, $H|1\rangle=\tfrac1{\sqrt2}(|0\rangle-|1\rangle)$, giving

$$\tfrac12|0,-1\rangle+\tfrac12|1,-1\rangle+\tfrac12|0,+1\rangle-\tfrac12|1,+1\rangle,$$

then the shift moves each term ($|0,x\rangle\to|0,x-1\rangle$, $|1,x\rangle\to|1,x+1\rangle$):

$$\tfrac12|0,-2\rangle+\tfrac12|1,0\rangle+\tfrac12|0,0\rangle-\tfrac12|1,+2\rangle.$$

Reading off probabilities: $P(-2)=1/4$; at position $0$ the two contributions carry different coin states so they do not interfere, giving $P(0)=(1/2)^2+(1/2)^2=1/2$; and $P(+2)=1/4$. At this short length the result numerically coincides with the classical 2-step binomial walk — the quantum/classical divergence (from interference between equal-coin-state paths reaching the same site) only becomes visible from step 3 onward, which is worth stating honestly rather than implying an advantage is visible after 2 steps.