Deutsch-Jozsa: lo que me sorprendió al comprender uno de los primeros algoritmos cuánticos

Hay algoritmos que son importantes porque resuelven un problema útil. Otros lo son porque cambian la forma en que entendemos qué significa resolver un problema. Deutsch-Jozsa pertenece claramente al segundo grupo, consiste en un ejercicio académico pero que que sentó las bases para un desarrollo posterior de la computación cuántica.

Y yo, cuando lo comprendí, puedo decir que me estalló la cabeza, no por su relativa dificultad en comprenderlo, sino por las implicaciones que este simple algoritmo puede tener.

Si es la primera vez que escuchas algo como el algoritmo de Deutsch-Jozsa, te pido un poco de paciencia hasta terminar de leer este artículo.

Si vienes del desarrollo de software clásico (como yo), puede parecer extraño dedicar tiempo a un algoritmo cuyo problema está construido bajo una promesa muy particular y que no tiene una aplicación industrial directa evidente. Sin embargo, precisamente por su sencillez, Deutsch-Jozsa permite observar algunas de las ideas que después aparecen constantemente en algoritmos cuánticos más sofisticados y prácticos: superposición, oráculos, codificación de información en la fase e interferencia.

Pero sobre todo, introduce una pregunta esencial: ¿puede un computador cuántico necesitar muchas menos consultas que uno clásico para descubrir una propiedad de una función?

La respuesta, bajo el modelo concreto del problema, es sí. Pero conviene entender exactamente qué significa ésto.

Adelanto: en este algoritmo no se calcula un resultado a partir de unos datos de entrada, sino que se averigua cierta propiedad de una función.

El problema consiste en averiguar si una función es constante o balanceada

Supongamos una función booleana, que recibe una cadena de $n$ bits y devuelve un único bit:

$$f:\{0,1\}^n \rightarrow \{0,1\}$$

Además, conocemos de antemano una restricción importante: la función es constante o balanceada. Si es constante devuelve siempre el mismo valor. Si es balanceada devuelve $0$ para exactamente la mitad de sus $2^n$ entradas y $1$ para la otra mitad.

Así de simple, pero lo interesante es entender cómo este algoritmo lo resuelve.

Nuestro trabajo no consiste en calcular todos los valores de la función, sino únicamente en determinar a cuál de esas dos categorías pertenece.

Aquí aparece la primera idea interesante para un programador: no nos interesa conocer cada salida, sino una propiedad global de la función.

Si solo podemos consultar $f$ como una caja negra, un algoritmo clásico determinista puede verse obligado, en el peor caso, a realizar $2^{n-1}$ consultas, claro, en función del número de bits en la entrada.

Después de obtener el mismo resultado para $2^{n-1}$ entradas todavía podría ocurrir que la función fuera balanceada y que todas las entradas restantes devolvieran el valor opuesto. Hace falta una consulta más para eliminar esa posibilidad.

Deutsch-Jozsa obtiene la respuesta exacta utilizando una sola consulta al oráculo cuántico.

Ésta es la separación que hace famoso al algoritmo: piénsalo, en una sola consulta, se averigua el resultado, pero, ¿cómo?

El oráculo no es exactamente una caja negra

El término «oráculo» puede resultar algo grandilocuente, pero la idea es bastante sencilla. Podemos pensar en él como una función cuya implementación interna desconocemos y a la que accedemos mediante una interfaz bien definida.

En un circuito cuántico necesitamos, además, que esa operación sea reversible (esto es una necesidad de la computación cuántica basada en puertas que va más allá del objetivo de este artículo, pero que te aseguro que es muy interesante).

El oráculo suele representarse como una transformación $U_f$:

$$U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$$

Tenemos un registro que contiene $x$ y un cúbit auxiliar $y$. El operador aplica un XOR entre ese cúbit auxiliar y el resultado de $f(x)$. Si todo esto te suena a un galimatías, no importa, sigue adelante.

Hasta aquí no parece que hayamos ganado demasiado. La diferencia comienza cuando $x$ no representa una única entrada, sino una superposición de muchas entradas posibles.

Preparamos los $n$ primeros cúbits en $|0\rangle^{\otimes n}$ y el auxiliar en $|1\rangle$. Después aplicamos puertas de Hadamard.

El primer registro pasa a ser

$$\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle$$

y el cúbit auxiliar queda en el estado $| - \rangle$:

$$|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}$$

Ahora podemos consultar $U_f$ sobre esa superposición. Pero cuidado con una interpretación demasiado común: esto no significa que podamos ejecutar la función para todas las entradas y después leer todos esos resultados. Al medir, la superposición no nos entrega una tabla con $2^n$ valores (esto sería como pensar desde el punto de vista de la computación clásica, y esto no tiene nada que ver).

Lo realmente importante ocurre con la fase.

Phase kickback e interferencia: aquí está la clave del cálculo

Al utilizar $|-\rangle$ como cúbit auxiliar aparece el llamado phase kickback. La evaluación del oráculo puede expresarse, sobre el primer registro, como

$$|x\rangle \longrightarrow (-1)^{f(x)}|x\rangle$$

La información de $f(x)$ queda codificada en el signo de las amplitudes. Para $f(x)=0$ no cambia el signo; para $f(x)=1$ aparece un factor $-1$.

Este detalle es la clave del algoritmo, y reconozco que hay que pensarlo detenidamente, y estudiarlo, hasta ver la luz en uno de los algoritmos cuánticos más básicos.

Pero sigamos. Después del oráculo aplicamos de nuevo puertas de Hadamard sobre los $n$ primeros cúbits. Las amplitudes asociadas a las distintas entradas interfieren entre sí. Algunas se refuerzan y otras se cancelan.

La amplitud del estado $|0\cdots0\rangle$ resulta proporcional a

$$\frac{1}{2^n}\sum_x (-1)^{f(x)}$$

Ahora observa qué ocurre.

Si $f$ es constante, todos los términos tienen el mismo signo, de modo que la suma tiene módulo $2^n$. Después de normalizar, mediremos $|0\cdots0\rangle$ con certeza.

Si $f$ es balanceada, hay exactamente tantos términos $+1$ como $-1$. Se cancelan y la amplitud de $|0\cdots0\rangle$ es cero. Por tanto, nunca obtendremos ese resultado al medir.

No estamos leyendo todos los valores de la función. Estamos construyendo una interferencia que hace visible únicamente la propiedad que nos interesa.

Creo que ésta es una forma mucho más útil de comprender el algoritmo que recurrir simplemente a eso de que «el computador cuántico prueba todos los valores a la vez» (algo que no es para nada cierto). Esa frase puede ser intuitiva al principio, pero es insuficiente y termina ocultando el mecanismo real de funcionamiento.

El circuito, paso a paso

El circuito puede resumirse en cuatro etapas:

1. Inicializar $n$ cúbits en $|0\rangle$ y un auxiliar en $|1\rangle$.
2. Aplicar Hadamard a todos ellos.
3. Ejecutar una única vez el oráculo $U_f$.
4. Aplicar de nuevo Hadamard al primer registro y medirlo.

En pseudocódigo:

preparar |0>^n |1>
aplicar H a todos los qubits
ejecutar Uf una vez
aplicar H a los n qubits de entrada
medir

si resultado == 00...0:
    función constante
si no:
    función balanceada

La estructura es sorprendentemente pequeña. No obstante, esa sencillez no debería hacernos perder de vista dónde se encuentra el trabajo: en la preparación de la superposición, en cómo el oráculo codifica $f(x)$ en las fases y en la interferencia posterior.

Algo que me llamó la atención en su día era la enorme complejidad de conceptos inherentes que había en un circuito cuántico aparentemente tan simple como este.

¿Pero dónde está realmente la mejora?

Aquí hay que hilar fino.

Frente a un algoritmo clásico determinista exacto, Deutsch-Jozsa presenta una separación exponencial en complejidad de consultas: el caso clásico necesita $2^{n-1}+1$ consultas en el peor caso, como hemos dicho, mientras que el algoritmo cuántico necesita una.

Sí, solo una. ¿Te das cuenta?

Pero si permitimos error, un algoritmo clásico aleatorizado puede muestrear unas pocas entradas. Si encuentra dos salidas diferentes sabe inmediatamente que la función es balanceada. Cuantas más muestras coincidan, mayor será su confianza en que sea constante. Es decir, el contraste deja de ser tan espectacular cuando comparamos con algoritmos probabilísticos que aceptan una pequeña probabilidad de error.

Esto nos obliga a distinguir algo que en computación cuántica es fundamental: separación teórica, ventaja computacional y utilidad práctica no son sinónimos.

Deutsch-Jozsa demuestra algo importante dentro de un modelo de consultas a un oráculo. No demuestra que cualquier problema clásicamente exponencial pueda convertirse mediante computación cuántica en uno polinómico. Tampoco proporciona por sí mismo una aplicación industrial capaz de justificar un computador cuántico. De hecho, este es el campo de investigación más activo actualmente, el determinar qué problemas de complejidad exponencial se pueden resolver con complejidad polinómica y cómo usando las propiedades de la computación cuántica, nada más y nada menos.

Lo que sí hace es mostrarnos que existe un modelo de computación en el que superposición, fase e interferencia permiten extraer determinada información global con menos consultas de las necesarias para un algoritmo clásico determinista.

Entonces, ¿abre el camino hacia aceleraciones exponenciales?

Sí, pero hay que expresarlo con precisión.

Deutsch-Jozsa fue una de las primeras demostraciones claras de que un algoritmo cuántico podía presentar una separación exponencial de consultas respecto a algoritmos clásicos deterministas para un problema especialmente construido. Históricamente, ese resultado ayudó a mostrar que la computación cuántica no consistía simplemente en ejecutar el cálculo clásico utilizando un hardware diferente.

Posteriormente aparecerían problemas mucho más relevantes para estudiar ventajas cuánticas, entre ellos el problema de Simon y, sobre todo, el algoritmo de Shor para factorización y logaritmos discretos. Ahí comienza a verse con mayor claridad que determinadas estructuras matemáticas pueden ser explotadas mediante algoritmos cuánticos de maneras que no conocemos cómo reproducir eficientemente con los mejores algoritmos clásicos conocidos.

Pero sería incorrecto extraer de Deutsch-Jozsa una regla general del tipo «la computación cuántica convierte problemas exponenciales en polinómicos». No existe tal regla, es tan solo algo así como un ejercicio académico (pero que abrió la puerta a un gran desarrollo posterior de la computación cuántica).

La lección es más interesante: la forma de representar y manipular la información puede cambiar radicalmente la complejidad de determinadas tareas. Léelo de nuevo.

Para quienes venimos de la ingeniería de software, quizá ése sea el concepto que merece quedarse. Un algoritmo cuántico no es un algoritmo clásico ejecutándose simultáneamente por muchos caminos. Diseñarlo significa conseguir que las amplitudes evolucionen para amplificar la información que buscamos y cancelar la que no necesitamos.

Deutsch-Jozsa hace exactamente eso con una elegancia difícil de ignorar.

Es más que un algoritmo histórico

Si estás empezando con algoritmos cuánticos, Deutsch-Jozsa es un excelente siguiente paso después de comprender superposición, puertas Hadamard y medición. Introduce el concepto de oráculo, obliga a prestar atención a la fase y muestra por primera vez cómo la interferencia puede convertirse en una herramienta computacional.

No resolveremos con él un problema empresarial relevante. Tampoco demuestra una ventaja cuántica práctica sobre cualquier estrategia clásica razonable. Pero ésa no es su verdadera utilidad.

Su valor está en enseñarnos una nueva forma de pensar los algoritmos, desde un paradigma diferente de computación, opino que esto es lo realmente importante y no siempre se lo describe así en la literatura más especializada.

La pregunta deja de ser únicamente «¿cómo calculo todos estos resultados?» y pasa a ser «¿cómo puedo hacer que el propio estado cuántico revele la propiedad que necesito?».

De nuevo, piénsalo, pasamos de calcular algo a revelar cierta propiedad.

Ese cambio de perspectiva, más que la respuesta concreta de si una función es constante o balanceada, es lo verdaderamente importante de Deutsch-Jozsa.