Kvantumorákulumok működése és definiálása

  • Cikk

Az orákulum ( $O$) egy nem létező művelet, amelyet egy másik algoritmus bemeneteként használnak. Az ilyen műveleteket gyakran egy klasszikus f függvénnyel $definiálják: \{0, 1\}^n \to \{0, 1\}^m$, amely n$ bites bináris bemenetet használ$, és m-bit$ bináris kimenetet hoz létre$. Ehhez vegye figyelembe az 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}}$ címkével láthatja el.

Először megpróbálhatja az O-t$ úgy definiálni$, hogy $O\ket{x=}\ket{f(x)}$ legyen, de ennek a metódusnak több problémája is van. Először is, $az f$ eltérő méretű bemenettel és kimenettel ($n \ne m$) rendelkezhet, így az O$ alkalmazása $megváltoztatná a qubitek számát a regiszterben. Másodszor, még ha $n = m$ is, előfordulhat, hogy a függvény nem invertálható: ha $f(x) = f(y)$ néhány $x \ne y$ esetében, akkor $O\ket{x=} O\ket{y}$, de $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Ez azt jelenti, hogy nem fogja tudni létrehozni az O^\dagger$mellékműveletet$, és az orákulumoknak definiálni kell hozzájuk egy mellékintet.

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

Mindkét problémát úgy kezelheti, hogy bevezeti az m$ qubitek második regiszterét $a válasz tárolásához. Ezután határozza meg az orákulum hatását az összes számítási alapállapotra: minden 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$ építéssel, és mindkét korábbi problémát megoldotta.

Tipp

Az O^=megtekintéséhez vegye figyelembe, hogy $$az O^2 =\mathbf{1}$ a \oplus b \oplus b a =$ óta $az összes $a, b \in{0, 1}$ esetében.{\dagger}$ Ennek eredményeként O x}y \oplus f(x)\ket{=}x}\ket{y \oplus f(x) \oplus f(x)=\ket{}x}\ket{y.}$\ket{\ket{$

Fontos, hogy az egyes számítási alapállapotokhoz $\ket{így definiáljon egy orákulumot x}\ket{y}$ azt is, 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, amelyben működik. Vegyük például a Hadamard műveletet, amelyet a H\ket{=\ket{0} +}$ és $a H \ket{1}\ket{-}$=határoz meg.$ Ha tudni szeretné, hogyan $működik a H$ a +}$-on$\ket{, használhatja 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 O$ orákulum $definiálásakor hasonlóképpen használhatja azt is, hogy az n + m$ qubiten lévő $állapotok $\ket{\psi}$ bármilyen módon írhatók

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

ahol $\alpha : \{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-ra$ kódol$$, ha egy fázist alkalmaz az O$ bemenete $alapján. Definiálhat $például O-t$ úgy, hogy $$\begin{align}\begin{O \ket{x}= (-1)^{f(x)}\ket{x}. \end{align} $$

Ha egy fázisorákulum kezdetben egy 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 nagy teljesítményű erőforrás lehet, ha szuperpozícióra vagy ellenőrzött műveletként alkalmazzák. Vegyünk például egy fázisorákulum-O_f $$ egy egy qubites f$ függvényhez$. $$\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} $$

Megjegyzés

Vegye figyelembe, hogy $a Z^{-1}=Z^{\dagger}=Z$ és így $a Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

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

Az orákulum implementálásának legjobb módja nagyban függ attól, hogy ezt az orákulumot hogyan kell használni egy adott algoritmuson belül. A Deutsch-Jozsa algoritmus például az első módon implementált orákulumra támaszkodik, míg a Grover algoritmusa a második módon implementált oracle-ra támaszkodik.

További információt a Gilyén et al. 1711.00465 című témakörben talál.

Következő lépések