Amplitude Amplification

Get Amplitude Amplification essential facts below. View Videos or join the Amplitude Amplification discussion. Add Amplitude Amplification to your Like2do.com topic list for future reference or share this resource on social media.
## Algorithm

## Applications

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

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.

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 :

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.

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.

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

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Top US Cities

United States

Like2do.com was developed using defaultLogic.com's knowledge management platform. It allows users to manage learning and research. Visit defaultLogic's other partner sites below: