Arbeiten Sie mit und definieren Sie Quantenorakel

  • Artikel

Ein Orakel, $O$, ist ein nicht exponierter Vorgang, der als Eingabe für einen anderen Algorithmus verwendet wird. Häufig werden solche Vorgänge mit einer klassischen Funktion $f : \{0, 1\}^n \to \{0, 1\}^m$ definiert, die eine $n-Bit-Binäreingabe$ übernimmt und eine $binäre m-Bit-Ausgabe$ 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 Qubitzustä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 einige Probleme.$ Zunächst könnte $f$ eine verschiedene Größe des Ein- und Ausgangs aufweisen ($n \ne m$), so dass die Anwendung von $O$ die Anzahl der Qubits im Register ändern würde. Zweitens: Sogar wenn $n = m$, ist die Funktion möglicherweise nicht invertierbar: bei $f(x) = f(y)$ für einige $x \ne y$, dann gilt $O\ket{x}= O\ket{y}$, aber $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Dies bedeutet, dass Sie nicht in der Lage sein werden, den angrenzenden Vorgang $O^\dagger$ zu erstellen, und für Orakel muss ein angrenzendes Element definiert sein.

Definieren Sie einen Orakel anhand seiner Auswirkung auf rechnerische Grundzustände

Sie können beide Probleme lösen, indem Sie ein zweites Register von $m-Qubits$ einführen, um die Antwort zu enthalten. Definieren Sie dann die Wirkung des Orakels auf allen Berechnungszustä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 Konstruktion, und Sie haben beide 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 ergibt sich unmittelbar aus der Tatsache, dass $O$ wie alle Quantenvorgänge linear in dem Zustand ist, auf den es wirkt. Betrachten Sie beispielsweise den Hadamard-Vorgang, der durch $H\ket{=\ket{0} +}$ und $H \ket{1}=\ket{-}$definiert wird. Wenn Sie wissen möchten, wie $H$ auf $\ket{+}$ wirkt, können Sie verwenden, dass $H$ linear ist,

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

Wenn Sie das Orakel $O$ definieren, können Sie auf ähnliche Weise verwenden, dass jeder Zustand $\ket{\psi}$ auf $n + m-Qubits$ als geschrieben werden kann.

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

Dabei stellt $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ 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 Orakel $O$ codieren$, indem Sie eine Phase basierend auf der Eingabe auf $O$ anwenden. Beispielsweise können Sie O so definieren$, dass\begin{$$\begin{align} 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 $\ket{x}$ befindet, dann ist diese Phase eine globale Phase und somit nicht beobachtbar. Ein solches Orakel kann jedoch eine leistungsfähige Ressource sein, wenn es auf eine Überlagerung oder als kontrollierter Vorgang angewendet wird. Betrachten Sie beispielsweise einen Phasen-Orakel $O_f$ für eine Einzel-Qubit-Funktion$f$. $$\begin{align} Dann 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} $$

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 Orakeln erweitert werden, um klassische Funktionen darzustellen, die statt nur ein einzelnes Bit reelle Zahlen zurückgeben.

Die Wahl der besten Methode zum Implementieren eines Orakels hängt stark davon ab, wie dieses Orakel 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 et al. 1711.00465.

Nächste Schritte