Oráculos

Los oráculos son operaciones abstractas que generalmente son definidas utilizando la notación de funciones binarias clásicas:

$$f: \{0,1\}^n \rightarrow \{0,1\}^m$$

Los oráculos actúan como cajas negras y abstraen su implementación, que varía segun el contexto. Notar que si no se pueden encontrar circuitos reales (con puertas) para representar la funcionalidad el oráculo carece de uso práctico.

Los oráculos se utilizan, por ejemplo, en los algoritmos Deutsch-Jozsa y Grover. En el primero se usa para abstraer la función a determinar si es constante o balanceada, y en el segundo caso se utiliza para abstraer el suscinto sobre el cual buscar.

Estos se definen de forma general de la siguiente manera:

$$U_f(\ket{x} \otimes \ket{y}) = \ket{x} \otimes \ket{y \oplus f(x)}$$

Donde \(x\) es la entrada e \(y\) un registro que se utilizará como salida. La razon de la creación de un nuevo registro para salida es para permitir que la operación sea reversible, es decir que a partir de la salida se pueda saber cuál fue la entrada.

Vale por construcción que \(U_f=U_f^\dag\), permitiendo que para obtener el valor de entrada solo se deba aplicar nuevamente la operación.

Cálculo

Uso de oráculos

Los oráculos son utilizados para verificar el resultado de una entrada, o para poder distinguir (aplicando una fase) aquellos valores que pertenecen a la solución del problema. Utilizando la definicion matemática de oráculo, se puede verificar que la entrada $x$ sea una solución de $f$ reemplazando $y$ con "$0$" de la siguiente manera:

$$\begin{align} U_f(\ket{x} \otimes \ket{0}) =& \ket{x} \otimes \ket{0 \oplus f(x)}\\ =&\ket{x} \otimes \ket{f(x)} \end{align}$$

Al leer el segundo cubit se puede verificar si $x$ es solución o no de $f$.

De forma análoga, si se reemplaza $y$ con "$1$" se obtiene el complemento de $f(x)$ en el segundo cubit:

$$\begin{align} U_f(\ket{x} \otimes \ket{1}) =& \ket{x} \otimes \ket{1 \oplus f(x)}\\ =&\ket{x} \otimes \ket{\overline{f(x)}} \end{align}$$

Oráculo de Fase

Se suele utilizar el valor "$-$" en lugar de $y$ para distinguir aquellos valores que pertenecen a la solución del problema, con la precondición $m=1$, es decir que haya un solo bit de solución:

$$\begin{align} U_f(\ket{x} \otimes \ket{-}) =& U_f\left(\ket{x} \otimes \frac{\ket{0}-\ket{1}}{\sqrt{2}}\right)\\ =& U_f\left(\frac{\ket{x}\ket{0}-\ket{x}\ket{1}}{\sqrt{2}}\right)\\ =& \frac{1}{\sqrt{2}}U_f\left(\ket{x}\ket{0}-\ket{x}\ket{1}\right)\\ =& \frac{1}{\sqrt{2}}\left(U_f\ket{x}\ket{0}-U_f\ket{x}\ket{1}\right)\\ =& \frac{1}{\sqrt{2}}\left(\ket{x}\ket{f(x)}-\ket{x}\ket{\overline{f(x)}}\right)\\ =&\begin{cases} \frac{1}{\sqrt{2}}\left(\ket{x}\ket{0}-\ket{x}\ket{1}\right) && \text{si }f(x)=0\\ =\ket{x}\frac{\ket{0}-\ket{1}}{\sqrt{2}}=\ket{x}\ket{-}\\ \frac{1}{\sqrt{2}}\left(\ket{x}\ket{1}-\ket{x}\ket{0}\right) && \text{si }f(x)=1\\ =-\ket{x}\frac{1}{\sqrt{2}}\left(-\ket{1}+\ket{0}\right)=-\ket{x}\ket{-}\\ \end{cases}\\ =&(-1)^{f(x)}\ket{x}\ket{-}\\ \end{align}$$

Este oráculo es conocido como oráculo de fase. El último cubit no cambia nunca por lo que ciertas bibliografías simplifican enunciándolo de la siguiente manera:

$$P_f\ket{x}=(-1)^{f(x)}\ket{x}$$

Detalles adicionales

En ciertas ocasiones se utiliza combinado con el operador de difusión (por ejemplo el Operador de Grover), ya que permite seleccionar la solución al problema (cuando $f(x)=1$) invirtiendo su fase, para luego amplificar su amplitud.

Por otra parte, en el algoritmo de Deutsch-Jozsa se utiliza para identificar si la función es balanceada o constante.

Más información

Bibliografía:

Recomendada

Alternativa

Opcional

Libro

Capítulo 7.1.3 y 7.1.4, Introduction to Classical and Quantum Computing (Thomas G. Wong) [Inglés]

Video

Quantum Computing Course: 3.2.B Quantum Functions (Quantum Soar) [Inglés]

Otros

Understanding quantum oracles (Microsoft) [Inglés]

Libro

Capítulo 6.1.1, Quantum Computation and Quantum Information (Michael A. Nielsen; Isaac L. Chuang) [Inglés]