Walks for Search

Quantum walk algorithms turn the ballistic spreading of a quantum walk into a directed search. Instead of spreading uniformly across a graph, the walk is designed so that amplitude accumulates at a specially marked vertex — the target node. For the complete graph on $N$ nodes, this approach reproduces Grover's algorithm, achieving the quadratic speedup over classical unstructured search.

Searching on the complete graph

Consider the complete graph $K_N$ : every pair of nodes is connected, so every node is reachable from every other node in a single step. We model the walker's position using $n = \lceil \log_2 N \rceil$ position qubits. For $N = 4$ nodes, two qubits suffice and the four nodes are labeled $|00\rangle, |01\rangle, |10\rangle, |11\rangle$ .

One marked node $|m\rangle$ is distinguished. The goal is to concentrate the walker's probability on $|m\rangle$ as quickly as possible.

The two-part walk step

Each walk step consists of two unitaries applied in sequence:

Oracle — applies a phase flip to the marked node only:

$O = I - 2|m\rangle\langle m|.$

For the marked node $|m\rangle = |11\rangle$ and two position qubits, $O$ is realized by a single controlled- $Z$ gate:

$CZ\,|11\rangle = -|11\rangle, \qquad CZ\,|xy\rangle = |xy\rangle \text{ for } |xy\rangle \neq |11\rangle.$
Grover coin (diffusion operator) — reflects every amplitude about the mean of the uniform superposition $|s\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ :

$D = 2|s\rangle\langle s| - I.$

In circuit form, $D = H^{\otimes n}\,(2|0\rangle\langle 0| - I)\,H^{\otimes n}$ . The inner phase-flip $2|0\rangle\langle 0| - I$ is realized as $-X^{\otimes n}\,CZ\,X^{\otimes n}$ (since $X^{\otimes n}\,CZ\,X^{\otimes n} = I - 2|0\rangle\langle 0|$ ), giving the two-qubit coin circuit $H^{\otimes n}\,X^{\otimes n}\,CZ\,X^{\otimes n}\,H^{\otimes n}$ , which equals $-D$ and differs from $D$ only by a global phase that does not affect measurement outcomes.

Why one step suffices for $N = 4$

Starting from the equal superposition $|s\rangle$ (all four nodes equally likely), the geometry of the two reflections determines how quickly the state rotates toward $|m\rangle$ . The initial overlap between $|s\rangle$ and $|m\rangle$ is $\langle m|s\rangle = \frac{1}{\sqrt{N}}$ . The angle between $|s\rangle$ and the marked-state subspace is

$\theta = \arcsin\!\left(\frac{1}{\sqrt{N}}\right).$

Each walk step rotates the state by $2\theta$ toward $|m\rangle$ . After $k$ steps the overlap with $|m\rangle$ is $\sin^2\!\left((2k+1)\theta\right)$ . To reach probability 1 we need

$k = \left\lfloor \frac{\pi}{4\theta} \right\rfloor \approx \frac{\pi}{4}\sqrt{N}.$

For $N = 4$ we get $\theta = \arcsin(1/2) = \pi/6$ , so $k = \lfloor \pi/(4 \cdot \pi/6)\rfloor = \lfloor 3/2 \rfloor = 1$ . A single step is enough to land exactly on $|11\rangle$ with probability 1.

The full circuit

For $N = 4$ and target $|m\rangle = |11\rangle$ , the search circuit is:

$\underbrace{H \otimes H}_{\text{superposition}} \;\cdot\; \underbrace{CZ}_{\text{oracle}} \;\cdot\; \underbrace{(H \otimes H)(X \otimes X)\,CZ\,(X \otimes X)(H \otimes H)}_{\text{Grover coin}}.$

After this single walk step, measuring yields $|11\rangle$ with certainty.

Try it

Implement the four-step walk search circuit: prepare the uniform superposition, apply the oracle, apply the Grover coin, then measure. The grader checks the output distribution — all probability should appear on node $|11\rangle$ (bitstring 11).

Run your code to see the quantum state.

After running, open the Probabilities tab to see a single bar at outcome 11 with height 1. That is the quantum walk delivering the marked node with certainty in one step.