Amplitude Amplification

Generalize Grover's algorithm: amplify any marked state with unknown oracles.

Amplitude Amplification

Amplitude amplification is the mathematical heart of Grover's algorithm, generalized to any quantum subroutine. While Grover's searches an unstructured database, amplitude amplification applies to any algorithm A that has some probability of finding a "good" solution.

The setup:

Given a quantum algorithm A that, without any knowledge of the solution, succeeds with probability p = |α|² (i.e., A|0⟩ = α|good⟩ + β|bad⟩):

Classically: to achieve success probability ≥ 1-δ, you need $O (1/ p)$ repetitions. With amplitude amplification: O(1/√p) iterations of a specific two-step circuit.

This quadratic speedup applies universally.

The two operators:

1.Oracle $O_{f}$ : marks good states with a phase flip, $O_{f} ∣ x ⟩ = - ∣ x ⟩$ if x is good, $∣ x ⟩$ otherwise
2.Diffusion $D_{A}$ : reflects amplitudes about the average, using A: $D_{A} = A \cdot S_{0} \cdot A^{†}$ , where $S_{0}$ flips the phase of $∣0 ⟩$

The amplitude amplification circuit applies $(D_{A} \cdot O_{f})^{k}$ times, then measures.

Why this works: geometric intuition:

In 2D, the state space is spanned by |good⟩ and |bad⟩. The initial state $A ∣0 ⟩$ makes angle $θ$ with $∣ bad ⟩$ where $sin^{2} (θ) = p$ (the success probability). Each application of $(D_{A} \cdot O_{f})$ rotates the state by $2 θ$ toward $∣ good ⟩$ . After $⌊ π / (4 θ)⌋$ rotations, the state is nearly |good⟩.

k = ⌊ \frac{π}{4 θ} ⌋ where sin (θ) = p

Amplitude amplification generalizes Grover's search

Grover's search is amplitude amplification with $A = H^{\otimes n}$ (uniform distribution, $p = 1/ N$ ) and $O_{f}$ = phase oracle for the target. The number of iterations is ⌊π√N/4⌋. The generalization to arbitrary A is powerful: if A succeeds with probability 1/100 classically, amplitude amplification achieves success in ~10 iterations instead of ~100. Any quantum algorithm with a verifiable 'good' output becomes faster with amplitude amplification.

Iteration count for different scenarios:

Initial success prob p	Classical trials needed	Amplitude amp iterations
1/4 (sin²(π/6))	4	1
1/100	100	~8
1/N (Grover's)	N	~π√N/4

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.

Part of: Quantum Algorithms

Learn the algorithms that make quantum computers powerful.

Previous lessonGrover's Search Algorithm Next lessonQuantum Walks

This lesson is part of Pro

Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground