Amplitude amplification is a technique inquantum computing that generalizes the idea behindGrover's search algorithm, and gives rise to a family ofquantum algorithms.It was discovered byGilles Brassard andPeter Høyer in 1997,^[1] and independently rediscovered byLov 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 by Brassard et al. in 2000.^[3]Assume we have an${\displaystyle N}$-dimensionalHilbert space${\displaystyle \mathcal{H}}$ representing thestate space of a quantum system, spanned by the orthonormal computational basis states${\displaystyle B:=\{|k⟩{\}}_{k=0}^{N-1}}$.Furthermore assume we have aHermitianprojection operator${\displaystyle P:\mathcal{H}\to \mathcal{H}}$.Alternatively,${\displaystyle P}$ may be given in terms of a Booleanoracle function${\displaystyle \chi :\mathbb{Z}\to \{0,1\}}$and an orthonormal operational basis${\displaystyle B_{\text{op}}:=\{|{\omega }_k⟩{\}}_{k=0}^{N-1}}$,in which case

${\displaystyle P:=\sum _{\chi (k)=1}|{\omega }_k⟩⟨{\omega }_k|}$.

${\displaystyle P}$ can be used to partition${\displaystyle \mathcal{H}}$ into a direct sum of two mutually orthogonal subspaces, thegood subspace${\displaystyle {\mathcal{H}}_1}$ and thebad subspace${\displaystyle {\mathcal{H}}_0}$:In other words, we are defining a "good subspace"${\displaystyle {\mathcal{H}}_1}$ via the projector${\displaystyle P}$. The goal of the algorithm is then to evolve some initial state${\displaystyle |\psi ⟩\in \mathcal{H}}$ into a state belonging to${\displaystyle {\mathcal{H}}_1}$.

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

${\displaystyle |\psi ⟩=\sin (\theta )|{\psi }_1⟩+\cos (\theta )|{\psi }_0⟩}$,

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

Define a unitary operator${\displaystyle Q(\psi ,P):=-S_{\psi }{S}_P}$, where

${\displaystyle S_P}$ flips the phase of the states in thegood subspace, whereas${\displaystyle S_{\psi }}$ flips the phase of the initial state${\displaystyle |\psi ⟩}$.

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

${\displaystyle Q|{\psi }_0⟩=-S_{\psi }|{\psi }_0⟩=(2{\cos }^2(\theta )-1)|{\psi }_0⟩+2\sin (\theta )\cos (\theta )|{\psi }_1⟩}$ and

${\displaystyle Q|{\psi }_1⟩=S_{\psi }|{\psi }_1⟩=-2\sin (\theta )\cos (\theta )|{\psi }_0⟩+(1-2{\sin }^2(\theta ))|{\psi }_1⟩}$.

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

.

Applying${\displaystyle Q}$${\displaystyle n}$ times on the state${\displaystyle |\psi ⟩}$gives

${\displaystyle Q^n|\psi ⟩=\cos ((2n+1)\theta )|{\psi }_0⟩+\sin ((2n+1)\theta )|{\psi }_1⟩}$,

rotating the state between thegood andbad subspaces.After${\displaystyle n}$ iterations the probability of finding thesystem in agood state is${\displaystyle {\sin }^2((2n+1)\theta )}$.
The probability is maximized if we choose

${\displaystyle n=\lfloor \frac{\pi }{4\theta }\rfloor }$.

Up until this point each iteration increases the amplitude of thegood states, hence the name of the technique.

Assume we have an unsorted database with N elements, and anoracle function${\displaystyle \chi }$ which can recognize thegood entries we are searching for, and${\displaystyle B_{\text{op}}=B}$ for simplicity.

If there are${\displaystyle G}$good entries in the database in total, then we can find them by initializing aquantum register${\displaystyle |\psi ⟩}$ with${\displaystyle n}$qubits where${\displaystyle 2^n=N}$ intoa uniform superposition of all the database elements${\displaystyle N}$ such that

${\displaystyle |\psi ⟩=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}|k⟩}$

and running the above algorithm. In this case the overlap of the initial state with thegood subspace is equal to the square root of the frequency of thegood entries in the database,${\displaystyle \sin (\theta )=|P|\psi ⟩|=\sqrt{G/N}}$. If${\displaystyle \sin (\theta )\ll 1}$, we can approximate the number of required iterations as

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

Measuring the state will now give one of thegood entrieswith high probability. Since each application of${\displaystyle S_P}$ requires a single oracle query (assuming that the oracle is implemented as aquantum gate), we can find agood entry with just${\displaystyle O(\sqrt{N})}$ oracle queries, thus obtaining a quadratic speedup over the best possible classical algorithm. (The classical method for searching the database would be to perform the query for every${\displaystyle e\in \{0,1,\dots ,N-1\}}$ until a solution is found, thus costing${\displaystyle O(N)}$ queries.) Moreover, we can find all${\displaystyle G}$ solutions using${\displaystyle O(\sqrt{GN})}$ queries.

If we set the size of the set${\displaystyle G}$ to one, the above scenario essentially reduces to the originalGrover search.

Suppose that the number ofgood entries is unknown. We aim to estimate${\displaystyle \tilde{G}}$ such that${\displaystyle (1-\delta )G\le \tilde{G}\le (1+\delta )G}$ for small${\displaystyle \delta >0}$. We can solve for${\displaystyle \tilde{G}}$ by applying the quantum phase estimation algorithm on unitary operator${\displaystyle Q}$.

Since${\displaystyle e^{2i\theta }}$ and${\displaystyle e^{-2i\theta }}$ are the only two eigenvalues of${\displaystyle Q}$, we can let their corresponding eigenvectors be${\displaystyle |{\psi }_1⟩}$ and${\displaystyle |{\psi }_2⟩}$. We can find the eigenvalue${\displaystyle e^{2i\theta }}$ of${\displaystyle |\psi ⟩}$, which in this case is equivalent to estimating the phase${\displaystyle \theta }$. This can be done by applying Fourier transforms and controlled unitary operations, as described in the quantum phase estimation algorithm. With the estimate${\displaystyle \tilde{\theta }}$, we can estimate${\displaystyle \sin \theta }$, which in turn estimates${\displaystyle G}$.

Suppose we want to estimate${\displaystyle \theta }$ with arbitrary starting state${\displaystyle |s⟩}$, instead of the eigenvectors${\displaystyle |{\psi }_1⟩}$ and${\displaystyle |{\psi }_2⟩}$. We can do this by decomposing${\displaystyle |s⟩}$ into a linear combination of${\displaystyle |{\psi }_1⟩}$ and${\displaystyle |{\psi }_2⟩}$, and then applying the phase estimation algorithm.

• Quantum algorithms
• Search algorithms

• Articles with short description
• Short description matches Wikidata