amplitude estimation

In plain terms

Amplitude amplification boosts a success probability, and amplitude estimation measures it. Classically, learning a probability to a given precision costs about one over the square of that precision in samples, so ten times the precision needs a hundred times the runs. The quantum route starts from a fact about the amplification step, which rotates a two-dimensional stage by an angle whose squared sine is the success probability, so the probability is encoded in an angle. A rotation has two special states it leaves unchanged apart from a phase factor, and those phase factors, its eigenvalues, carry exactly the angle in question, and eigenvalue angles are precisely what phase estimation reads out.

So run the rotation a controlled number of times, read the control register through the quantum Fourier transform, and the measured index lands near the angle with fixed odds. Squaring the sine of that angle gives the estimate of the probability, accurate to about one over the number of rounds after only that many rounds, and that quadratic saving is what makes quantum counting and quantum Monte Carlo speedups work.

The state splits into exactly two clean branches, one rotating clockwise and one anticlockwise. Because the companion states of the two branches are perpendicular, the readout is an honest half-and-half mixture of two well-understood distributions, with no interference between them.

In CSD

Amplitude estimation is where three prepared layers of the corpus meet in one theorem, the two special states with opposite rotation angles, the joint-register mixture law, which says that perpendicular second factors kill every cross-term in the readout probabilities, and the phase-estimation success bound. The state of the control register after the controlled rotations is proved equal to a two-branch phase form, so the counting readout is an exact half-and-half mixture, an equality and not an estimate.

The stated bounds are these. Any index in the window closest to the true angle carries probability at least two divided by pi squared, its mirror index carries the other branch's two divided by pi squared and decodes to the same estimate, so the pair jointly carries four divided by pi squared, and the estimate lands within an explicit distance of the truth that shrinks in proportion to one over the number of rounds, with the exact expression in the mathematical section. The paper's literal bound of eight divided by pi squared counts both rounding directions, so the corpus proves a two-index inequality on the Dirichlet kernel and accepts the two grid points straddling the true angle together with their mirrors, which gives the paper's constant and its error bound exactly. The standing disclaimer applies, as the algorithm layer consumes the programme's unitary-evolution pillar and doesn't support the foundations.

Mathematically

The AA-5b assembly. With Q the amplification step at angle theta (sin theta = sqrt a) on the rotation plane, the kickback state (1/sqrt T) sum_x |x> tensor Q^x psi decomposes exactly as c_+ phaseStateR(theta/pi) tensor v_+ + c_- phaseStateR(-theta/pi) tensor v_-, where v_+- = g +- i b are the orthogonal eigenvectors, Q^x v_+- = e^(+-2 i x theta) v_+-, and |c_+-| = 1/2.

Applying the inverse QFT to the counting register and taking the Born marginal gives exactly (P_+(c) + P_-(c))/2, the half-half mixture of the two single-phase counting distributions. At any c with |theta/pi - c/T| <= 1/(2T), the plus branch contributes at least 4/pi^2, so the marginal carries at least 2/pi^2, the mirror index -c carries the minus branch's 2/pi^2 and decodes to the same estimate, so the pair carries 4/pi^2. And sin^2(pi c / T) estimates a = sin^2 theta within 2 sqrt(a(1-a)) eps + eps^2 at eps = pi/(2T), that is within pi sqrt(a(1-a))/T + pi^2/(4 T^2), by the product-form sin^2 difference identity plus the Lipschitz bound on sin (amplitude_estimation). The paper's literal 8/pi^2 counts both rounding directions: sin^2(pi x)(1/x^2 + 1/(1-x)^2) >= 8 on (0,1) gives f(delta) + f(delta - 1/T) >= 8/pi^2 for the Dirichlet kernel at 0 <= delta <= 1/T (dirichlet_two_index, phase_estimation_two_index), so the four indices {c, c+1, -c, -(c+1)} carry at least 8/pi^2 and each decodes within 2 pi sqrt(a(1-a))/T + pi^2/T^2 (amplitude_estimation_bhmt), BHMT's Theorem 11 at k = 1.

The name

The same four authors as amplitude amplification, Brassard, Hoyer, Mosca and Tapp, in the same 2000 paper, "Quantum Amplitude Amplification and Estimation". The estimation half is the paper's Theorem 12, feeding their quantum counting results, which estimate how many marked items a database holds without ever listing them.

The technique is the meeting point of the field's two workhorse subroutines, Grover's rotation geometry (1996) and Kitaev-style phase estimation (1995), and it later became the engine of quantum Monte Carlo speedups through Montanaro's 2015 work.

Related entries

• amplitude amplificationAmplitude amplification is the theorem of which Grover's algorithm is a shadow, as any quantum procedure with any success probability can have that probability raised by pure interference, quadratically faster than retrying.
• 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.
• 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.
• Fisher informationThere's a floor under every error bar, classical or quantum, and Fisher information is what sets it.
• 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.