Delen via

Inzicht in kwantumorakels

  • Artikel

Een oracle, $O$, is een niet-belichte bewerking die wordt gebruikt als invoer voor een ander algoritme. Dergelijke bewerkingen worden vaak gedefinieerd met behulp van een klassieke functie $f: \{0, 1\}^n \to \{0, 1\}^m$, die een $n-bits$ binaire invoer gebruikt en een $binaire m-bit-uitvoer$ produceert. Hiervoor moet u een bepaalde binaire invoer $x (x_{0}, x_{1}, \dots, x_{n-1})$ overwegen.= U kunt qubitstatussen labelen als $\ket{\vec{x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$

U kunt eerst proberen O te definiëren $zodat $O\ket{x\ket{}=f(x)}$, maar deze methode heeft een aantal problemen.$ $Ten eerste kan f$ een andere grootte van invoer en uitvoer hebben ($n \ne m$), zodat het toepassen van $O$ het aantal qubits in het register zou wijzigen. Ten tweede, zelfs als n m, de functie mogelijk niet omkeerbaar is: als $f(x) f(y)$= voor sommige $x \ne y$, dan $O\ket{x=} O\ket{y}$, maar $O^\dagger O\ket{x}\ne O^\dagger O\ket{y.}$$=$ Dit betekent dat u de aangrenzende bewerking $O^\dagger$niet kunt maken en dat oracles hiervoor een aangrenzende definitie moeten hebben.

Een oracle definiëren op basis van het effect ervan op rekenkundige basisstatussen

U kunt beide problemen oplossen door een tweede register van $m$ qubits in te voeren om het antwoord vast te stellen. Definieer vervolgens het effect van het oracle op alle rekenkundige basisstatussen: voor alle x \0, 1\}^n$ en $y \in \{0, 1\}^m$,{\in$

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

= O $O^\dagger$ door constructie en u hebt beide eerdere problemen opgelost.

Tip

Als u wilt zien dat $$O=^{\dagger}$2\mathbf{1}$=sinds $een \oplus b \oplus b = b a$ voor alle $a, b \in{0, 1.}$ Als gevolg hiervan$, O \ket{x}\ket{y \oplus f(x)\ket{=}x}\ket{y \oplus f(x) \oplus f(x)}\ket{=x}\ket{y.}$

Belangrijk is dat het definiëren van een oracle op deze manier voor elke rekenkundige basisstatus $\ket{x}\ket{y}$ ook definieert hoe $O$ voor elke andere status fungeert. Dit gedrag volgt onmiddellijk van het feit dat $O$, net als alle kwantumbewerkingen, lineair is in de toestand waarop het reageert. Denk bijvoorbeeld aan de Hadamard-bewerking, die is gedefinieerd door $H \ket{0}=\ket{+}$ en $H \ket{1}=\ket{-}$. Als u wilt weten hoe $H$ werkt op $\ket{+}$, kunt u die $H$ lineair gebruiken,

$$\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 (\ket{{0} + \ket{{1} +{0}\ket{-{1}\ket{ ) . =\ket{{0} \end{align} $$

Wanneer u het oracle $O$ definieert, kunt u op dezelfde manier gebruiken dat elke status $\ket{\psi}$ op $n + m$ qubits kan worden geschreven als

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

waarbij $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ de coëfficiënten van de toestand $\ket{\psi}$vertegenwoordigt. Dus

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

Faseorakels

U kunt f ook coderen $in een oracle $O$ door een fase toe te passen op basis van de invoer op $O$.$ U kunt bijvoorbeeld O zo definiëren $dat $$\begin{\begin{align} O \ket{x=} (-1)^{f(x)}\ket{x.}$ \end{align} $$

Als een faseorakel in eerste instantie in een rekenkundige basistoestand $\ket{x}$ op een register reageert, is deze fase een globale fase en dus niet waarneembaar. Maar een dergelijk oracle kan een krachtige resource zijn als deze wordt toegepast op een superpositie of als een gecontroleerde bewerking. Denk bijvoorbeeld aan een faseorakel $O_f$ voor een functie $met één qubit f$. $$\begin{align} Vervolgens 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)\ket{{1}}) /&\sqrt{{2}=\\ (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+.} \end{align} $$

Notitie

Houd er rekening mee dat $Z^Z^{-1}={\dagger}=Z$ en daarom $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

Over het algemeen kunnen beide weergaven van oracles worden uitgebreid om klassieke functies weer te geven, wat reële getallen retourneert in plaats van slechts één bit.

Het kiezen van de beste manier om een oracle te implementeren, is sterk afhankelijk van hoe dit oracle moet worden gebruikt binnen een bepaald algoritme. Het Deutsch-Jozsa-algoritme is bijvoorbeeld afhankelijk van het oracle dat op de eerste manier is geïmplementeerd, terwijl het algoritme van Grover afhankelijk is van het oracle dat op de tweede manier is geïmplementeerd.

Zie de discussie in Gilyén et al. 1711.00465 voor meer informatie.

Gerelateerde inhoud