Présentation des oracles quantiques
Un oracle, $O$, est une opération non exposée utilisée comme entrée d’un autre algorithme. Souvent, ces opérations sont définies à l’aide d’une fonction $classique f : \{0, 1\}^n \to \{0, 1\}^m$, qui prend une $entrée binaire n$ bits et produit une $sortie binaire m$ bits. Pour ce faire, considérons une entrée binaire particulière $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Vous pouvez étiqueter les états qubit en tant que $\ket{\vec{x=\ket{}}x_{0}}\ket{\otimes{x_{1}}\otimes\otimes\ket{\cdotsx_{n-1.}}$
Vous pouvez d’abord tenter de définir $O$ afin que $O\ket{x=}\ket{f(x)}$, mais cette méthode présente quelques problèmes. Tout d’abord, $f$ peut avoir une taille différente d’entrée et de sortie ($n \ne m$), de sorte que l’application $d’O$ modifie le nombre de qubits dans le registre. Ensuite, même si $n = m$, la fonction peut ne pas être inversée : si $f(x) = f(y)$ pour un x \ne $y$, O $\ket{x=} O\ket{y}$ mais $O^\dagger O\ket{x}\ne O^\dagger O y y}$\ket{. Cela signifie que vous ne pouvez pas construire l’opération $d’adjoint O^\dagger$, et les oracles doivent avoir un adjoint défini pour eux.
Définir un oracle par son effet sur les états de base de calcul
Vous pouvez traiter ces deux problèmes en introduisant un deuxième registre de $qubits m$ pour contenir la réponse. Ensuite, définissez l’effet de l’oracle sur tous les états de calcul : pour tous les x \0, 1\}^n$ et $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} $$
Maintenant $O = ^\dagger$ en construction et vous avez résolu les deux problèmes précédents.
Conseil
Pour voir si $O = O^{\dagger}$, notez que $O^2 =\mathbf{1}$ depuis $a \oplus b \oplus b = a$ pour tout $a, b \in{0, 1}$. Par conséquent, $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.
Plus important encore, la définition d’un oracle de cette façon pour chaque état de base de calcul $\ket{x}\ket{y}$ définit également la manière dont $O$ agit pour tout autre état. Ce comportement suit immédiatement le fait que $O$, comme toutes les opérations quantiques, est linéaire dans l’état sur lequel il agit. Considérez l’opération Hadamard, par exemple, qui est définie $H \ket{0}\ket{=+}$ et $H .\ket{1}=\ket{-}$ Si vous souhaitez savoir comment $H$ agit sur $\ket{+}$, vous pouvez utiliser que $H$ est linéaire,
$$\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{{1} +{1}{0} \ket{\ket{- ) . =\ket{{0} \end{align} $$
Lors de la définition de l’oracle $O$, vous pouvez utiliser de la même façon que n $$\ket{\psi}$ + m$ qubits peuvent être écrits en tant qubits
$$\begin{\begin{align}\ket{\psi}&ère; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y)}\ket{\ket{ x y.} \end{align} $$
Ici, $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ représente les coefficients de l’état $\ket{\psi}$. Donc
$$\begin{\begin{align}O \ket{\psi}& ; = O \sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m\alpha}(x, y) \ket{\ket{}x 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} $$
Oracles de phase
Vous pouvez également encoder $f$ dans un O oracle $$ en appliquant une phase basée sur l’entrée à $O$. Par exemple, vous pouvez définir $O$ de sorte que\begin{$$\begin{align} O \ket{x=} (-1)^{f(x)}\ket{x.} \end{align} $$
Si un oracle de phase agit sur un registre initialement dans un état de base de calcul $\ket{x}$, cette phase est une phase globale qui n’est donc pas observable. Toutefois, un tel oracle peut être une ressource puissante si elle est appliquée à une superposition ou en tant qu’opération contrôlée. Par exemple, considérez un oracle de phase $O_f$ pour une fonction qubit unique $f$. Ensuite, $$\begin{align} 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} $$
Remarque
Notez que $Z^{-1}=Z^{\dagger}=Z$ et donc $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$
Plus généralement, les deux vues d’oracles peuvent être élargies pour représenter des fonctions classiques, qui retournent des nombres réels au lieu d’un seul bit.
Le choix de la meilleure façon d’implémenter un oracle dépend fortement de la façon dont cet oracle doit être utilisé dans un algorithme donné. Par exemple, l'algorithme Deutsch-Jozsa s’appuie sur l’oracle implémenté de la même façon, tandis que l'algorithme de Grover s’appuie sur l’oracle implémenté de la seconde façon.
Pour plus d’informations, consultez la discussion dans Gilyén 1711.00465.