Algorithms · Amplitude amplification
Grover unstructured search
The canonical search primitive, paired with the linear classical baseline it is meant to improve.
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
- Wires2
- Qubits2 toy
- DepthOracle + diffusion
- ClaimO(√N) queries
- Papers1
Grover amplifies the amplitude of marked states using an oracle and a diffusion step. It is useful for testing whether a claimed speedup includes oracle construction and readout costs.
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 →
For an unstructured search space of size with a single marked item, Grover's algorithm reaches the marked state with high probability using oracle queries, versus expected queries for classical exhaustive search — a quadratic query-complexity separation, not a claim about wall-clock time on any given hardware. The construction alternates an oracle that flips the sign of the marked amplitude with the diffusion operator ; each pass rotates the state by (where ) toward the marked subspace, and the success amplitude after iterations is , so overshooting past the optimal actually reduces success probability. This record's two-qubit () toy oracle and diffusion layer are checked against the ideal circuit — small-instance evidence for the construction — while the asymptotic claim rests on the cited literature and assumes a coherent oracle where oracle calls, not classical readout, dominate cost.
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
- 2 toy
- Depth
- Oracle + diffusion
- Claim
- O(√N) queries
- Oracle
- One marked state
- Classical baseline
- Linear search
- Readout
- Measure candidate
H×2on q[0], q[1]Oracleon q[0], q[1]Diffusionon q[0], q[1]
Quantum vs classical
| Metric | Classical | Quantum |
|---|---|---|
| Query complexity | O(N) | O(√N) |
| Queries (1 of N marked) | ~N/2 avg | ⌊(π/4)√N⌋ |
| Register (N = 2ⁿ) | n bits | n qubits |
| Asymptotic speedup | baseline | quadratic |
Classical baseline
Linear scan or a classical indexed data structure, depending on whether the oracle is already available.
Quantum claim
Quadratic improvement in oracle queries for an unstructured search problem.
How to compare
Include oracle synthesis, state preparation, error correction, measurement repetitions, and data-loading costs before calling it an application speedup.
Nobody has reviewed this record for gaps yet.
from qiskit import QuantumCircuit
qc = QuantumCircuit(2)
qc.h([0, 1])
# Oracle marks one basis state.
qc.cz(0, 1)
qc.h([0, 1])
qc.x([0, 1])
qc.cz(0, 1)
qc.x([0, 1])
qc.h([0, 1])
FINAL_CIRCUIT = qcThe oracle is intentionally small so the circuit can be inspected. Scaling claims belong to the cited query-complexity result.
Where this sits
This record is named by the layer graph at:
- Fixed-iteration amplitude rotation Method
Takes A check evaluable in superposition on any candidate, the size of the domain it ranges over, and the promise that fixes the schedule — Grover assumes exactly one accepted candidate; a method may instead require the check to answer about partial commitments rather than whole candidates. Returns One accepted candidate, with the number of queries spent and the probability the answer is right — or the report, at a stated confidence, that the domain holds none.
Related entries
- Quantum amplitude estimation
Algorithms
- Hadamard gate
Gates
References
- A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Original search algorithm and the O(√N) query comparison with classical search.