# Amplitude amplification

**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 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.

## Algorithm[edit]

The derivation presented here roughly follows the one given in
.^{[3]}
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 :

*good subspace*" via the projector . The goal of the algorithm is then to evolve some initial state into a state belonging to .

Given a normalized state vector with 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.

## Applications[edit]

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 *good* 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 to one, the above scenario essentially reduces to the original Grover search.

## References[edit]

**^**Gilles Brassard; Peter Høyer (June 1997). "An exact quantum polynomial-time algorithm for Simon's problem".*Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems*. IEEE Computer Society Press: 12–23. arXiv:quant-ph/9704027. Bibcode:1997quant.ph..4027B.**^**Grover, Lov K. (May 1998). "Quantum Computers Can Search Rapidly by Using Almost Any Transformation".*Phys. Rev. Lett*.**80**(19): 4329–4332. arXiv:quant-ph/9712011. Bibcode:1998PhRvL..80.4329G. doi:10.1103/PhysRevLett.80.4329.**^**Gilles Brassard; Peter Høyer; Michele Mosca; Alain Tapp (2000-05-15). "Quantum Amplitude Amplification and Estimation". arXiv:quant-ph/0005055.