Descripción de los oráculos cuánticos
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.}}$
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$ podría tener un tamaño diferente de entrada y 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 algunas $x \ne y$, a continuación$, O\ket{x}= O\ket{y}$, pero $O^\dagger O^\ne} O\ket{^\dagger O^ O\ket{y.}$$= $ Esto significa que no se puede construir la operación $adyacente O^\dagger$, y los oráculos tienen que tener definido un adyacente 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 O = ^\dagger$ por construcción y usted resolvió 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 $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{\begin{align}\ket{\psi}&erio; =\sum_{x \in \{0, 1\}^n, y \in \{0, 1\}^m}\alpha(x, y) \ket{x}\ket{y}. \end{align} $$
Aquí, $\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, consulte la discusión en Gilyén 1711.00465.