Utiliser et définir des oracles Quantum

  • Article

Un oracle, $O$, est une opération non exposée qui est utilisée comme entrée dans un autre algorithme. Souvent, de telles 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-bit$ et produit une $sortie binaire m-bit$. 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 de qubit comme $\ket{\vec{x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$

Vous pouvez d’abord essayer de définir $O$ de sorte que $O\ket{x=}\ket{f(x)}$, mais cette méthode présente quelques problèmes. Premièrement, $f$ peut avoir une taille différente d’entrée et de sortie ($n \ne m$), de sorte que l’application de $O$ modifie le nombre de qubits dans le registre. Deuxièmement, même si $n = m$, la fonction ne peut pas être réversible : si $f(x) = f(y)$ pour un $x \ne y$, puis $O\ket{x}= O\ket{y}$, mais $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Cela signifie que vous ne pourrez pas construire l’opération $d’adjoint O^\dagger$, et que 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 gérer ces deux problèmes en introduisant un deuxième registre de $m$ qubits pour contenir la réponse. Ensuite, définissez l’effet de l’oracle sur tous les états de base 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 $= O^\dagger$ par 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 découle immédiatement du fait que $O$, comme toutes les opérations quantiques, est linéaire dans l’état sur lequel il agit. Prenons l’opération Hadamard, par exemple, qui est définie par $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{ +{1}\ket{+ \ket{{0} -{1}\ket{ ) . =\ket{{0} \end{align} $$

Lors de la définition de l’oracle $O$, vous pouvez également utiliser que n’importe quel état $\ket{\psi}$ sur $n + m$ qubits peut être écrit en tant que

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

où $\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{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} $$

Oracles de phase

Vous pouvez également encoder $f$ dans un oracle $O$ en appliquant une phase basée sur l’entrée à $O$. Par exemple, vous pouvez définir $O$ de telle 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. Mais 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} $$

Notes

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 des 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, voir la discussion dans Gilyén et al. 1711.00465.

Étapes suivantes