Amplitude amplification

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 \mathcal{H} representing the state space of our quantum system, spanned by the orthonormal computational basis states B := \{ |k\rangle \}_{k=0}^{N-1}. Furthermore assume we have a Hermitian projection operator P: \mathcal{H} \to \mathcal{H}. Alternatively, P may be given in terms of a Boolean oracle function \chi:\mathbb{Z} \to \{0,1\} and an orthonormal operational basis B_{\text{op}} := \{|\omega_k\rangle \}_{k=0}^{N-1}, in which case

P := \sum_{\chi(k)=1} |\omega_k \rangle \langle \omega_k|.

P can be used to partition \mathcal{H} into a direct sum of two mutually orthogonal subspaces, the good subspace \mathcal{H}_1 and the bad subspace \mathcal{H}_0:


\begin{align}
\mathcal{H}_1 &:= \text{Image}\; P &= \operatorname{span}\{|\omega_k\rangle \in B_{\text{op}} \;|\; \chi(x) = 1\},\\
\mathcal{H}_0 &:= \text{Ker} \; P &= \operatorname{span}\{|\omega_k\rangle \in B_{\text{op}} \;|\; \chi(x) = 0\}.
\end{align}

Given a normalized state vector |\psi\rangle \in \mathcal{H} which has nonzero overlap with both subspaces, we can uniquely decompose it as

|\psi\rangle = \sin(\theta) |\psi_1\rangle  +\cos(\theta) |\psi_0\rangle,

where \theta = \arcsin\left( \left| P |\psi\rangle \right| \right) \in [0, \pi/2], and |\psi_1\rangle and |\psi_0\rangle are the normalized projections of |\psi\rangle into the subspaces \mathcal{H}_1 and \mathcal{H}_0, respectively. This decomposition defines a two-dimensional subspace \mathcal{H}_\psi, spanned by the vectors |\psi_0\rangle and |\psi_1\rangle. The probability of finding the system in a good state when measured is \sin^2(\theta).

Define a unitary operator Q(\psi, P) := -S_\psi S_P \,\!, where


\begin{align}
S_\psi &= I -2|\psi\rangle \langle\psi|\quad \text{and}\\
S_P    &= I -2 P.
\end{align}

S_P flips the phase of the states in the good subspace, whereas S_\psi flips the phase of the initial state |\psi\rangle.

The action of this operator on \mathcal{H}_\psi is given by

Q |\psi_0\rangle = -S_\psi |\psi_0\rangle = (2\cos^2(\theta)-1)|\psi_0\rangle +2 \sin(\theta) \cos(\theta) |\psi_1\rangle and
Q |\psi_1\rangle =  S_\psi |\psi_1\rangle = -2 \sin(\theta) \cos(\theta) |\psi_0\rangle +(1-2\sin^2(\theta))|\psi_1\rangle.

Thus in the \mathcal{H}_\psi subspace Q corresponds to a rotation by the angle 2\theta\,\!:

Q = \begin{pmatrix}
\cos(2\theta) & \sin(2\theta)\\
-\sin(2\theta) & \cos(2\theta)
\end{pmatrix}.


Applying Q n times on the state |\psi\rangle gives

Q^n |\psi\rangle = \cos((2n+1) \theta) |\psi_0\rangle +\sin((2n+1)\theta) |\psi_1\rangle,

rotating the state between the good and bad subspaces. After n iterations the probability of finding the system in a good state is \sin^2((2n+1)\theta)\,\!.
The probability is maximized if we choose

n = \left\lfloor\frac{\pi}{4\theta}\right\rfloor.

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 \chi which can recognize the good entries we are searching for, and B_{\text{op}} = B 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

|\psi\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} |k\rangle

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, \sin(\theta) = |P |\psi\rangle|= \sqrt{G/N}. If \sin(\theta) \ll 1, we can approximate the number of required iterations as

n = \left\lfloor\frac{\pi}{4\theta}\right\rfloor
\approx \left\lfloor\frac{\pi}{4 \sin(\theta)}\right\rfloor
= \left\lfloor\frac{\pi}{4} \sqrt{\frac{N}{G}}\right\rfloor = O(\sqrt{N}).

Measuring the state will now give one of the good entries with a high probability. Since each application of S_P requires a single oracle query (assuming that the oracle is implemented as a quantum gate), we can find a good entry with just O(\sqrt{N}) 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.

References[edit]

  1. ^ 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. 
  2. ^ 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. 
  3. ^ Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp (2000-05-15). "Quantum Amplitude Amplification and Estimation". arXiv:quant-ph/0005055 [quant-ph].