Posterior: Evaluación de funciones booleanas Arriba: Nociones básicas de Computación Anterior: qubits y palabras de

Compuertas cuánticas

Para $n=1$, consideraremos las siguientes compuertas básicas, llamadas también operadores cuánticos:

Identidad.

$I=\left[\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right]$. $I:\mathbb{H}_1\to\mathbb{H}_1$ es el operador identidad.

Negación.

$N=\left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right]$. Se tiene $N: \left[\begin{array}{c} z_0 \\ z_1 \end{array}\right] \mapsto \left[\begin{array}{c} z_1 \\ z_0 \end{array}\right]$. $N$ es unitaria y tiene como función permutar señales, es de hecho ``una reflexión a lo largo de la diagonal principal''.

Hadamard.

$H=\frac{1}{\sqrt{2}}\left[\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\right]$. Se tiene $H: \left[\begin{array}{c} z_0 \\ z_1 \end{array}\right] \mapsto \frac{1}{\sqrt{2}}\left[\begin{array}{c} z_0+z_1 \\ z_0-z_1 \end{array}\right]$. $H$ es unitaria y tiene como función ``reflejar el plano respecto al eje $x$ y rotar luego un ángulo de $\frac{\pi}{4}$ radianes, en sentido opuesto a las manecillas del reloj''.

Naturalmente, $N^{\otimes n}$ y $H^{\otimes n}$ son sendas compuertas en $\mathbb{H}_n$. Las matrices que las representan, respecto a la base producto $B_{\mathbb{H}_n}$, pueden ser calculadas mediante la relación (1).

Observamos aquí, primeramente, que $N^{\otimes n}$ actúa como el ``complemento a $2^n-1$'', es decir, en los vectores básicos se tiene

$$N^{\otimes n}\left(\mbox{\bf e}_{\varepsilon_{n-1}\cdots\var... ...right) = \mbox{\bf e}_{\delta_{n-1}\cdots\delta_{1}\delta_{0}}$$ (3)

donde $\left(\varepsilon_{n-1}\cdots\varepsilon_{1}\varepsilon_{0}\right)_2 + \left(\delta_{n-1}\cdots\delta_{1}\delta_{0}\right)_2 = 2^n-1$.

Observamos también que

$$\begin{eqnarray*} H^{\otimes 1}(\mbox{\bf e}_0) &=& \frac{1}{\sqrt{2}}(\mbox{\bf... ...00}+\mbox{\bf e}_{01}+\mbox{\bf e}_{10}+\mbox{\bf e}_{11}) %%\\ \end{eqnarray*}$$

y de manera general

$$H^{\otimes n}(\mbox{\bf e}_{0\cdots 0}) = \frac{1}{(\sqrt{2}... ...mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}} \right)$$ (4)

es decir, el operador $H^{\otimes n}$ aplicado al primer vector básico $\mbox{\bf e}_{0\cdots 0}$ produce el estado que ````promedia'' a todos los demás con pesos uniformes''.

Negación controlada.

Sea $C:\mathbb{H}_2\to \mathbb{H}_2$ la transformación lineal que sobre los vectores básicos actúa $\mbox{\bf e}_x\otimes\mbox{\bf e}_y\mapsto\mbox{\bf e}_x\otimes\mbox{\bf e}_{x\oplus y}$ (recuerdo una vez más que $\oplus$ es la disyunción excluyente, o más bien la adición módulo 2). Esta transformación se llama negación controlada debido a que en su salida, el segundo qubit es la negación del primero sólo si en la entrada el segundo qubit ``estaba prendido''. Esto puede verse como que el segundo qubit de entrada sirve de ``control'' para aplicar el operador de negación al primero, el cual hace las veces de ``argumento''.

$C$ no es el producto tensorial de dos transformaciones unitarias en $\mathbb{H}_1$. Se tiene que $C$ queda representado, respecto a la base canónica de $\mathbb{H}_2$ por la matriz

$$C=\left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 %%\\ \end{array}\right]$$

Negación controlada cambiada.

Sea $D:\mathbb{H}_2\to \mathbb{H}_2$ la transformación lineal tal que $(\mbox{\bf x},\mbox{\bf y})\mapsto D(\mbox{\bf x},\mbox{\bf y})= C(\mbox{\bf y},\mbox{\bf x})$ que tan sólo cambia los roles de variable de control y variable de argumento. Se tiene

$$D=\left[\begin{array}{cccc} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 %%\\ \end{array}\right]$$

En el espacio de transformaciones unitarias, $C$ y $D$ generan un subgrupo con la operación de composición. La tabla de multiplicación del subgrupo es de la forma:

$$\begin{array}{r\vert rrrrrr} \circ & I & C & D & CD & DC & CD... ...& CD & C \\ CDC & CDC & CD & DC & C & D & I %%\\ \end{array}$$

Alternativamente, podemos decir que este grupo queda presentado por su unidad $I$, dos generadores $C,D$ y la relación $CDC=DCD$. De hecho este grupo es isomorfo al grupo de permutaciones de 3 elementos, $S_3$. En efecto, si $\rho=(1,2)$ es la reflexión y $\phi=(1,2,3)$ es el ciclo de orden 3, entonces se puede identificar $C\leftrightarrow \rho$, $D\leftrightarrow \rho\circ\phi$.

Reversos.

Entre los elementos que aparecen en el ejemplo anterior, $R_2=CDC:\mathbb{H}_2 \to \mathbb{H}_2$ queda representado, respecto a la base canónica, mediante la matriz

$$R_2=\left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 %%\\ \end{array}\right],$$

es decir, es tal que $R_2(\mbox{\bf e}_i\otimes\mbox{\bf e}_j) = \mbox{\bf e}_j\otimes\mbox{\bf e}_i$. De hecho, para cada $n\geq 2$, actuando sobre la base canónica, se tiene:

$$R_n=R_2^{\otimes n}\left(\mbox{\bf e}_{\varepsilon_{n-1}\cdo... ...\bf e}_{\varepsilon_{0}\varepsilon_{1}\cdots\varepsilon_{n-1}}$$ (5)

es decir, el efecto de este operador es revertir el orden de la ``palabra de entrada'', por lo cual, $R_n$ se dice ser el operador reverso.

Un estado en $\mathbb{H}_n$, digamos $\mbox{\boldmath$\sigma$}(\mbox{\bf z})=\sum_{\mbox{\scriptsize\boldmath$\vareps... ...boldmath$\varepsilon$}} \mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}}$ está determinado por las $2^n$ coordenadas del vector $\mbox{\bf z}\in E_{2^n}$. Si $U:\mathbb{H}_n\to\mathbb{H}_n$ es una compuerta cuántica, el estado $\mbox{\boldmath$\sigma$}(U\mbox{\bf z})$ al que arriba al aplicársele el operador $U$ consta también de $2^n$ coordenadas. De esta manera, un cálculo que involucra un número exponencial de términos se hace en ``un paso'' de cómputo cuántico y es posible así acelerar el proceso de corrida.

Toda combinación lineal de elementos en la base cuyos coeficientes formen un punto en la esfera euclidiana unitaria de $\mathbb{C}^{2^n}$ es un estado, $\mbox{\boldmath$\sigma$}(\mbox{\bf z})$. Se dice que el estado es descomponible, o factorizable, si es de la forma $\mbox{\bf z}_1\otimes \cdots \otimes \mbox{\bf z}_n = \mbox{\boldmath$\sigma$}(\mbox{\bf z})$, con $\mbox{\bf z}_i\in\mathbb{H}_1$. Un estado que no es descomponible se dice ser revuelto (entangled state).

Posterior: Evaluación de funciones booleanas Arriba: Nociones básicas de Computación Anterior: qubits y palabras de