TopicIntermediateEstablished concept

Amplitude Amplification

Amplitude Amplification

Amplitude amplificationAmplitude Amplification: Amplitude amplification is a generalisation of Grover's algorithm: two successive reflections rotate the state towards the "good" subspace by an angle 2θ per iteration,… is a generalisation of Grover's algorithm: two successive reflections rotate the state towards the "good" subspace by an angle $2\theta$ per iteration, raising the success probability from $\sin^2\theta$ to nearly 1 after $O(1/\theta)$ iterations.

Let an initial state be $|\psi\rangle=\sin\theta|\text{good}\rangle+\cos\theta|\text{bad}\rangle$, i.e. the probability of success with a direct measurement is $\sin^2\theta$. The Grover operator consists of two reflections: $S_f$ flips the sign of the good component (via the oracle), and $S_\psi=2|\psi\rangle\langle\psi|-I$ reflects about the initial state (the diffusion operator). The product of two reflections is a rotation, by the angle $2\theta$, in the plane spanned by $|\text{good}\rangle$ and $|\text{bad}\rangle$. After $k$ iterations: $$G^k|\psi\rangle=\sin((2k+1)\theta)|\text{good}\rangle+\cos((2k+1)\theta)|\text{bad}\rangle.$$

So $k\approx\frac{\pi}{4\theta}$ is chosen. When searching for $M$ items among $N$, $\sin\theta=\sqrt{M/N}$, so $k=O(\sqrt{N/M})$ against $O(N/M)$ classically. Boyer, Brassard, Høyer and Tapp (1998) proved tight bounds and gave a version that works when $M$ is unknown.

A practical caveat: the process is periodic, so iterating past the optimal value lowers the probability of success. And the speed-up is only quadratic, which is optimal for unstructured search problems in the query model.

Amplitude amplification is used as a building block in other algorithms, such as amplitude estimation, which combines it with phase estimation to estimate $\sin^2\theta$ more precisely than direct sampling. The idea differs from Grover only in that the initial state can be the output of any preparation algorithm $\mathcal{A}|0\rangle$, not just the uniform superposition.

q0q1q2H⊗nOracleDiffOracleDiff
Grover's algorithm: superposition, then repeated oracle and diffusion

Mathematical formulation

$$P_k=\sin^2\big((2k+1)\theta\big),\qquad \sin\theta=\sqrt{M/N}$$

Worked example

$N=8$ and $M=1$: $\theta=\arcsin(1/\sqrt8)\approx0.3614$. After $k=1$: $\sin^2(3\theta)\approx0.781$. After $k=2$: $\sin^2(5\theta)\approx0.945$. After $k=3$: $\sin^2(7\theta)\approx0.330$; i.e. extra iterations hurt. The optimal value is $k=2$.

Try it yourself: Grover's Algorithm

Loading the simulator…

The full experiment page

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
  2. Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998). Tight Bounds on Quantum Searching. Fortschritte der Physik 46(4-5):493–505 doi:10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
  3. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.