Posterior: Algoritmo para el cálculo Arriba: Nociones básicas de Computación Anterior: Evaluación de funciones booleanas

Algoritmo de Deutsch-Jozsa

Sea $V=\{0,1\}$ el conjunto de valores de verdad clásicos. De las $2^2=4$ funciones booleanas $f:V\to V$ dos son constantes y las otras dos son equilibradas. Al nombrarlas

$$f_0:\begin{array}{ccc} 0 &\mapsto& 0 \\ 1 &\mapsto& 0 %%\\ ... ...n{array}{ccc} 0 &\mapsto& 1 \\ 1 &\mapsto& 1 %%\\ \end{array}$$

se tiene que las funciones constantes son $f_0$ y $f_3$, y las equilibradas son $f_1$ y $f_2$.

El propósito del algoritmo de Deutsch-Jozsa es decidir, para una $f$ dada, si acaso es constante o equilibrada ``utilizando un solo paso de cómputo''.

Sea $U_f$ una matriz permutación de orden $2^{2}\times 2^{2}$ tal que $U_f(\mbox{\bf e}_{x}\otimes \mbox{\bf e}_{z})= (\mbox{\bf e}_{x}\otimes \mbox{\bf e}_{(z+f(x))\mbox{\scriptsize mod }2})$. $U_f$ es pues unitaria. De hecho es muy similar al funcionamiento de la compuerta ``negación controlada'', salvo que en aquella, la función $f$ es propiamente la identidad. En la tabla 1 ilustramos la acción de $U_f$ refiriéndonos solamente a los índices de vectores básicos.

Recuadro 1: Acción de la matriz unitaria $U_f$ en el algoritmo de Deutsch-Jozsa.

$(x,z)$	$(x,(z+f(x))\mbox{ mod }2)$
(0,0)	(0,$f(0)$)
(0,1)	(0, $\overline{f(0)}$)
(1,0)	(1,$f(1)$)
(1,1)	(1, $\overline{f(1)}$)

Considerando el operador de Hadamard $H$, hagamos $H_2=H\otimes H$. Primero se tiene, $H(\mbox{\bf e}_0) = \mbox{\bf x}_0=\frac{1}{\sqrt{2}}(\mbox{\bf e}_0+\mbox{\bf e}_1)$ y $H(\mbox{\bf e}_0) = \mbox{\bf x}_1=\frac{1}{\sqrt{2}}(\mbox{\bf e}_0-\mbox{\bf e}_1)\in\mathbb{H}_1$ y luego $H_2(\mbox{\bf e}_0\otimes \mbox{\bf e}_1) = H(\mbox{\bf e}_0)\otimes H(\mbox{\bf e}_1) = \mbox{\bf x}_0\otimes \mbox{\bf x}_1$. Claramente, $\mbox{\bf x}_0\otimes \mbox{\bf x}_1 = \frac{1}{2}(\mbox{\bf e}_{00}-\mbox{\bf e}_{01}+\mbox{\bf e}_{10}-\mbox{\bf e}_{11})\in\mathbb{H}_2.$ Por tanto,

$$\begin{eqnarray*} U_f(\mbox{\bf x}_0\otimes \mbox{\bf x}_1) &=& \frac{1}{2}(\mbo... ...}_0\otimes \mbox{\bf x}_1 & \mbox{si } f=f_3 \end{array}\right. \end{eqnarray*}$$

En consecuencia,

$$\begin{eqnarray*} H_2U_fH_2(\mbox{\bf e}_0\otimes \mbox{\bf e}_1) = H_2U_f(\mbox... ...}_0\otimes \mbox{\bf e}_1 & \mbox{si } f=f_3 \end{array}\right. \end{eqnarray*}$$

vale decir, al aplicar el algoritmo cuántico $H_2U_fH_2$ (nótese que utilizamos notación algebraica: los operadores se aplican de derecha a izquierda), partiendo del vector básico $\mbox{\bf e}_0\otimes \mbox{\bf e}_1$ se obtiene un vector de la forma $\varepsilon \mbox{\bf e}_S\otimes \mbox{\bf e}_1$ donde $\varepsilon\in\{-1,1\}$ es un signo y $S$ es una señal que indica si acaso $f$ es o no equilibrada. En otras palabras, la respuesta $S$ coincide con $f(0)\oplus f(1)$, donde $\oplus$ es la disyunción excluyente, XOR. La auscultación del valor $S$ se realiza siguiendo el postulado de medición, y su valor está apareciendo leyendo sólo el primer qubit. Al efectuar la medición se elige al vector básico $\mbox{\bf e}_S\otimes \mbox{\bf e}_1$ con probabilidad $\varepsilon^2=1$.

Posterior: Algoritmo para el cálculo Arriba: Nociones básicas de Computación Anterior: Evaluación de funciones booleanas