Amplitude amplification

Amplitude amplification is a technique in quantum computing which generalizes the idea behindthe Grover's search algorithm, and gives rise to a family of
quantum algorithms.It was discovered by Gilles Brassard and
Peter Høyer in 1997,cite journal
author=Gilles Brassard, Peter Høyer
year=1997
month=June
title=An exact quantum polynomial-time algorithm for Simon's problem
journal=Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems
pages=12--23
publisher=IEEE Computer Society Press
url=http://arxiv.org/abs/quant-ph/9704027] and independently rediscovered by Lov Grover in 1998.cite journal
author=Grover, Lov K.
year=1998
month=May
title=Quantum Computers Can Search Rapidly by Using Almost Any Transformation
journal=Phys. Rev. Lett.
volume=80
issue=19
pages=4329--4332
doi=10.1103/PhysRevLett.80.4329]

In a quantum computer, amplitude amplification can be used to obtain aquadratic speedup over several classical algorithms.

Algorithm

The derivation presented here roughly follows the one given incite journal
author=Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp
date=2000-05-15
title=Quantum Amplitude Amplification and Estimation
journal=arXiv:quant-ph/0005055
url=http://arxiv.org/abs/quant-ph/0005055] .Assume we have an $N$-dimensional Hilbert space $mathcal\{H\}$representing the state space of our quantum system, spanned by theorthonormal computational basis states $mathbf\{B\}\; :=\; \{\; |x\; angle\; \}\_\{x=0\}^\{N-1\}$.Furthermore assume we have a Boolean function:$chi:mathbb\{Z\}\; o\; \{0,1\}$.$chi$ can be used to partition$mathcal\{H\}$ into a direct sum of two mutually orthogonal subspaces,:the "good" subspace $mathcal\{H\}\_1\; =\; operatorname\{span\}\{|x\; angle\; in\; mathbf\{B\}\; ;|;\; chi(x)\; =\; 1\}$, and:the "bad" subspace $mathcal\{H\}\_0\; =\; operatorname\{span\}\{|x\; angle\; in\; mathbf\{B\}\; ;|;\; chi(x)\; =\; 0\}$.

Given a (normalized) state vector $|psi\; angle\; in\; mathcal\{H\}$, we canuniquely decompose it as :$|psi\; angle\; =\; a\; |psi\_1\; angle\; +\; b\; |psi\_0\; angle$,where$|psi\_1\; angle$ and $|psi\_0\; angle$ are thenormalized projections of $|psi\; angle$ into thesubspaces $mathcal\{H\}\_1$ and $mathcal\{H\}\_0$,respectively, and . This decomposition defines a two-dimensional subspace$mathcal\{H\}\_psi$, spanned by the vectors$|psi\_0\; angle$ and $|psi\_1\; angle$. The probability of finding the system in a "good" state when measuredis $a^2$. Furthermore we have $a^2+b^2=1$.

Define a unitary operator$Q(psi,\; chi)\; :=\; -S\_psi\; S\_chi\; ,!$,where:$S\_psi\; =\; I\; -\; 2|psi\; angle\; langlepsi|quad$ and:$S\_chi\; |x\; angle\; =\; (-1)^\{chi(x)\}\; |x\; angle$.The action of this operator on $mathcal\{H\}\_psi$ is given by:$Q\; |psi\_0\; angle\; =\; -S\_psi\; |psi\_0\; angle\; =\; (1-2a^2)|psi\_0\; angle\; +2ab|psi\_1\; angle$ and:$Q\; |psi\_1\; angle\; =\; S\_psi\; |psi\_1\; angle\; =\; -2ab|psi\_0\; angle+(1-2a^2)|psi\_1\; angle$.By defining $heta\; :=\; arcsin(a)\; ,!$,, we can clearly see that in this subspace $Q$corresponds to a rotation by the angle $2\; heta,!$::.

Applying $Q(psi,\; chi),!$ repeatedly on the state$|psi\; angle$gives:$Q^n\; |psi\; angle\; =\; cos((2n+1)\; heta)\; |psi\_0\; angle\; +sin((2n+1)\; heta)\; |psi\_1\; angle$,rotating the state between the "good" and "bad" subspaces.After $n$ applications the probability of finding thesystem in a "good" state is $sin^2((2n+1)\; heta),!$. The probability is maximized if we choose:$n\; =\; leftlfloorfrac\{pi\}\{4\; heta\}\; ight\; floor$.Up until this point each application of $Q$ increases the amplitude of the "good" states, hencethe name of the technique.

References