Computaciones clásicas en computadoras cuánticas

Ahora dirigiremos nuestra atención a la implementación de algoritmos clásicos en computadoras cuánticas. Veremos que cualquier computación que pueda realizarse con un circuito booleano clásico también puede realizarse mediante un circuito cuántico con un costo computacional asintótico similar. Además, esto puede hacerse de manera "limpia" — como se describirá en breve —, lo cual es un requisito importante para usar estas computaciones como subrutinas dentro de computaciones cuánticas más grandes.

Simulando circuitos booleanos con circuitos cuánticos

Los circuitos booleanos están compuestos de compuertas AND, OR, NOT y FANOUT. Para simular circuitos booleanos con circuitos cuánticos, comenzaremos mostrando cómo cada una de estas cuatro compuertas puede ser simulada por compuertas cuánticas. Una vez hecho eso, convertir un circuito booleano dado a un circuito cuántico es simplemente cuestión de simular una compuerta a la vez. Solo necesitaremos compuertas NOT, compuertas NOT controladas y compuertas Toffoli para lograrlo, que son todas operaciones deterministas además de ser unitarias.

Compuertas Toffoli

Las compuertas Toffoli también pueden describirse como compuertas NOT doblemente controladas, cuya acción sobre los estados de la base estándar se muestra en la siguiente figura.

Teniendo en cuenta que usamos la convención de ordenamiento de Qiskit, donde los qubits están ordenados en orden creciente de significancia de arriba hacia abajo, la representación matricial de esta compuerta es la siguiente.

$$\begin{pmatrix} 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 & 0 & 0 & 0 & 1 \\ 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 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Otra forma de pensar en las compuertas Toffoli es que son esencialmente compuertas de consulta para la función AND, en el sentido de que siguen el patrón que vimos en la lección anterior para las implementaciones de compuertas de consulta unitarias de funciones arbitrarias con entradas y salidas de cadenas binarias.

Las compuertas Toffoli no están incluidas en el conjunto de compuertas predeterminado que se discutió antes en la lección, pero es posible construir una compuerta Toffoli a partir de compuertas $H,$ $T,$ $T^{\dagger}$ y CNOT de la siguiente manera.

Simulando compuertas booleanas con compuertas Toffoli, NOT controladas y NOT

Una sola compuerta Toffoli, usada junto con algunas compuertas NOT, puede implementar una compuerta AND y una compuerta OR, y las compuertas FANOUT pueden implementarse fácilmente usando compuertas NOT controladas, como sugieren los siguientes diagramas.

En los tres casos, los qubits sobre los que actúan las compuertas AND, OR y FANOUT ingresan por la izquierda como entradas, y también necesitamos un qubit de espacio de trabajo inicializado al estado cero para cada uno. Estos qubits de espacio de trabajo aparecen dentro de las cajas que representan las implementaciones de las compuertas para indicar que son nuevos y, por lo tanto, forman parte del costo de estas implementaciones.

Para las compuertas AND y OR también tenemos dos qubits sobrantes, además del qubit de salida. Por ejemplo, dentro de la caja en el diagrama que representa la simulación de una compuerta AND, los dos qubits superiores quedan en los estados $\vert a\rangle$ y $\vert b\rangle.$ Estos qubits se ilustran como si permanecieran dentro de las cajas porque ya no son necesarios y no forman parte de la salida. Por ahora pueden ignorarse, aunque volveremos a ellos en breve.

La compuerta booleana restante, la compuerta NOT, está incluida en nuestro conjunto predeterminado de compuertas cuánticas, por lo que no necesitamos una simulación para esta.

Simulación compuerta por compuerta de circuitos booleanos

Ahora supón que tenemos un circuito booleano ordinario llamado $C,$ compuesto de compuertas AND, OR, NOT y FANOUT, y con $n$ bits de entrada y $m$ bits de salida. Sea $t = \operatorname{size}(C)$ el número de compuertas en $C,$ y nombremos $f$ a la función que $C$ computa, que tiene la forma

$$f:\Sigma^n\rightarrow\Sigma^m$$

para $\Sigma = \{0,1\}.$

Ahora considera lo que sucede cuando recorremos una por una las compuertas AND, OR y FANOUT de $C,$ reemplazando cada una por la simulación correspondiente descrita anteriormente, incluida la adición de los qubits de espacio de trabajo requeridos. Nombremos $R$ al circuito resultante, y ordenemos los qubits de $R$ de modo que los $n$ bits de entrada de $C$ correspondan a los $n$ qubits superiores de $R$ y los qubits de espacio de trabajo queden en la parte inferior.

Aquí, $k$ es el número de qubits de espacio de trabajo requeridos — uno por cada compuerta AND, OR y FANOUT de $C$ — y $g$ es una función de la forma $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ que describe los estados de los qubits sobrantes creados por las simulaciones de compuertas después de ejecutar $R$. En la figura, los qubits correspondientes a la salida $f(x)$ están en la parte superior y los qubits sobrantes restantes que almacenan $g(x)$ están en la parte inferior. Podemos forzar que esto ocurra si lo deseamos reordenando los qubits con compuertas SWAP, que pueden implementarse con tres compuertas NOT controladas así:

Como veremos en la siguiente sección, en realidad no es esencial reordenar los qubits de salida de esta manera, pero es sencillo hacerlo si así lo elegimos.

La función $g$ que describe los estados clásicos de los qubits sobrantes está determinada por el circuito $C,$ pero en realidad no necesitamos preocuparnos demasiado por ella; no nos importa específicamente en qué estado se encuentran estos qubits cuando termina la computación. La letra $g$ viene después de $f,$ así que es un nombre razonable para esta función por esa razón, pero hay una razón mejor para elegir el nombre $g$ — es una abreviatura de basura.

Limpiando la basura

Si nuestro único interés es evaluar la función $f$ calculada por un circuito booleano $C$ dado con un circuito cuántico, no necesitamos ir más allá de la simulación compuerta por compuerta que acabamos de describir. Esto significa que, además de la salida de la función, tendremos un montón de basura sobrante.

Sin embargo, esto no es suficiente si queremos realizar computaciones clásicas como subrutinas dentro de computaciones cuánticas más grandes, porque esos qubits de basura causarán problemas. El fenómeno de la interferencia es de vital importancia para los algoritmos cuánticos, y los qubits de basura pueden arruinar los patrones de interferencia necesarios para que los algoritmos cuánticos funcionen.

Afortunadamente, no es difícil limpiar la basura, por así decirlo. La clave está en aprovechar el hecho de que, como $R$ es un circuito cuántico, podemos ejecutarlo en reversa, simplemente reemplazando cada compuerta por su inversa y aplicándolas en el orden inverso, obteniendo así un circuito cuántico para la operación $R^{\dagger}.$ Las compuertas Toffoli, las compuertas CNOT y las compuertas NOT son en realidad sus propias inversas, por lo que ejecutar $R$ en reversa es simplemente cuestión de aplicar las compuertas en orden inverso — pero en general cualquier circuito cuántico puede invertirse como se acaba de describir.

Específicamente, lo que podemos hacer es agregar $m$ qubits más (recordando que la función $f$ tiene $m$ bits de salida), usar compuertas CNOT para copiar la salida de $R$ en estos qubits, y revertir $R$ para limpiar la basura. La siguiente figura ilustra el circuito resultante y describe su acción sobre los estados de la base estándar.

Si ponemos una caja alrededor de todo el circuito y lo llamamos $Q,$ se ve así:

Dado que $C$ tiene $t$ compuertas, el circuito $Q$ tendrá $O(t)$ compuertas.

Si ignoramos los $k$ qubits de espacio de trabajo adicionales, lo que tenemos es un circuito $Q$ que funciona exactamente como una compuerta de consulta para la función $f.$ Si simplemente queremos calcular la función $f$ sobre alguna cadena $x,$ podemos establecer $y = 0^m$ y el valor resultante $f(x)$ aparecerá en los $m$ qubits inferiores — o podemos introducir un estado diferente en los $m$ qubits inferiores si lo deseamos (quizás para aprovechar un retroceso de fase, como en el algoritmo de Deutsch o el de Deutsch-Jozsa).

Esto significa que para cualquier algoritmo de consulta, si tenemos un circuito booleano que calcula la función de entrada, podemos reemplazar cada compuerta de consulta por una implementación en circuito de la misma, y el algoritmo de consulta funcionará correctamente.

Observa que los qubits de espacio de trabajo son necesarios para que este proceso funcione, pero regresan a sus estados iniciales una vez que se ejecuta el circuito combinado. Esto permite que estos qubits se vuelvan a utilizar como qubits de espacio de trabajo para otros propósitos. También existen estrategias conocidas para reducir el número de qubits de espacio de trabajo requeridos (a costa de hacer los circuitos más grandes), pero no las discutiremos aquí.

Implementando funciones invertibles

La construcción recién descrita nos permite simular cualquier circuito booleano con un circuito cuántico de manera libre de basura. Si $C$ es un circuito booleano que implementa una función $f:\Sigma^n \rightarrow \Sigma^m,$ entonces obtenemos un circuito cuántico $Q$ que opera de la siguiente manera sobre los estados de la base estándar.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

El número $k$ indica cuántos qubits de espacio de trabajo se requieren en total. Esto es suficiente para los propósitos de este curso, pero es posible llevar esta metodología un paso más adelante cuando la función $f$ en sí misma es invertible.

Para ser precisos, supongamos que la función $f$ tiene la forma $f:\Sigma^n \rightarrow \Sigma^n,$ y también supongamos que existe una función $f^{-1}$ tal que $f^{-1}(f(x)) = x$ para todo $x\in\Sigma^n$ (que es necesariamente única cuando existe). Esto significa que la operación que transforma $\vert x \rangle$ en $\vert f(x) \rangle$ para todo $x\in\Sigma^n$ es unitaria, por lo que podríamos esperar construir un circuito cuántico que implemente la operación unitaria definida por

$$U \vert x \rangle = \vert f(x) \rangle$$

para todo $x\in\Sigma^n.$

Para ser claros, el hecho de que esta sea una operación unitaria depende de que $f$ sea invertible — no es unitaria cuando $f$ no lo es. Sin tener en cuenta los qubits de espacio de trabajo, $U$ es diferente de la operación que implementa el circuito $Q$ porque no estamos manteniendo una copia de la entrada y aplicándole XOR con una cadena arbitraria, sino que estamos reemplazando $x$ por $f(x).$

La pregunta es: cuando $f$ es invertible, ¿podemos hacer esto?

La respuesta es sí, siempre que se nos permita usar qubits de espacio de trabajo y, además de tener un circuito booleano que calcule $f,$ también tengamos uno que calcule $f^{-1}.$ ¡Así que esto no es un atajo para invertir funciones computacionalmente cuando ya no sabemos cómo hacerlo! El siguiente diagrama ilustra cómo puede hacerse componiendo dos circuitos cuánticos, $Q_f$ y $Q_{f^{-1}},$ que se obtienen individualmente para las funciones $f$ y $f^{-1}$ mediante el método descrito anteriormente, junto con $n$ compuertas de intercambio, tomando $k$ como el máximo del número de qubits de espacio de trabajo requeridos por $Q_f$ y $Q_{f^{-1}}.$