Amplitude amplification
Encyclopedia
Amplitude amplification is a technique in quantum computing which generalizes the idea behind
the Grover's search algorithm
, and gives rise to a family of
quantum algorithm
s.
It was discovered by Gilles Brassard
and
Peter Høyer in 1997,
and independently rediscovered by Lov Grover in 1998.
In a quantum computer, amplitude amplification can be used to obtain a
quadratic speedup over several classical algorithms.
.
Assume we have an N-dimensional Hilbert space
representing the state space
of our quantum system, spanned by the
orthonormal computational basis states
.
Furthermore assume we have a Hermitian
projection operator
.
Alternatively,
may be given in terms of a
Boolean oracle function
and an orthonormal operational basis
,
in which case
.
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
which has nonzero overlap with both subspaces, we can
uniquely decompose it as
,
where
,
and
and 
are the
normalized projections of
into the
subspaces
and 
,
respectively.
This decomposition defines a two-dimensional subspace
, spanned by the vectors
and 
.
The probability of finding the system in a good state when measured
is
.
Define a unitary operator
,
where
flips the phase of the states in the good subspace, whereas
flips the phase of the initial state 
.
The action of this operator on
is given by
and
.
Thus in the
subspace 
corresponds to a rotation by the angle
:
.
Applying
times on the state
gives
,
rotating the state between the good and bad subspaces.
After
iterations the probability of finding the
system in a good state is
.
The probability is maximized if we choose
.
Up until this point each iteration increases the amplitude of the good states, hence
the name of the technique.
which can recognize the good entries we are searching for, and 
for simplicity.
If there are G such entries in the database in total, then we can find them by
initializing the quantum computer into a uniform superposition
of all the database elements,
and running the above algorithm. In this case the overlap of the initial state with the good subspace is equal to the
square root of the frequency of the good entries in the database,
.
If
, we can approximate the number of required iterations as
Measuring the state will now give one of the good entries with a high probability. Since each application of
requires a single oracle query (assuming that the oracle is implemented as a quantum gate),
we can find a good entry with just
oracle queries, thus obtaining a quadratic speedup over the best possible classical algorithm.
If we set G to one, the above scenario essentially reduces to the original Grover search.
the Grover's search algorithm
Grover's algorithm
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....
, and gives rise to a family of
quantum algorithm
Quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a...
s.
It was discovered by Gilles Brassard
Gilles Brassard
Gilles Brassard was born in Montreal, Canada, in 1955. He received a Masters degree from the Université de Montréal in 1975, and obtained his Ph.D. in Computer Science from Cornell University in 1979, working in the field of cryptography with John Hopcroft as his advisor...
and
Peter Høyer in 1997,
and independently rediscovered by Lov Grover in 1998.
In a quantum computer, amplitude amplification can be used to obtain a
quadratic speedup over several classical algorithms.
Algorithm
The derivation presented here roughly follows the one given in.
Assume we have an N-dimensional Hilbert space
Hilbert space
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...
representing the state space
Mathematical formulation of quantum mechanics
The mathematical formulations of quantum mechanics are those mathematical formalisms that permit a rigorous description of quantum mechanics. Such are distinguished from mathematical formalisms for theories developed prior to the early 1900s by the use of abstract mathematical structures, such as...
of our quantum system, spanned by the
orthonormal computational basis states
.Furthermore assume we have a Hermitian
Hermitian
A number of mathematical entities are named Hermitian, after the mathematician Charles Hermite:*Hermitian adjoint*Hermitian connection, the unique connection on a Hermitian manifold that satisfies specific conditions...
projection operator
.Alternatively,
may be given in terms of aBoolean oracle function
and an orthonormal operational basis
,in which case
. can be used to partition into a direct sum of two mutually orthogonal subspaces,the good subspace
andthe bad subspace
:Given a normalized state vector
which has nonzero overlap with both subspaces, we canuniquely decompose it as
,where
,and
and are thenormalized projections of
into thesubspaces
and ,respectively.
This decomposition defines a two-dimensional subspace
, spanned by the vectors and .The probability of finding the system in a good state when measured
is
.Define a unitary operator
,where
flips the phase of the states in the good subspace, whereas flips the phase of the initial state .The action of this operator on
is given by and.Thus in the
subspace corresponds to a rotation by the angle
:.Applying
times on the stategives
,rotating the state between the good and bad subspaces.
After
iterations the probability of finding thesystem in a good state is
.The probability is maximized if we choose
.Up until this point each iteration increases the amplitude of the good states, hence
the name of the technique.
Applications
Assume we have an unsorted database with N elements, and an oracle function which can recognize the good entries we are searching for, and for simplicity.If there are G such entries in the database in total, then we can find them by
initializing the quantum computer into a uniform superposition
of all the database elements,
and running the above algorithm. In this case the overlap of the initial state with the good subspace is equal to the
square root of the frequency of the good entries in the database,
.If
, we can approximate the number of required iterations asMeasuring the state will now give one of the good entries with a high probability. Since each application of
requires a single oracle query (assuming that the oracle is implemented as a quantum gate),we can find a good entry with just
oracle queries, thus obtaining a quadratic speedup over the best possible classical algorithm.If we set G to one, the above scenario essentially reduces to the original Grover search.