12.9 Grover’s search algorithm

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §12.9–12.9.1. Original prose — no Qiskit oracle listing dumps. Continues 12.8b. Labs: 12.9b.

Classical lookup of one marked index among $N$ unsorted items costs $O(N)$ queries in the worst case. Grover’s algorithm finds a marked item with $O(\sqrt N)$ oracle calls on a quantum computer.

Database toy model

Suppose $N=16=2^4$ entries $(j,V_j)$ — e.g. $j=8$ stores $V=90$. Searching needs 4 qubits. Goal: amplify the computational-basis state $|i\rangle$ that encodes the desired index.

Uniform start + oracle + diffuser

Initialize $|0\rangle^{\otimes n}$, apply $H^{\otimes n}$ for a uniform superposition, then iterate oracle + diffuser. Pick the oracle phase-mark, the diffuser $U_\psi$, and the $\sim\pi\sqrt N/4$ iteration count among lookalikes.

For $|15\rangle=|1111\rangle$, a multi-controlled $Z$ sandwiched by Hadamards on the target line implements the mark. Other indices: wrap selected qubits with $X$ so the all-$1$ pattern of the CCCZ hits the desired bitstring (e.g. $|9\rangle=|1001\rangle$).

Geometrically the diffuser sends each amplitude $\alpha_k$ to $2\bar\alpha-\alpha_k$. One Grover operator $G=U_\psi\mathcal O$ boosts the marked amplitude before over-rotation.

Lab: wire Grover skeleton

Simulator vs hardware

Ideal simulators show a sharp peak (e.g. $|1001\rangle$ for $i=9$). Physical backends smear that peak — noise, not a failure of the algorithm’s math.

Exercise idea: mark $j=8$ ($V=90$) and check the measured bitstring decodes to $8$.

Takeaway

Piece	Role
$H^{\otimes n}$	uniform superposition
Oracle $\mathcal O$	phase-flip $
Diffuser $U_\psi$	invert about mean
$\sim\pi\sqrt N/4$ rounds	amplify then measure

Quiz

Grover

1 / 3

The oracle marks the answer by…

Pick an answer to see if you are right.

Next: 12.9b Grover labs.