- 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 byGilles Brassard andPeter 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-dimensionalHilbert 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 partitionmathcal{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,wherepsi_1 angle and psi_0 angle are thenormalized projections of psi angle into thesubspaces mathcal{H}_1 and mathcal{H}_0,respectively, and 0 < a < 1. This decomposition defines a two-dimensional subspacemathcal{H}_psi, spanned by the vectorspsi_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 operatorQ(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) ,!,0 < heta < pi/2 ,!, we can clearly see that in this subspace Qcorresponds to a rotation by the angle 2 heta,!::Q = egin{pmatrix}cos(2 heta) & sin(2 heta)\-sin(2 heta) & cos(2 heta)end{pmatrix}.
Applying Q(psi, chi),! repeatedly on the statepsi anglegives: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
Wikimedia Foundation. 2010.