QCQI – Chapter 8 Detailed Summary: Grover Search & Amplitude Amplification

Learning Objectives¶

• Implement the Grover iterate $G = D\,O_f$ where $O_f$ marks “good” states and $D$ is diffusion.

• Explain the two-dimensional geometry (good/bad subspace), derive the optimal iteration count, and quantify success.

• Generalize to amplitude amplification with arbitrary state-preparation $A$ and reflection operators.

• Understand amplitude estimation / quantum counting at a high level.

• Build small oracles and diffusion circuits and explore multiple-solution cases.

Problem Statement & Oracle¶

Unstructured search: given $f:\{0,\dots,N-1\}\to\{0,1\}$ with $M=\left|f^{-1}(1)\right|$, find any $x$ with $f(x)=1$.

Oracle $O_f$ acts as a phase flip on marked basis states: $O_f|x\rangle = (-1)^{f(x)}|x\rangle.$

Eureka! Phase oracles are lossless: a global phase on marked states becomes actionable after interference via the diffuser.

State Decomposition & Geometry¶

Let $S$ (good) have size $M$; define $|\alpha\rangle=\frac{1}{\sqrt{N-M}}\sum_{x\notin S}|x\rangle$ and $|\beta\rangle=\frac{1}{\sqrt{M}}\sum_{x\in S}|x\rangle$. Initialize $|s\rangle=\frac{1}{\sqrt{N}}\sum_x |x\rangle=\sin\theta\,|\beta\rangle+\cos\theta\,|\alpha\rangle$ with $\sin\theta=\sqrt{M/N}$.

Eureka! Grover is a planar rotation in span$\{|\alpha\rangle,|\beta\rangle\}$ by angle $2\theta$ each iterate.

Grover Iterate¶

Oracle $O_f$ reflects across $|\alpha\rangle$ (phase flip on $|\beta\rangle$). Diffusion $D=2|s\rangle\!\langle s|-I$ reflects across $|s\rangle$. Therefore $G=DO_f$ is a rotation by $2\theta$. After $r$ iterations, $G^r|s\rangle=\sin((2r+1)\theta)|\beta\rangle+\cos((2r+1)\theta)|\alpha\rangle.$

Optimal count. Choose $r^\star=\left\lfloor \frac{\pi}{4\theta}-\frac12\right\rfloor \approx \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rfloor$. Success $\approx \sin^2((2r^\star+1)\theta)\gtrsim 1- O(M/N)$.

Eureka! Quadratic speedup: $\Theta(\sqrt{N/M})$ queries vs. classical $\Theta(N/M)$.

Diffusion Operator Circuits¶

Using $|s\rangle=H^{\otimes n}|0^n\rangle$, $D = H^{\otimes n}\,(2|0\rangle\!\langle 0|-I)\,H^{\otimes n}.$ Implement $2|0\rangle\!\langle 0|-I$ by an $n$-controlled-$Z$ (phase flip on $|0^n\rangle$), e.g., for $n=3$: $H$–CCX–$H$ on the last qubit with appropriate $X$ conjugations to retarget.

Eureka! “Reflect about $|s\rangle$” $\iff$ reflect about $|0^n\rangle$ in the Hadamard basis.

Multiple Solutions & Overshoot¶

With $M>1$, $\theta$ increases; over-iterating rotates past the target. Use the same $r^\star$ formula with $M$ known or guessed (or use fixed-point search variants to avoid overshoot).

Amplitude Amplification (General Form)¶

Given $A|0\rangle = \sin\theta\,|\beta\rangle+\cos\theta\,|\alpha\rangle$ (any preparation), define reflections $S_0 = I - 2|0\rangle\!\langle 0|,\qquad S_f=I-2\Pi_{\text{good}}.$ Then the iterate $Q = -A S_0 A^\dagger S_f$ rotates by $2\theta$ in the same two-dimensional subspace.

Eureka! Grover is just $A=H^{\otimes n}$ with the good-subspace projector defined by $f$.

Amplitude Estimation & Counting (Idea)¶

Combine QPE with the Grover iterate $Q$ to estimate $\theta$ (or $M$) without scanning $r$: phase of $Q$’s eigenvectors is $\pm 2\theta$. Quantum counting estimates $M\approx N\sin^2\theta$.

Worked Nuggets¶

Mark a single item. Conjugate an $n$-controlled-$Z$ with $X$ on bits where the target has 0.

Diffuser for $n=3$. $H^{\otimes 3}\, X^{\otimes 3}\, \mathrm{CCZ}\, X^{\otimes 3}\, H^{\otimes 3}$.

General success curve. $P_r=\sin^2((2r+1)\theta)$; the first maximum is near $r^\star$.

Pseudo-code Aids¶

Pseudocode — Grover (one marked string, $n$ small)

Input: $n$, marked bitstring $m$, iterations $r$ Prepare $|s\rangle=H^{\otimes n}|0^n\rangle$ Repeat $r$ times: Oracle: for each bit $j$ with $m_j=0$ apply $X$ on $j$; apply $n$-controlled-$Z$; undo the $X$’s Diffuser: apply $H^{\otimes n}$; $X^{\otimes n}$; $n$-controlled-$Z$; $X^{\otimes n}$; $H^{\otimes n}$ Measure in computational basis

Pseudocode — Optimal iteration estimate

Input: $N=2^n$, guess $M$ $\theta=\arcsin\sqrt{M/N}$; $r^\star=\left\lfloor \frac{\pi}{4\theta}-\frac12\right\rfloor$

Pseudocode — Amplitude amplification (general)

Input: state-prep $A$, projector $\Pi_{\text{good}}$ Set $S_0=I-2|0\rangle\!\langle 0|$, $S_f=I-2\Pi_{\text{good}}$ Iterate $Q=-A S_0 A^\dagger S_f$ for $r$ steps; measure

Schematics¶

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

2D Rotation Picture¶

Hands-on Notebook (Multi-Backend)¶

Run: L10_QCQI_Ch08_Grover_and_Amplitude_Amplification

In the first cell set backend to one of: cirq, pennylane, braket, pyquil, or qiskit.

Mini-Lab Ideas¶

1. For $n=3$, mark one string and plot success vs. iterations to observe the sine-squared curve.

2. Mark $M=2$ strings; compare measured $P_r$ with theory using $\theta=\arcsin\sqrt{M/N}$.

3. Replace $H^{\otimes n}$ by a biased $A$ (e.g., rotate first qubit) and verify amplitude amplification still performs planar rotations.