Amplitude Amplification - Algorithm

Algorithm

The derivation presented here roughly follows the one given in . 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 :

\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 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

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

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 :

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


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.

Read more about this topic:  Amplitude Amplification