Amplitude amplification

Amplitude amplification is a technique in quantum computing that generalizes the idea behind 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, and independently rediscovered by Lov Grover in 1998.

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

${\displaystyle P}$ can be used to partition ${\displaystyle {\mathcal {H}}}$ into a direct sum of two mutually orthogonal subspaces, the good subspace ${\displaystyle {\mathcal {H}}_{1}}$ and the bad subspace ${\displaystyle {\mathcal {H}}_{0}}$:$${\displaystyle {\begin{aligned}{\mathcal {H}}_{1}&:={\text{Image}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=1\},\\{\mathcal {H}}_{0}&:={\text{Ker}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=0\}.\end{aligned}}}$$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 \rangle \in {\mathcal {H}}}$ into a state belonging to ${\displaystyle {\mathcal {H}}_{1}}$.

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

where ${\displaystyle \theta =\arcsin \left(\left|P|\psi \rangle \right|\right)\in [0,\pi /2]}$, and ${\displaystyle |\psi _{1}\rangle }$ and ${\displaystyle |\psi _{0}\rangle }$ are the normalized projections of ${\displaystyle |\psi \rangle }$ 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}\rangle }$ and ${\displaystyle |\psi _{1}\rangle }$. The probability of finding the system in a good 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 the good subspace, whereas ${\displaystyle S_{\psi }}$ flips the phase of the initial state ${\displaystyle |\psi \rangle }$.