Amplitude amplification is a technique in quantum computing which 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,^[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

The derivation presented here roughly follows the one given by Brassard et al. in 2000.^[3] 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:=\sum _{\chi (k)=1}|\omega _{k}\rangle \langle \omega _{k}|}$.

${\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}}}$$

${\displaystyle {\mathcal {H}}_{1}}$

${\displaystyle P}$

${\displaystyle |\psi \rangle \in {\mathcal {H}}}$

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

${\displaystyle |\psi \rangle =\sin(\theta )|\psi _{1}\rangle +\cos(\theta )|\psi _{0}\rangle }$,

where ${\displaystyle \theta =\arcsin \left(\left|P|\psi \rangle \right|\right)\in }$, 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 {\begin{aligned}S_{\psi }&=I-2|\psi \rangle \langle \psi |\quad {\text{and}}\\S_{P}&=I-2P.\end{aligned}}}$

${\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 }$.

The action of this operator on ${\displaystyle {\mathcal{H}}_{\mathrm{\psi <!--\; \psi \; -->}}}$Zdroj:https://en.wikipedia.org?pojem=Amplitude_amplification
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.