- Amplitude amplification
Amplitude amplification is a technique in
quantum computingwhich generalizes the idea behindthe Grover's search algorithm, and gives rise to a family of
quantum algorithms.It was discovered by
Gilles Brassardand Peter Høyerin 1997,cite journal
author=Gilles Brassard, Peter Høyer
title=An exact quantum polynomial-time algorithm for Simon's problem
journal=Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems
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.
title=Quantum Computers Can Search Rapidly by Using Almost Any Transformation
journal=Phys. Rev. Lett.
In a quantum computer, amplitude amplification can be used to obtain aquadratic speedup over several classical algorithms.
The derivation presented here roughly follows the one given incite journal
author=Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp
title=Quantum Amplitude Amplification and Estimation
url=http://arxiv.org/abs/quant-ph/0005055] .Assume we have an -dimensional
Hilbert spacerepresenting the state space of our quantum system, spanned by theorthonormal computational basis states .Furthermore assume we have a Boolean function:. can be used to partition into a direct sum of two mutually orthogonal subspaces,:the "good" subspace , and:the "bad" subspace .
Given a (normalized) state vector , we canuniquely decompose it as :,where and are thenormalized projections of into thesubspaces and ,respectively, and . This decomposition defines a two-dimensional subspace, spanned by the vectors and . The probability of finding the system in a "good" state when measuredis . Furthermore we have .
Define a unitary operator,where: and:.The action of this operator on is given by: and:.By defining ,, we can clearly see that in this subspace corresponds to a rotation by the angle ::.
Applying repeatedly on the stategives:,rotating the state between the "good" and "bad" subspaces.After applications the probability of finding thesystem in a "good" state is . The probability is maximized if we choose:.Up until this point each application of increases the amplitude of the "good" states, hencethe name of the technique.
Wikimedia Foundation. 2010.