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. Bibcode:1997quant.ph..4027B. arXiv:quant-ph/9704027 .**^**Grover, Lov K. (May 1998). "Quantum Computers Can Search Rapidly by Using Almost Any Transformation".*Phys. Rev. Lett*.**80**(19): 4329-4332. Bibcode:1998PhRvL..80.4329G. arXiv:quant-ph/9712011 . 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 [quant-ph].

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