QCQI - Chapter 8: Grover Search & Amplitude Amplification

Learning Objectives¶

• Oracle + diffuser $\Rightarrow$ rotation in 2D.

• Optimal iterate count and overshoot.

• Amplitude amplification and estimation.

Grover Geometry¶

$|s\rangle=\sin\theta|\beta\rangle+\cos\theta|\alpha\rangle$, $\sin\theta=\sqrt{M/N}$.

$G=DO_f$ rotates by $2\theta$ per iterate.

Eureka! Quadratic speedup from planar rotations.

Circuits¶

Oracle: conjugated multi-controlled-$Z$; Diffuser: $H^{\otimes n}X^{\otimes n}\mathrm{CCZ}X^{\otimes n}H^{\otimes n}$ (for $n=3$).

Eureka! Reflect about $|s\rangle$ via Hadamards and a single CCZ.

Amplitude Amplification¶

$Q=-A S_0 A^\dagger S_f$; same rotation picture.

Amplitude estimation uses QPE on $Q$ to learn $\theta$.

Schematic: Iterate $G = D\,O_f$ (concept)¶

Hands-on Notebook¶

Companion notebook (multi-backend): L10_QCQI_Ch08_Grover_and_Amplitude_Amplification

Set backend in the first cell to cirq, pennylane, braket, pyquil, or qiskit.

Mini-Lab¶

• Plot $P_r$ vs. $r$ for $n=3$.

• Try $M=2$ solutions and compare with theory.

• Replace $H^{\otimes n}$ by biased $A$ and check rotation.