Algorithms · Generalized Grover / amplitude amplification

Amplitude amplification

The general framework behind Grover's algorithm: boosting the success probability of any subroutine with a known reflection structure.

Open on the map View frozen graph

A small worked example, computed in your browser. It is not a result from this record's papers.

Grover's algorithm finds |101⟩

3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.

Step 1 of 5 · Hadamard layer(3)

Probability of each outcome after this step

00013%
00113%
01013%
01113%
10013%
10113%
11013%
11113%

Spreads the state into an equal superposition of all 8 three-qubit strings. Every answer is equally likely, including the right one.
Probability spreads from 1 outcome to 8. All 8 are equally likely.
The oracle marks |101⟩ by flipping its sign, and leaves the other seven states exactly as they were. Measuring now would be no better than guessing — the mark is a phase, and a phase is not an outcome.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
The diffuser reflects every amplitude about their average. The marked state sits below the average because its sign was flipped, so reflecting pushes it up and pulls the other seven down. This is where the phase becomes probability.
Probability moves between the same 8 outcomes. Up: 101 12.5% → 78.1%. Down: 111 12.5% → 3.1%, 011 12.5% → 3.1%.
The same oracle again, flipping the sign of |101⟩ — now the largest amplitude rather than one of eight equal ones.
The outcome probabilities do not move at all. What this step changes is phase — 2 distinct relative phases across the state now — which no measurement can see until a later step turns it back into probability.
And the same reflection again. Two iterations is close to the optimal number for 8 states: a third would overshoot and start pushing the answer back down.
Probability moves between the same 8 outcomes. Up: 101 78.1% → 94.5%. Down: 100 3.1% → 0.8%, 010 3.1% → 0.8%.

Readout Measuring gives 101, the marked state, with high probability.

Open in Studio

Steps3
Wires1
Qubits1 (toy instance)
Iterations to certainty (a=1/4)k = 1
General scalingO(1/√a) iterations
Papers1

Amplitude amplification (Brassard, Høyer, Mosca, Tapp, 2000) generalizes Grover's algorithm from the specific case where the initial state is prepared by Hadamards to an arbitrary state-preparation operator $A$ .

Setup. Suppose $A|0\rangle = \sin\theta\,|\text{good}\rangle + \cos\theta\,|\text{bad}\rangle$ , so the initial success probability is $a=\sin^2\theta$ . Define the amplification operator

Q = A\,S_0\,A^{-1}\,S_\chi,

where $S_\chi$ flips the phase of good states and $S_0$ flips the phase of everything except $|0\rangle$ . Geometrically, $Q$ is a rotation by $2\theta$ in the 2-dimensional real span of $|\text{good}\rangle$ and $|\text{bad}\rangle$ , so after $k$ applications the success probability is

P_k = \sin^2\big((2k+1)\theta\big).

Choosing $k\approx \frac{\pi}{4\theta}-\frac12$ drives $P_k$ close to 1, needing $O(1/\sqrt a)$ iterations versus the $O(1/a)$ classical repetitions needed to hit a probability- $a$ event with matching confidence — the same quadratic gain that Grover's algorithm gets as the special case $A=H^{\otimes n}$ .

Exactly solvable small instance. Take a single qubit with $A=R_y(2\theta)$ , $\theta=\pi/6$ , so $a=\sin^2(\pi/6)=1/4$ — the initial success ("good" = $|1\rangle$ ) probability is exactly $1/4$ . One iteration gives

P_1 = \sin^2(3\theta) = \sin^2\!\left(\frac{\pi}{2}\right) = 1,

i.e. a single amplitude-amplification step turns a 25%-success preparation into a certain one — the same numeric case that underlies the classic "Grover on $N=4$ , $M=1$ " result, here derived directly from the rotation-angle formula rather than from an oracle over a register.

Where it is used. Amplitude amplification is the mechanism inside quantum counting, amplitude estimation, and any algorithm that needs to boost the probability of a rare event once a coherent way to recognize "success" (a reflection oracle) is available.

Quantum vs classical

Metric	Classical	Quantum
Query complexity (good-state prob. a)	O(1/a)	O(1/√a)
Asymptotic speedup	baseline	quadratic

Classical baseline

Classical repeated sampling needs O(1/a) expected trials to observe an event of probability a.

Quantum claim

One amplitude-amplification iteration boosts success from a=1/4 to certainty in this instance; more generally O(1/√a) iterations suffice, assuming a reflection oracle over the good subspace is available.

How to compare

Compare oracle depth × iteration count against the classical sampling cost for the same acceptance threshold, and confirm the reflection oracle is actually available at that cost.

FrameworkNative

amplitude_amplification.py

from qiskit import QuantumCircuit
import numpy as np

theta = np.pi / 6  # sin(theta) = 1/2 -> initial success a = 1/4

def state_prep():
    qc = QuantumCircuit(1, name="A")
    qc.ry(2 * theta, 0)
    return qc

def oracle():
    qc = QuantumCircuit(1, name="S_chi")
    qc.z(0)  # marks |1> (good state) with a phase flip
    return qc

A = state_prep()
qc = QuantumCircuit(1, 1)
qc.append(A, [0])
# One amplitude-amplification iteration: S_chi, A^-1, S_0, A
qc.append(oracle(), [0])
qc.append(A.inverse(), [0])
qc.x(0)
qc.z(0)
qc.x(0)  # S_0: reflect about |0>
qc.append(A, [0])
qc.measure(0, 0)

FINAL_CIRCUIT = qc

References

Quantum Amplitude Amplification and Estimation
Gilles Brassard, Peter Hoyer, Michele Mosca, Alain Tapp · 2000
Generalizes Grover's algorithm to an arbitrary state-preparation operator and derives the amplification operator Q used here.

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

Amplitude amplification

Grover's algorithm finds |101⟩

Quantum vs classical

Classical baseline

Quantum claim

How to compare

Where this sits

Related entries

References