amplitude amplification

In plain terms

Suppose your quantum procedure succeeds only sometimes, with some fixed probability. Classically the only remedy for a small probability is repetition, about one over the probability runs, and it's natural to assume that's simply what boosting success must cost.

Brassard, Hoyer, Mosca and Tapp found the general trick hiding inside Grover's search. Reflect the state about the failures, then reflect it about where you started. A reflection here is the quantum analogue of a mirror, as it flips the sign of one part of the state and leaves the rest alone, and two reflections make a rotation, so each round rotates the state by a fixed angle towards success. After about one over the square root of the probability rounds, not one over the probability, you measure and win, and the exact success curve at every round is known in closed form.

Run past the sweet spot and you rotate beyond the target, so the procedure has a timer, just as Grover's does. Grover's search is exactly this machine pointed at a uniform starting state with one marked item.

In CSD

Amplitude amplification is a library theorem in the corpus, deliberately free of CSD content and fully general, for any finite register, any set of outcomes counted as good, and any starting state whose success probability lies strictly between zero and one. The two-reflection rotation and the closed-form success curve are exact statements and not approximations for large registers. The recommended round count succeeds with probability at least one minus the starting probability, and that round count is at most a fixed constant times one over the square root of the starting probability, which is the quadratic speedup as a named inequality.

The corpus's module on Grover's algorithm is rebuilt on this theorem, so the search step is proved to be the amplification step, the headline result is re-derived as an instance, and the distribution for several marked items arrives free. For an unknown success probability the module also carries the randomised search engine from the same paper, as a round count chosen uniformly at random below a cap succeeds with average probability at least one quarter once the cap is large enough relative to the success probability, and the sum over rounds telescopes to an exact closed form. The whole search with its exponentially growing caps is proved as well, so a run finishes in an expected number of steps at most a fixed constant times one over the square root of the success probability, with the run modelled as independent stages on a probability space. The exact threshold is stated in the mathematical section. The standing disclaimer applies, as the algorithm layer consumes the programme's unitary-evolution pillar and doesn't support the foundations.

Mathematically

A Cat-1 theorem. On EuclideanSpace C over a finite basis with good set G, the step is reflection about the initial state composed with the sign flip on the good coordinates. On the plane spanned by the normalised good and bad components the step is a rotation by 2 theta with sin theta = sqrt(goodProb), and j rounds send the plane angle to (2j+1) theta, so the success probability is exactly sin^2((2j+1) theta), that is sin^2((2j+1) arcsin sqrt(a)) (amplitude_amplification).

The optimal count m = floor(pi/(4 theta)) lands the angle within theta of pi/2, giving success at least cos^2(theta) = 1 - a, and m <= pi/(4 sqrt a) since sqrt a = sin theta <= theta. For unknown a the QSearch engine (BHMT Lemma 2) is also proved, as a uniformly random round count below M succeeds with average probability at least 1/4 once M * 2 sqrt(a(1-a)) >= 1, the odd-angle sum telescoping to an exact closed form. The full QSearch (BHMT Theorem 3) is proved in QSearch.lean: with caps M_l = ceil((6/5)^l), the stages modelled as independent random variables (QSearchRun) and the cost 2 + 2j charged to a reached stage with round count j, the expected number of applications is at most 54/sqrt(a) for 0 < a < 1 (qsearch_expected_cost), and the model is consistent (exists_qsearchRun). Degenerate boundaries a = 0 (no plane) and a = 1 (nothing to amplify) are excluded by hypothesis. Round counting is abstract, and no oracle model or gate decomposition is claimed.

The name

Gilles Brassard (Montreal) is one half of the BB84 quantum-cryptography protocol. Peter Hoyer (Calgary), Michele Mosca (Waterloo, later a founder of the Institute for Quantum Computing) and Alain Tapp (Montreal) were his collaborators in the Quebec- Ontario quantum information school of the late 1990s.

Their paper, "Quantum Amplitude Amplification and Estimation" (2000, published 2002), unified a string of post-Grover boosting tricks into one two-reflection geometry and paired it with amplitude estimation, the phase-estimation reading of the same rotation, which is where the two workhorse subroutines of the field meet.

Related entries

• Grover's algorithmGrover's algorithm finds one marked item in an unsorted list in a number of steps proportional to the square root of the list size, and a separate theorem shows that no quantum algorithm can do better.
• amplitude estimationPoint phase estimation at the rotation inside amplitude amplification and the success probability itself becomes measurable, quadratically faster than sampling could ever learn it.
• phase estimationPhase estimation, the workhorse subroutine of quantum computing, carries a guarantee, as if you read the dial at the nearest tick you're right at least four divided by pi squared of the time, a little over forty percent, however fine the dial.
• swap testThe swap test measures how alike two quantum states are without learning anything about what either one is, so it's a comparison that keeps both secrets.
• quantum Fourier transformThe quantum Fourier transform runs Fourier's transform as a single reversible motion of a quantum register, and it's the lens that turns hidden periods and phases into outcomes a measurement can land on.