Grundlegendes zu Quanten oracles
Ein Oracle, $O$, ist ein nicht exponierten Vorgang, der als Eingabe für einen anderen Algorithmus verwendet wird. Häufig werden solche Vorgänge mithilfe einer klassischen Funktion $f : \{0, 1\}^n \{0 \to , 1\}^m$ definiert, die eine $n-Bit-Binäreingabe$ verwendet und eine $m-Bit-Binärausgabe$ erzeugt. Für diesen Zweck erwägen Sie eine bestimmte binäre Eingabe $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Sie können qubit-Zustände als $\ket{\vec{x}}=\ket{x_\otimes{0}}{\ket{x_x_\otimes{1}}\otimes\ket{\cdots{n-1}}$ bezeichnen.
Sie können zuerst versuchen, O so zu definieren$, dass $O\ket{x\ket{}=f(x)}$, aber diese Methode hat ein paar Probleme.$ $Erstens könnte f$ eine andere Größe von Eingabe und Ausgabe ($n \ne m$) haben, sodass das Anwenden $von O$ die Anzahl der Qubits im Register ändern würde. Zweitens, selbst wenn $n = m$, ist die Funktion möglicherweise nicht invertierbar: wenn $f(x) = f(y)$ für einige $x \ne y$, dann $O\ket{x}= O\ket{y}$, aber $O^\dagger O x}\ne O\ket{^ O^\dagger O\ket{y}$. Dies bedeutet, dass Sie den angrenzenden Vorgang $O^\dagger$ nicht konstruieren können, und Oracles müssen für sie einen angrenzenden definiert haben.
Definieren Sie einen Orakel anhand seiner Auswirkung auf rechnerische Grundzustände
Sie können mit beiden Problemen umgehen, indem Sie ein zweites Register von $M-Qubits$ einführen, um die Antwort zu halten. Definieren Sie dann die Wirkung des Oracles auf allen rechenbasierten Zuständen: für alle x \0, 1\}^n$ und $y \in \{0, 1\}^m$,{\in $
$$\begin{\begin{align} O(\ket{x}\otimes\ket{y}) =\ket{x}\otimes\ket{y \oplus f(x)}. \end{align} $$
Jetzt $O = O^\dagger$ durch den Bau und Sie haben beide der früheren Probleme behoben.
Tipp
Um $O = O^{\dagger}$ zu erhalten, beachten Sie, dass $O^2 =\mathbf{1}$, da $a \oplus b \oplus b = a$ für alle $a, b \in{0, 1}$. Das Ergebnis ist: $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.
Wichtig ist, dass die Definition eines Orakels auf diese Weise für jeden Berechnungsbasisstatus $\ket{x}\ket{y}$ auch definiert wie $O$ sich auf jeden anderen Status auswirkt. Dieses Verhalten folgt unmittelbar der Tatsache, dass $O$ wie alle Quantenvorgänge linear in dem Zustand ist, an dem es wirkt. Betrachten Sie beispielsweise den Hadamard-Vorgang, der H\ket{=\ket{0} +}$ und $H \ket{1}\ket{-}$=definiert $ist. Wenn Sie wissen möchten, wie $H$ auf $\ket{+}$wirkt, können Sie diese $H$ linear verwenden.
$$\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} -{1}{0} \ket{\ket{) . =\ket{{0} \end{align} $$
Beim Definieren des Oracle $O$ können Sie auf ähnliche Weise verwenden, dass jeder Zustand $\ket{\psi}$ auf $n + m$ Qubits geschrieben werden kann.
$$\begin{\begin{align}\ket{\psi}&Ampere; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}. \end{align} $$
$\alpha Hier: \{0, 1\}^n \{0 \times , 1\}^m \to\mathbb{C}$ stellt die Koeffizienten des Zustands $\ket{\psi}$dar. Demnach sind
$$\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} $$
Phasen-Orakel
Alternativ können Sie f$ in ein Oracle $O$ codieren$, indem Sie eine Phase basierend auf der Eingabe auf $O$ anwenden. Sie können z. B. O$ so definieren$, dass\begin{align} $$\begin{O \ket{x}= (-1)^{f(x)x.}\ket{} \end{align} $$
Wenn ein Phasen-Orakel auf ein Register einwirkt, das sich zunächst in einem rechnerischen Grundzustand befindet $\ket{x}$, dann ist diese Phase eine globale Phase und somit nicht beobachtbar. Aber eine solche Oracle kann eine leistungsstarke Ressource sein, wenn sie auf eine Oberposition oder als kontrollierte Operation angewendet wird. Betrachten Sie beispielsweise einen Phasen-Orakel $O_f$ für eine Einzel-Qubit-Funktion$f$. Dann $$\begin{align} O_f \ket{+}& = O_f ( +\ket{0} \ket{{1}) / \sqrt{\\{2}& = ((-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{) / \sqrt{&{2}\\amp; = (-1)^{f(0) Z^{f(0)} - f(1)}\ket{+.} \end{align} $$
Hinweis
Beachten Sie, dass $Z^{-1}=Z^{\dagger}=Z$ und daher $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}$ ist.
Im Allgemeinen können beide Ansichten von Oraclen erweitert werden, um klassische Funktionen darzustellen, die reale Zahlen statt nur ein einzelnes Bit zurückgeben.
Die Wahl der besten Methode zur Implementierung eines Oracles hängt stark davon ab, wie dieses Oracle innerhalb eines bestimmten Algorithmus verwendet werden soll. Beispielsweise basiert der Deutsch-Jozsa-Algorithmus auf dem Orakel, das auf die erste Weise implementiert wurde, während derGrover´s Algorithmus auf dem Orakel basiert, das auf die zweite Weise implementiert wird.
Weitere Informationen finden Sie in der Diskussion in Gilyén 1711.00465.