Compartir a través de

Descripción de los oráculos cuánticos

  • Artículo

Un oráculo, $O$, es una operación no expuesta que se usa como entrada para 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úbits como $\ket{\vec{x=\ket{}}x_{0}}\ket{{\otimesx_\otimes{1}}\otimes\ket{\cdotsx_{n-1.}}$

Primero 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 definido un adjunto 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 todos los 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 O de oracle$, puede usar de forma similar que cualquier estado $\ket{\psi}$ en $n + m$ cúbits se puede escribir como$

$$\begin{align}\ket{\psi}&erio; =\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 O$ de oracle $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)} ({0}\ket{ + (-1)^{f(1) - f(0){1}\ket{}) /\\{2}&\sqrt{ amp; = (-1)^{f(0)} Z^{f(0) - f(1)}\ket{+.} \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.

Elegir la mejor manera de implementar un oráculo depende en gran medida de cómo se va a usar 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.

Contenido relacionado