Quantum-OraclesQuantum Oracles

Bei einem Oracle-$O $ handelt es sich um einen "Blackbox"-Vorgang, der als Eingabe für einen anderen Algorithmus verwendet wird.An oracle $O$ is a "black box" operation that is used as input to another algorithm. Häufig werden solche Vorgänge mithilfe eines klassischen Funktions $f definiert: \ {0, 1 \ } ^ n \to \ {0, 1 \ } ^ m, $ der eine binäre $n $ -Bit-Eingabe annimmt und eine binäre $m $ -Bit-Ausgabe erzeugt.Often, such operations are defined using a classical function $f : \{0, 1\}^n \to \{0, 1\}^m$ which takes an $n$-bit binary input and produces an $m$-bit binary output. Beachten Sie hierzu eine bestimmte binäre Eingabe $x = (x_ {0 } , x_ {1 } , \dots, x_ {n-1 } ) $.To do so, consider a particular binary input $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Wir können Qubit-Zustände als "$ \ket { \vec{x } } = \ket{x_ {0 } } \otimes \ket{x_ {1 } } \otimes \cdots \otimes \ket{x_ {n-1 } } $" bezeichnen.We can label qubit states as $\ket{\vec{x}} = \ket{x_{0}} \otimes \ket{x_{1}} \otimes \cdots \otimes \ket{x_{n-1}}$.

Wir könnten zuerst versuchen, $O zu definieren, $ sodass $O \ket {x } = \ket{f (x)} $, aber dies hat einige Probleme.We may first attempt to define $O$ so that $O\ket{x} = \ket{f(x)}$, but this has a couple problems. Erstens können $f $ eine andere Größe von Eingabe und Ausgabe haben ($n \nE m $ ), sodass beim Anwenden von $O $ die Anzahl der Qubits im Register geändert würde.First, $f$ may have a different size of input and output ($n \ne m$), such that applying $O$ would change the number of qubits in the register. Zweitens: auch wenn $n = m $ ist, ist die Funktion möglicherweise nicht invertierbar: Wenn $f (x) = f (y) $ für einige $x \nE y $ , $O \ket {x } = O \ket {y $, } aber $O ^ \dagger o \ket {x } \nE o ^ \dagger o \ket {y } $.Second, even if $n = m$, the function may not be invertible: if $f(x) = f(y)$ for some $x \ne y$, then $O\ket{x} = O\ket{y}$ but $O^\dagger O\ket{x} \ne O^\dagger O\ket{y}$. Dies bedeutet, dass wir den Adjoint-Vorgang nicht erstellen können $O ^ \dagger $ , und für Oracles muss ein Adjoint-Element definiert sein.This means we won't be able to construct the adjoint operation $O^\dagger$, and oracles have to have an adjoint defined for them.

Definieren eines Oracle-Effekts durch seine Auswirkung auf den Berechnungsbasis StatusDefining an oracle by its effect on computational basis states

Wir können diese beiden Probleme behandeln, indem wir ein zweites Register $m $ Qubits einführen, um unsere Antwort zu speichern.We can deal with both of these problems by introducing a second register of $m$ qubits to hold our answer. Anschließend definieren wir die Auswirkung des Oracle auf alle Berechnungs Status Zustände: für alle $x \in \ {0, 1 \ } ^ n $ und $y \in \ {0, 1 \ } ^ m $ ,Then we will define the effect of the oracle on all computational basis states: for all $x \in \{0, 1\}^n$ and $y \in \{0, 1\}^m$,

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

Nun $O = O ^ \dagger $ by Construction, daher haben wir beide früheren Probleme gelöst.Now $O = O^\dagger$ by construction, thus we have resolved both of the earlier problems.

Tipp

Um zu sehen, dass $O = O ^ {\dagger } $ lautet, beachten Sie, dass $O ^ 2 = \boldone $ seit $a \oplus b \oplus b = a $ für alle $a, b \in { 0, 1 } $.To see that $O = O^{\dagger}$, note that $O^2 = \boldone$ since $a \oplus b \oplus b = a$ for all $a, b \in {0, 1}$. Folglich $O \ket{x } \ket{y \oplus f (x)} = \ket{x } \ket{y \oplus f (x) \oplus f (x)} = \ket{x } \ket{y } $.As a result, $O \ket{x} \ket{y \oplus f(x)} = \ket{x} \ket{y \oplus f(x) \oplus f(x)} = \ket{x} \ket{y}$.

Wichtig: die Definition eines Oracle auf diese Weise für jeden Berechnungsbasis Status $ \ket{x } \ket{y } $ definiert auch, wie $O $ für jeden anderen Zustand agiert.Importantly, defining an oracle this way for each computational basis state $\ket{x}\ket{y}$ also defines how $O$ acts for any other state. Dies folgt unmittelbar daran, dass $O $ , wie alle Quantum-Vorgänge, in dem Zustand, auf den er angewendet wird, linear ist.This follows immediately from the fact that $O$, like all quantum operations, is linear in the state that it acts on. Stellen Sie sich beispielsweise den Hadamard-Vorgang vor, der durch $H \ket{0 } = \ket { +} $ und $H \ket{1= } \ket { -} $ definiert wird.Consider the Hadamard operation, for instance, which is defined by $H \ket{0} = \ket{+}$ and $H \ket{1} = \ket{-}$. Wenn Sie wissen möchten, wie $H $ mit "$ \ket { +} $" funktioniert, können wir diese $H linear verwenden. $If we wish to know how $H$ acts on $\ket{+}$, we can use that $H$ is linear,

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

Wenn wir unsere Oracle-$O definieren $ , können wir auf ähnliche Weise den Status $ \ket { \psi } $ auf $n + m- $ Qubits schreiben alsIn the case of defining our oracle $O$, we can similarly use that any state $\ket{\psi}$ on $n + m$ qubits can be written as

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

wobei $ \alpha: \ {0, 1 \ } ^ n \times \ {0, 1 \ } ^ m \to \mathbb{c } $ die Koeffizienten des Zustands $ \ket { \psi } $ darstellt.where $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to \mathbb{C}$ represents the coefficients of the state $\ket{\psi}$. Demnach sindThus,

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

Phasen-OraclesPhase oracles

Alternativ $ dazu können Sie $f in eine Oracle-$O codieren, $ indem Sie eine Phase auf der Grundlage der Eingabe für $O anwenden $ .Alternatively, we can encode $f$ into an oracle $O$ by applying a phase based on the input to $O$. Beispielsweise können wir $O so definieren $ , dass $ $ \begin{align}For instance, we might define $O$ such that $$ \begin{align} O \ket{x } = (-1) ^ {f (x)} \ket{x } .O \ket{x} = (-1)^{f(x)} \ket{x}. \end{align}\end{align} $ $ Wenn eine Phase-Oracle zuerst in einem Compute-Status $ \ket{x $ auf ein Register angewendet wird } , ist diese Phase eine globale Phase und daher nicht Observable.$$ If a phase oracle acts on a register initially in a computational basis state $\ket{x}$, then this phase is a global phase and hence not observable. Ein solches Oracle kann jedoch eine sehr leistungsfähige Ressource sein, wenn Sie auf eine übergeordnete Position oder einen kontrollierten Vorgang angewendet wird.But such an oracle can be a very powerful resource if applied to a superposition or as a controlled operation. Stellen Sie sich z. b. einen Phasen-Orcale $O _F $ für eine Single-Qubit-Funktion $f dar $ .For example, consider a phase orcale $O_f$ for a single-qubit function $f$. Dann $ $ \begin{align}Then, $$ \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 } \ \ & = (-1) ^ {f (0)} (\ket{0+ } (-1) ^ {f (1)-f (0)} \ket{1 } )/\sqrt{2 } \ \ & = (-1) ^ {f (0)} Z ^ {f (0)-f (1)} \ket { +}.O_f \ket{+} & = O_f (\ket{0} + \ket{1}) / \sqrt{2} \\ & = ((-1)^{f(0)} \ket{0} + (-1)^{f(1)} \ket{1}) / \sqrt{2} \\ & = (-1)^{f(0)} (\ket{0} + (-1)^{f(1) - f(0)} \ket{1}) / \sqrt{2} \\ & = (-1)^{f(0)} Z^{f(0) - f(1)} \ket{+}. \end{align}\end{align} $$

Im Allgemeinen können beide Sichten von Oracles erweitert werden, um klassische Funktionen darzustellen, die anstelle eines einzelnen Bits reelle Zahlen zurückgeben.More generally, both views of oracles can be broadened to represent classical functions which return real numbers instead of only a single bit.

Das Auswählen der besten Methode zum Implementieren eines Oracle hängt stark davon ab, wie dieses Oracle innerhalb eines bestimmten Algorithmus verwendet werden soll.Choosing the best way to implement an oracle depends heavily on how this oracle will be used within a given algorithm. Der " Deutsch-Jozsa"-Algorithmus basiert z. b. auf dem Oracle, der auf die erste Weise implementiert ist, während der -Algorithmus von Grover auf die zweite Weise implementiert ist.For example, Deutsch-Jozsa algorithm relies on the oracle implemented in the first way, while Grover's algorithm relies on the oracle implemented in the second way.

Weitere Informationen finden Sie unter gilyén et al. 1711,00465.For more details, we suggest the discussion in Gilyén et al. 1711.00465.