A kvantumorákulumok ismertetése

Az oracle ( $O$) egy nem létező művelet, amelyet egy másik algoritmus bemeneteként használnak. Az ilyen műveleteket gyakran egy klasszikus f : \{0, 1\}^n \to \{0, 1\}^m$ függvény $használatával definiálják, amely egy $n$ bites bináris bemenetet vesz igénybe, és m-bit$ bináris kimenetet hoz létre$. Ehhez fontolja meg egy adott x bináris bemenetet $= (x_{0}, x_{1}, \dots, x_{n-1})$. A qubitállapotokat $\ket{\vec{x\ket{=}}x_{\otimes{0}}\ket{x_x_\otimes{1}}\otimes\ket{\cdots{n-1}}$ formátumban címkézheti.

Először megpróbálhatja az O-t$ úgy definiálni$, hogy $o\ket{x=}\ket{f(x)}$ legyen, de ez a módszer több problémával is rendelkezik. Először is előfordulhat, $hogy az f$ bemenetének és kimenetének mérete eltérő ($n \ne m$), így az O$ alkalmazása $megváltoztatná a qubitek számát a nyilvántartásban. Másodszor, még akkor is, ha n m, a függvény nem lehet invertálható: ha $f(x) = f(y)$ egy x $\ne y$, akkor $O\ket{x}= O\ket{y}$, de $O^\dagger O\ket{x}\ne O^\dagger O\ket{y.}$$= $ Ez azt jelenti, hogy nem lehet létrehozni az O^\dagger$szomszédos műveletet$, és az orákulumoknak meg kell határozniuk egy szomszédos műveletet.

Oracle meghatározása a számítási alapállapotokra gyakorolt hatása alapján

Mindkét probléma megoldásához be kell vezetnie egy második m$ qubit-regisztert $a válasz tárolásához. Ezután határozza meg az oracle hatását az összes számítási alapállapotra: az összes x \0, 1\}^n$ és $y \in \{0, 1\}^m$,{\in $

$$\begin{\begin{align}O(\ket{x}\ket{\otimesy})\ket{= x\otimes}\ket{y \oplus f(x).} \end{align} $$

Most $O = O^\dagger$ szerkezet szerint, és megoldotta mindkét korábbi problémát.

Fontos, hogy az x y}$ számítási alapállapothoz}\ket{$\ket{ ily módon definiált oracle azt is meghatározza, hogy az O$ hogyan $viselkedik bármely más állapotban. Ez a viselkedés közvetlenül abból a tényből következik, hogy $az O$, mint minden kvantumművelet, lineáris abban az állapotban, amelyen működik. Vegyük például a Hadamard műveletet, amely H \ket{0}\ket{=+}$ és $H .$\ket{1}=\ket{-}$ Ha tudni szeretné, hogyan $működik a H$ a +}$-on$\ket{, használhatja, hogy $a H$ lineáris,

$$\begin{align}H\ket{+}& =\frac{1}{\sqrt{{2}} H(\ket{0} + \ket{{1}) ={2}}\frac{1}{\sqrt{(H\ket{0} + H\ket{1}) \\& =\frac{1}{\sqrt{2}} (\ket{+} + \ket{{-}) =\frac12 ({0}\ket{ + + \ket{\ket{{0}{1} -{1}\ket{ ) . =\ket{{0} \end{align} $$

Az oracle $O$ definiálásakor hasonlóképpen használhatja, hogy az n + m$ qubiteken lévő $állapotok $\ket{\psi}$ bármilyen

$$\begin{\begin{align}\ket{\psi}&Amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}. \end{align} $$

$\alpha Itt: \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ az állapot $\ket{\psi}$együtthatóit jelöli. Így

$$\begin{\begin{align}O \ket{\psi}& = O \sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m\alpha}(x, y) \ket{x\ket{}y\\&}amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) O \ket{x}\ket{y\\&}amp; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m\alpha}(x, y) \ket{x}\ket{y \oplus f(x)}. \end{align} $$

Fázisorákulumok

Azt is megteheti, hogy f-et egy oracle $O-ba$ kódol$, ha egy fázist alkalmaz az O$ bemenete $$ alapján. O-t például úgy definiálhat$$, hogy $$\begin{align}\begin{O \ket{x}= (-1)^{f(x)}\ket{x.} \end{align} $$

Ha egy fázisorákulum kezdetben x számítási alapállapotú $\ket{}$regiszteren működik, akkor ez a fázis globális fázis, ezért nem figyelhető meg. Az ilyen oracle azonban hatékony erőforrás lehet, ha szuperpozícióra vagy szabályozott műveletre alkalmazzák. Vegyük például az f$ egy qubites függvény $fázis oracle $O_f$. $$\begin{align} Ezután O_f \ket{+}& = O_f (\ket{0} +{1}\ket{ ) /\\&\sqrt{{2} amp; = ((-1)^{f(0)}\ket{0} + (-1)^{f(1)\ket{1}}) /&\sqrt{2}\\ amp; = (-1)^{f(0)} ({0}\ket{ + (-1)^{f(1) - f(0){1}\ket{}) /\\{2}&\sqrt{ amp; = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+.} \end{align} $$

Általánosságban elmondható, hogy az orákulumok mindkét nézete kiterjeszthető a klasszikus függvények megjelenítésére, amelyek valós számokat adnak vissza egyetlen bit helyett.

Az oracle implementálásának legjobb módjának kiválasztása nagyban függ attól, hogy az oracle hogyan használható egy adott algoritmuson belül. A Deutsch-Jozsa algoritmus például az első módon implementált oracle-ra támaszkodik, míg a Grover algoritmusa a második módon implementált oracle-ra támaszkodik.

További információ: Gilyén 1711.00465.

Kapcsolódó tartalom

• Grover-algoritmus
• Kvantum köztes ábrázolás
• Vektorok és mátrixok
• T kapuk és T-gyárak