Amplitude Amplification

Improve an existing coherent success probability

Amplitude amplification generalises Grover search. The starting state need not be uniform over every candidate. A reversible procedure A prepares some state, and a predicate recognises good outcomes. If measuring that state succeeds with probability p, amplification can raise success using coherent calls to A, its inverse and suitable reflections.

Study Grover search first. The new idea is to reflect about whatever A prepares, rather than only the uniform state. The prerequisite that A can be run coherently and inverted is a real resource assumption. An arbitrary classical sampling service does not automatically supply it.

WORKED DIAGRAM · A07Amplify a biased one-qubit preparation

An initial good probability of 1/4 corresponds to angle π/6. One amplification iterate triples the angle to π/2 and yields success one for this preparation.

State the input and output

You receive a unitary preparation A, a standard input zero state, and a phase test that identifies a good subspace. Write the prepared state as a good component plus a bad component. Their squared weights sum to one. The task is to produce a good classical outcome on measurement, with a specified success probability.

The procedure does not need to know every good label in advance. It needs an implementable coherent recognition test. It also does not reveal the entire prepared state. Like Grover, it returns a sampled candidate, and the application should verify or interpret that candidate according to its contract.

Construct the two reflections

One reflection changes the sign of the good subspace. The other reflects about the state A applied to zero. To implement the latter, undo A, apply a reflection about zero, then reapply A. Up to a common sign convention, a full amplification step combines these reflections.

This construction explains why inverse access matters. If a preparation contains an uncontrolled measurement whose record is discarded, it may not admit the required simple inverse. Some randomised classical computations can be made reversible by retaining their random coins and workspace coherently, but that conversion has a cost and requires a plan to uncompute temporary information.

Worked one-qubit example

Let A prepare amplitudes square root of three over two for zero and one half for one. Define one as good. The initial success probability is one quarter, and the initial angle toward the good direction is 30 degrees. One amplification step should move that angle to 90 degrees, giving certain success in this special case.

The good-phase reflection changes the state to amplitudes square root of three over two and negative one half. The reflection about the original prepared state has matrix

$$R_{\psi}=\begin{pmatrix}1/2&\sqrt3/2\\\sqrt3/2&-1/2\end{pmatrix}.$$

Multiplying that matrix by the phase-flipped column gives zero in the first component and one in the second. The cancellation is exact. This example uses a biased preparation, so the uniform-state diffusion shortcut from basic Grover would be the wrong reflection. General amplification must reflect about the actual prepared state.

Correctness through a two-dimensional plane

Normalise the good projection of A’s output to define one direction and its bad projection to define another. The prepared state lies in their span. Let sine squared theta equal p. The good phase test and reflection about the preparation preserve this plane. Their composition rotates within it, giving success after k steps equal to sine squared of (2k plus one) theta.

For small p, reaching the first large-success region takes on the order of one over the square root of p amplification steps. Ordinary independent prepare-measure-check repetition needs on the order of one over p trials on average. The comparison assumes access to the coherent preparation, inverse and recognition reflection and counts those resources consistently.

Known and unknown success fractions

If p is known, choose an appropriate iteration count near a peak. Integer rounding and desired certainty matter; a basic fixed-phase iterate does not hit exact success for every p. Modified-phase methods can improve exactness or robustness under stated assumptions. If p is unknown, a single guessed iteration count may overshoot badly.

Randomised schedules, estimation-assisted approaches and fixed-point constructions address different versions of that problem. They have their own costs and guarantees. “Amplitude amplification” names a family of techniques, not a rule that repeatedly boosts success monotonically for any unknown input. State which variant is being used and what information about p it requires.

When it helps a larger algorithm

Suppose a coherent subroutine produces a useful answer rarely but can recognise success. Amplification can reduce the number of coherent attempts needed to obtain one good result. This pattern appears in search, state preparation and other probabilistic quantum subroutines. The improvement is relative to that subroutine’s initial success probability and access assumptions.

It does not eliminate expensive preparation. If A itself has a large data-loading or arithmetic cost, each amplification step pays for A and its inverse. If recognising a good result is as hard as solving the original problem, the phase test may be the bottleneck. An end-to-end analysis multiplies the iteration count by these costs and includes output verification.

Exercises

1. A coherent procedure succeeds with probability one in ten thousand. Compare the scaling of ordinary repetition and amplitude amplification, ignoring constants but counting a use of A as a resource.

2. A preparation service returns a random candidate but reveals no circuit and provides no inverse. Can you automatically apply the reflection construction above? Explain the missing resource.

Worked answers

1. Ordinary repetition has an average scale of ten thousand preparations. Amplification has a scale of one hundred coherent iterations, each including preparation/inverse and reflection work. These are scaling comparisons rather than exact runtime predictions.

2. No. The construction needs coherent unitary preparation and inverse access, plus the recognition reflection. A black-box classical sampler supplies only samples. Turning its implementation into a coherent reversible procedure may be possible in a particular setting, but must be explicitly designed and charged for.

Source

Brassard, Høyer, Mosca and Tapp develop amplitude amplification and estimation. The biased one-qubit calculation above makes the two reflections explicit for a small preparation.

Check your understanding

PAUSE & THINK

Why is a classical sampling service alone insufficient for this reflection construction?

Choose your answer

Its samples cannot be randomThe method also needs coherent preparation and inverse accessAmplification requires a uniform initial state

Check my answer

Answer: The method also needs coherent preparation and inverse access. Reflecting about A|0⟩ uses A†, a zero-state reflection and A. Ordinary samples do not automatically provide these coherent operations.