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.
Strong empiricalUpdated
Open on the mapView 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 replaces Grover's uniform-superposition preparation with an arbitrary operator A, generalizing the quadratic speedup to any algorithm that prepares a 'good/bad' superposition.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
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 .
Setup. Suppose , so the initial success probability is . Define the amplification operator
where flips the phase of good states and flips the phase of everything except . Geometrically, is a rotation by in the 2-dimensional real span of and , so after applications the success probability is
Choosing drives close to 1, needing iterations versus the classical repetitions needed to hit a probability- event with matching confidence — the same quadratic gain that Grover's algorithm gets as the special case .
Exactly solvable small instance. Take a single qubit with , , so — the initial success ("good" = ) probability is exactly . One iteration gives
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 , " 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.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Qubits
- 1 (toy instance)
- Iterations to certainty (a=1/4)
- k = 1
- General scaling
- O(1/√a) iterations
- Rotation angle
- θ, sin²θ = a
- Success after k iters
- sin²((2k+1)θ)
- Classical baseline
- O(1/a) repetitions
A (Ry state prep)on q[0]Oracle S_χon q[0]A⁻¹, S₀, Aon q[0]
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.
Nobody has reviewed this record for gaps yet.
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 = qcWhere this sits
This record is named by the layer graph at:
- Amplify a success branch Slot
Takes The preparation unitary and its inverse, a reflection about , and a reflection marking the good subspace — the Grover operator must be applicable at arbitrary powers. Individual variants additionally require a lower bound on , or a per-branch stopping flag. Returns A routine that produces the wanted branch with a stated failure probability, together with the query count and the maximum sequential depth consumed.
Related entries
- Grover unstructured search
Algorithms
- Quantum counting
Algorithms
- Quantum amplitude estimation
Algorithms
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.