Amplitude amplification Created 2026-09-24 Updated 2026-10-13
Amplitude amplification increases the probability of obtaining an answer accepted by a specified Boolean function. It requires a coherent preparation , its inverse, and a marked-state phase oracle that negates accepted components. Alternating that sign change with a reflection operator about the prepared state directs interference toward the accepted subspace. Brassard, Høyer, Mosca, and Tapp developed the general framework, extending Grover's algorithm beyond a uniform quantum superposition. [ref].
If a normalized quantum state has good amplitude , the product of the reflection in the bad axis and the reflection in the state line rotates its good-bad plane by . After iterations the good probability is
so iterations raise a small good amplitude close to one. Success subsequently oscillates, making the stopping time part of the algorithm.
Compute the exact Grover search on four entries directly. Order the computational basis as and mark . The Hadamard transform prepares amplitudes . The marked-state phase oracle changes these to , whose arithmetic mean is . The Grover diffusion operator performs inversion about the mean:
The three unmarked amplitudes become , while the marked amplitude becomes . All three stages have squared norm one. Here , so and one iteration gives , agreeing with the explicit calculation.
Figure 1.
One Grover iteration on four states: a phase flip followed by reflection about the mean concentrates all amplitude on the marked state
. Details.
Grover's original search paper was submitted on 29 May 1996; its algorithm combines selective sign changes with inversion about the mean. The example exposes the beauty of that construction: a change initially invisible to computational-basis measurement becomes complete cancellation of every wrong answer. [ref].
The marked-state phase oracle is an assumed operation, whose implementation cost must be counted. Computational-basis measurement yields a candidate label, here ; using it to retrieve a record requires the relevant data access. Preparing a quantum superposition does not make all its entries available as classical outputs. The improvement concerns the number of oracle queries needed to obtain an accepted label.
Start from , negate amplitudes at marked indices, and apply . If the marked fraction is , the oracle-state mean amplitude is . Inversion about the mean therefore gives amplitudes on unmarked indices and on marked ones. The marked success probability is . At it is exactly one: unmarked amplitudes vanish and each marked amplitude is . The output is uniform among the marked indices. This is an exact special case of Grover's algorithm, using one phase oracle call under the stated promise.
A quantum computing apparatus needs a scalable quantum register of controllable qubits, reproducible initialization, a universal quantum gate set, sufficiently long quantum coherence, and selective readout. A qubit is a two-dimensional state space; several qubits occupy a tensor product space and can develop entanglement. Quantum state preparation must establish a known low-entropy input and supply fresh ancillas during quantum error correction. A universal quantum gate set may use arbitrary single-qubit rotations with an entangling two-qubit gate such as controlled-NOT gate. Quantum coherence and control fidelity must suffice for the intended circuit, and measurement must recover chosen output probabilities without uncontrolled disturbance of other qubits. These are the five DiVincenzo criteria.[ref]
An atomic implementation can encode qubits in two long-lived internal levels, initialize them by optical pumping, drive coherent transitions with laser or microwave pulses, couple selected qubits through a shared interaction, and distinguish states by state-dependent fluorescence. For trapped ions, a shared vibrational mode can mediate entangling gates, so motional control and cooling are part of the computational apparatus. The motion is a resource only while uncontrolled heating does not erase the required quantum coherence.
The computational resource is coherent control of amplitudes and entanglement, with interference making useful outcomes likely. An -qubit pure state has basis amplitudes, but a single measurement does not reveal those amplitudes or all possible answers. Algorithms exploit structure rather than simply reading out parallel classical computations. The Shor algorithm gives factoring with polynomial resource scaling in the input bit length, compared with the best known classical algorithms' superpolynomial scaling; an exponential classical lower bound has not been proved.[ref] Grover's algorithm uses order oracle queries for unstructured search among possibilities, a quadratic query improvement.[ref] Quantum simulation is a further motivation because interacting quantum systems can require exponentially many classical amplitudes for a direct generic representation.
The main challenges are quantum decoherence, fluctuating control fields, imperfect gates, leakage out of the qubit subspace, readout errors, crosstalk, and the difficulty of scaling connectivity and calibration. Faster control can introduce extra errors, while stronger isolation can make preparation and readout harder. Quantum error correction encodes logical information redundantly in several physical qubits and extracts error syndromes without measuring the unknown logical state itself. Fault-tolerant quantum computation prevents the correction apparatus and gates from spreading a few faults into uncorrectable logical errors. It requires error rates below an architecture- and noise-dependent threshold and substantial resources; there is no universal numerical threshold for all implementations. Advantages are task-dependent, while reliable scaling requires both coherent hardware and error control.
Let and let be one only at the marked input. A three-qubit implementation of Grover's algorithm starts with , applies a Hadamard gate to each qubit, queries the reversible quantum oracle , applies the Grover diffusion operator to the first two qubits, and measures those two qubits in the computational basis. Here . The full three-wire quantum circuit is the composition
Figure 1.
Three- and two-qubit implementations of Grover's algorithm for four inputs
. Details.
Here . Since , phase kickback gives . The third qubit remains separable and unchanged. A direct marked-state phase oracle therefore replaces the three-qubit query using only two qubits:
For the explicit choice only at , is a Controlled-Z gate. Immediately after it,
The mean of these four probability amplitudes is . The Grover diffusion operator maps each probability amplitude to . The three unmarked probability amplitudes become zero and the marked one becomes one. A single query consequently finds with probability one.
A gate-level implementation of is . Up to an irrelevant global phase, it is . For any other chosen marked word, conjugate the Controlled-Z gate by Pauli X gates on precisely the positions where the marked word has a zero.