Amplitude amplification is a technique in quantum computing which generalizes the idea behind 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,[1] and independently rediscovered by Lov Grover in 1998.
[2] In a quantum computer, amplitude amplification can be used to obtain a quadratic speedup over several classical algorithms.
The derivation presented here roughly follows the one given by Brassard et al. in 2000.
representing the state space of a quantum system, spanned by the orthonormal computational basis states
Furthermore assume we have a Hermitian projection operator
may be given in terms of a Boolean oracle function
In other words, we are defining a "good subspace"
The goal of the algorithm is then to evolve some initial state
with nonzero overlap with both subspaces, we can uniquely decompose it as where
This decomposition defines a two-dimensional subspace
The probability of finding the system in a good state when measured is
flips the phase of the states in the good subspace, whereas
gives rotating the state between the good and bad subspaces.
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.
Assume we have an unsorted database with N elements, and an oracle function
good entries in the database in total, then we can find them by initializing a quantum register
into a uniform superposition of all the database elements
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,
, we can approximate the number of required iterations as Measuring the state will now give one of the good entries with high probability.
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.
(The classical method for searching the database would be to perform the query for every
to one, the above scenario essentially reduces to the original Grover search.
Suppose that the number of good entries is unknown.
by applying the quantum phase estimation algorithm on unitary operator
, which in this case is equivalent to estimating the phase
This can be done by applying Fourier transforms and controlled unitary operations, as described in the quantum phase estimation algorithm.
, and then applying the phase estimation algorithm.