Definición y trabajo con oráculos cuánticos

  • Artículo

Un oráculo, $O$, es una operación no expuesta que se usa como entrada a otro algoritmo. A menudo, estas operaciones se definen mediante una función $clásica f : \{0, 1\}^n \to \{0, 1\}^m$, que toma una $entrada binaria de n$ bits y genera una $salida binaria de m-bit$. Para ello, considere una entrada binaria determinada $x = (x_{0}, x_{1}, \dots, x_{n-1})$. Puede etiquetar los estados de cúbit como $\ket{\vec{x}}\ket{=x_{\ket{{0}}\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$

En primer lugar, puede intentar definir $O$ para que $O\ket{x}=\ket{f(x)}$, pero este método tenga un par de problemas. En primer lugar, $f$ puede tener un tamaño diferente de entrada y de salida ($n \ne m$), de modo que la aplicación de $O$ cambiaría el número de cúbits en el registro. En segundo lugar, incluso si $n = m$, es posible que la función no sea invertible: si $f(x) = f(y)$ para algunos $x \ne y$, entonces $O\ket{x}= O\ket{y}$ pero $O^\dagger O\ket{x}\ne O^\dagger O\ket{y}$. Esto significa que no podrá construir la operación $adyacente O^\dagger$, y los oráculos tienen que tener un adyacente definido para ellos.

Definición de un oráculo por su efecto en los estados de base computacional

Puede tratar ambos problemas introduciendo un segundo registro de $m$ cúbits para contener la respuesta. A continuación, defina el efecto del oráculo en todos los estados de base computacional: para todas las x \0, 1\}^n$ e 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} $$

Ahora $O = ^\dagger$ por construcción y ha resuelto ambos de los problemas anteriores.

Sugerencia

Para ver que $O = O^{\dagger}$, tenga en cuenta que $O^2 =\mathbf{1}$ porque $a \oplus b \oplus b = a$ para todo $a, b \in{0, 1}$. Como resultado, $O \ket{x}\ket{y \oplus f(x)}=\ket{x}\ket{y \oplus f(x) \oplus f(x)}=\ket{x}\ket{y}$.

Lo importante es que definir un oráculo de esta manera para cada estado de base computacional $\ket{x}\ket{y}$ también define cómo actúa $O$ para cualquier otro estado. Este comportamiento sigue inmediatamente del hecho de que O$, al igual que $todas las operaciones cuánticas, es lineal en el estado en el que actúa. Considere la operación Hadamard, por ejemplo, que se define mediante $H \ket{0}\ket{=+}$ y $H .\ket{1}=\ket{-}$ Si desea saber cómo $actúa H$ en $\ket{+}$, puede usar que $H$ es lineal,

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

Al definir el oráculo $O$, puede usar de forma similar que cualquier estado $\ket{\psi}$ en $n + m$ cúbits se puede escribir como

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

donde $\alpha : \{0, 1\}^n \times \{0, 1\}^m \to\mathbb{C}$ representa los coeficientes del estado $\ket{\psi}$. Así,

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

Oráculos de fase

Como alternativa, puede codificar $f$ en un oráculo $O$ aplicando una fase basada en la entrada a $O$. Por ejemplo, puede definir $O de forma que $$\begin{\begin{align} O \ket{x}= (-1)^{f(x)}\ket{x.}$ \end{align} $$

Si un oráculo de fase actúa en un registro inicialmente en un estado de base computacional $\ket{x}$, esta fase es una fase global y, por lo tanto, no se puede observar. Pero este tipo de oráculo puede ser un recurso eficaz si se aplica a una superposición o como una operación controlada. Por ejemplo, considere un oráculo de fase $O_f$ para una función $f$ de un único cúbit. A continuación, $$\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) (\ket{ + (-1)^{f(1) - f(0){1}}\ket{) / \sqrt{&\\{2}amp; = (-1)^{{f(0)} Z^{f(0) - f(1)}\ket{+.}{0}} \end{align} $$

Nota:

Tenga en cuenta que $Z^{-1}=Z^{\dagger}=Z$ y, por lo tanto, $Z^{f(0)-f(1)}=Z^{f(1)-f(0)}.$

Por lo general, ambas vistas de oráculos se pueden ampliar para representar funciones clásicas, que devuelven números reales en lugar de solo un solo bit.

La elección de la mejor manera de implementar un oráculo depende en gran medida de cómo se use este oráculo dentro de un algoritmo determinado. Por ejemplo, el algoritmo de Deutsch-Jozsa se basa en el oráculo implementado de la primera manera, mientras que el algoritmo de Grover se basa en el oráculo implementado de la segunda manera.

Para obtener más información, vea la discusión en Gilyén et al. 1711.00465.

Pasos siguientes