12 Paralelismo cuántico

Sección en construcción.

En la sección anterior hemos introducido la estructura principal de un circuito cuántico. Estos circuitos se pueden usar para realizar tareas de computación clásicas, pero también para desarrollar un nuevo paradigma de computación que permitirá el desarrollo de nuevos algoritmos puramente cuánticos. La idea clave detrás de la computación cuántica es aplicar una serie de operaciones y algoritmos, no a un estado definido, sino a una superposición de estados. De esta forma un ordenador cuántico no procesa las entradas de un forma secuencial, sino que tiene la capacidad de procesarlas simultáneamente en forma de superposición, lo que se conoce como paralelismo cuántico.

El potencial de esta idea es evidente si, por ejemplo, pensamos en calcular las salidas de una función booleana para todas sus posibles entradas de $n$ bits. Un ordenador clásico necesitaría evaluar la función $2^n$ veces (una para cada posible entrada), mientras un ordenador cuántico podría procesar la superposición de las $2^n$ posibles entradas en una única llamada a la función. Aunque la idea es relativamente sencilla, veremos que conseguir algoritmos útiles con esta técnica es muy complicado y, hoy en día, todavía no existen muchas aplicaciones de esta tecnología.

12.1 Funciones booleanas

En primer lugar vamos a estudiar cómo diseñar un circuito cuántico que represente una función booleana. Una función booleana es una función $f$ que toma como entrada una secuencia binaria de longitud $n$ y ofrece como salida otra secuencia binaria, posiblemente de una longitud diferente $m$: $$\begin{align*} f: \{0,1\}^n \to \{0,1\}^m \end{align*}$$

Por ejemplo, consideremos la función de dos entradas $a_1$ y $a_2 \in\{0,1\}$ cuya salida se corresponde con la operación AND:

$$\begin{align*} a_1 \wedge a_2 = \begin{cases} 1,& \text{ si }a_1=a_2=1,\qquad\\ 0,& \text{ en otro caso.} \end{cases} \end{align*}$$

Un circuito cuántico que realice esta operación necesitaría implementar una transformación unitaria $$\begin{align*} \ket{a_1 a_2} \rightarrow \ket{x_1 x_2} = U \ket{a_1 a_2} \end{align*}$$ tal que $x_1 = a_1 \wedge a_2$ y donde $x_2$ es una salida auxiliar que puede tomar cualquier valor. Aquí, es necesario añadir la salida auxiliar $x_2$ para que la dimensión del sistema a la salida coincida con la dimensión a su entrada. Al ser $U$ una transformación unitaria, debe ser una matriz cuadrada y la dimensión de la salida debe coincidir con la dimensión de la entrada.

Sin embargo, no existe ninguna transformación unitaria $U$ tal que $x_1 = a_1 \wedge a_2$. Intuitivamente, la imposibilidad de implementar la puerta AND de esta forma se debe a que las matrices unitarias son invertibles, por lo que en una puerta cuántica no se puede perder información. Por tanto cualquier operación realizada debe ser reversible. Dado que la función AND no es reversible, no existe ninguna transformación unitaria $U$ tal que $\ket{x_1 x_2} = U \ket{a_1 a_2}$ con $x_1 = a_1 \wedge a_2$.

Implementación cuántica de funciones booleanas

El ejemplo anterior muestra que, para una función $$\begin{align*} f: \{0,1\}^n \to \{0,1\}^m \end{align*}$$ la transformación $\ket{\boldsymbol{a}} \rightarrow \ket{f(\boldsymbol{a})}$ posiblemente no sea reversible y, por tanto, no se pueda implementar con un circuito cuántico, incluso añadiendo las salidas auxiliares necesarias para que encajen las dimensiones de la entrada y la salida.

Para evitar este problema, vamos a considerar el siguiente circuito cuántico:

En este bloque, además de los cúbits de entrada $\ket{\boldsymbol{a}}$, se consideran una serie de cúbits auxiliares $\ket{\boldsymbol{b}}$, con su dimensión correspondiente a la de la salida de la función $f(\boldsymbol{a})$. A la salida del bloque, por una parte se replica la entrada $\ket{\boldsymbol{a}}$ en sus líneas superiores, y se calcula un XOR (OR exclusivo) de la función de interés con la entrada auxiliar $\ket{\boldsymbol{b} \oplus f(\boldsymbol{a})}$.

Si en este circuito fijamos la entrada auxiliar a $\ket{\boldsymbol{b}}=\ket{0}$, obtenemos

A diferencia de la formulación vista anteriormente, esta operación siempre es reversible y se puede implementar como una transformación unitaria (y, por tanto, también como un circuito cuántico). Para ver que esta operación es reversible basta con darse cuenta de que a la salida disponemos de una copia de la entrada $\boldsymbol{a}$. Por tanto, para cualquier función booleana $f$, siempre podemos calcular $f(\boldsymbol{a})$ y deshacer el XOR de las líneas auxiliares y así obtener la parte $\boldsymbol{b}$ de la entrada.

Ejercicio 12.1 Vamos a implementar una puerta AND como un circuito cuántico que realiza la siguiente transformación: $$\begin{align*} \ket{a_1,a_2}\otimes\ket{0} \rightarrow \ket{a_1,a_2}\otimes\ket{a_1 \wedge a_2} \end{align*}$$

Para ello consideramos la puerta de Toffoli (de $3$ cúbits), que se define como:

$$\begin{align*} \text{TOFF} = \left[\begin{smallmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{smallmatrix}\right] \end{align*}$$

Esta puerta cuántica recuerda en gran medida a la puerta CNOT ya que se trata de una puerta controlada por los dos primeros cúbits de su entrada.

1. ¿Puede indicar a partir de la matriz TOFF cual es el estado de los dos primeros cúbits que activa la función NOT en el último?

2. Obtenga la salida de esta puerta para las entradas $\ket{000}$, $\ket{010}$, $\ket{100}$, y $\ket{110}$.

3. ¿Se ajusta este resultado a las salidas esperadas para una puerta AND, $\ket{a_1,a_2,a_1 \wedge a_2}$?

12.2 Paralelismo cuántico

Denominamos paralelismo cuántico a la capacidad de un circuito cuántico de evaluar una función booleana $f(\boldsymbol{a})$ para todos los valores de $\boldsymbol{a}$ de forma simultánea en forma de superposición. Esta es una de las claves que permitirá un incremento exponencial de la potencia de cálculo con el número de cúbits que puede manejar un ordenador cuántico.

En el punto anterior hemos visto que una función booleana $f$ se puede implementar con una transformación unitaria $U_f$. Así, con la estructura vista en la sección anterior, para una entrada $\ket{\boldsymbol{a}} \otimes\ket{0}$ a la salida obtenemos $\ket{\boldsymbol{a}}\otimes\ket{f(\boldsymbol{a})}$. Sin embargo, hasta ahora nos hemos restringido a entradas del tipo $\ket{\boldsymbol{a}}$ donde $\boldsymbol{a}\in \{0,1\}^n$. Sin embargo $U_f$ es un operador cuántico y por tanto nada nos impide aplicar un estado cuántico arbitrario $\ket{\psi}$ a su entrada:

Para determinar la salida $\ket{\varphi}$, descomponemos $\ket{\psi}$ como una superposición de elementos de la base computacional $$\begin{align*} \ket{\psi} = \alpha_1 \ket{0\cdots 00} + \alpha_2 \ket{0\cdots 01} + \cdots + \alpha_{2^n} \ket{1\cdots 11}, \end{align*}$$ y utilizamos que, como hemos visto en la sección anterior, $$\begin{align*} \ket{\boldsymbol{a}} = \ket{0\cdots 00} \quad&\Rightarrow\quad \ket{f(\boldsymbol{a})} = \ket{f(0\cdots 00)},\\ \ket{\boldsymbol{a}} = \ket{0\cdots 01} \quad&\Rightarrow\quad \ket{f(\boldsymbol{a})} = \ket{f(0\cdots 01)},\\ &\vdots\\ \ket{\boldsymbol{a}} = \ket{1\cdots 11} \quad&\Rightarrow\quad \ket{f(\boldsymbol{a})} = \ket{f(1\cdots 11)}. \end{align*}$$ Por la propiedad de linealidad de los operadores unitarios obtenemos $$\begin{align*} \ket{\varphi} = \alpha_1 \ket{f(0\cdots 00)} + \alpha_2 \ket{f(0\cdots 01)} + \cdots + \alpha_{2^n} \ket{f(1\cdots 11)}. \end{align*}$$ Es decir, si a la entrada de un circuito cuántico aplicamos una superposición de estados, a su salida obtendremos la superposición de las correspondientes salidas a esos estados. Este proceso se puede ver en detalle en el siguiente ejemplo.

Ejemplo 12.1 Consideremos el siguiente circuito cuántico:

1. El estado inicial en este circuito se corresponde con $\ket{000} = \ket{0} \otimes \ket{0} \otimes \ket{0}$.

2. Después de aplicarle los operadores $\text{H}$ a los dos primeros cúbits tenemos el estado intermedio $$\begin{align*} \bigl(\text{H} \otimes \text{H} \otimes \text{I}\bigr)\bigl(\ket{0} \otimes \ket{0} \otimes \ket{0}\bigr) &= \text{H}\ket{0} \otimes \text{H}\ket{0} \otimes \ket{0}\\ &= \tfrac{1}{\sqrt{2}}\bigl(\ket{0}+\ket{1}\bigr) \otimes \tfrac{1}{\sqrt{2}}\bigl(\ket{0}+\ket{1}\bigr) \otimes \ket{0}\\ &= \tfrac{1}{2}\bigl(\ket{000}+\ket{010}+\ket{100}+\ket{110}\bigr), \end{align*}$$ donde en el segundo paso hemos utilizado que $H\ket{0} = \tfrac{1}{\sqrt{2}}\bigl(\ket{0}+\ket{1}\bigr)$ y en el último paso hemos utilizado la propiedad distributiva del producto tensorial con la suma, $(a+b) \otimes c = (a\otimes c) + (b\otimes c)$.

3. Este estado se emplea como entrada de una puerta de Toffoli (que recordemos se corresponde con la función booleana AND de los 2 primeros cúbits). Así, a la salida del circuito obtenemos $$\begin{align*} \ket{\boldsymbol{y}} &= \tfrac{1}{2}\bigl(\ket{0,0, 0\wedge 0}+\ket{0,1, 0\wedge 1}+\ket{1,0, 1\wedge 0}+\ket{1,1, 1\wedge 1}\bigr)\\ &= \tfrac{1}{2}\bigl(\ket{000}+\ket{010}+\ket{100}+\ket{111}\bigr). \end{align*}$$ Vemos que el último cúbit se corresponde con la operación AND aplicada sobre los dos primeros.

Es importante tener en cuenta que en un circuito cuántico, la salida no se presenta como una serie de salidas definidas, sino que se manifiesta como una superposición de las mismas. Esta superposición no es directamente accesible ya que se corresponde con un estado cuántico y solo se puede observar a través de un proceso de medida.

La clave para aprovechar el paralelismo cuántico pasa entonces por transformar esta superposición en un observable que se pueda medir y que además resuelva la tarea de computación deseada. Existen varios algoritmos que pueden aprovechar el paralelismo cuántico de una manera no trivial, logrando el resultado deseado mediante una medición determinista o con una alta probabilidad. Así, el paralelismo cuántico puede ser una herramienta muy útil para la computación, pero solo se puede aprovechar mediante procesos de medida cuidadosamente diseñados.