El ordenador cuántico de la institución Alamena Fraunhofer-Geselleschaft
Déjame encarar el desafío de frente. No va ser fácil pero voy a intentarlo, voy a explicarte el algoritmo de Grover, un algoritmo cuántico con aplicaciones prácticas y, en esta entrada, voy a explicarlo sin notación matemática, lo que no significa que no te hable de números y operaciones. En futuras entradas describiré como programarlo.
Voy a plantear un problema “de juguete” para que pilles la idea, y luego lo convertiré en un problema “de verdad” para que veas la ventaja.
Conforme leas el texto te darás cuenta de que tienes muchas preguntas y comentarios que hacer. No te reprimas y usa los comentarios o las redes sociales, pero espera a llegar al final. Tengo que poner especial cuidado en que esto no se convierta en un curso de mecánica cuántica, como los siete borradores que preceden a la versión del artículo que estás leyendo hoy.
Vale, al lío. Vamos a encontrar el número que multiplicado por 2 da X. Para hacerlo todavía más simple, sabemos que la solución existe y es algún número entre 0 y 9. En vez de deshacer la operación y dividir X entre dos, vamos a hacerlo por fuerza bruta: cargamos el 0, lo multiplicamos por dos, ¿es X? –no–, pues ese no es. Siguiente: cargamos 1, lo multiplicamos por dos, ¿es X? –no–, pues ese tampoco es… y así, hasta llegar al que sea X, momento en que paramos y consultamos el número que hemos cargado. La secuencia es: carga, multiplicación, chequeo y decisión acerca de si seguir o parar.
Hasta aquí, nada nuevo bajo el sol, ningún algoritmo cuántico a la vista. Esta es sólo la explicación del problema que vamos a resolver: encontrar un elemento que cumple una propiedad.
Da igual cómo te de por recorrer los números, si empezando por el 0, por el 9, por el 5, o aleatoriamente. La estadística dice que, de media, te llevará un número de repeticiones de la secuencia igual a la mitad de las posibilidades, en este caso, la mitad de diez es cinco. Quédate con eso.
En un ordenador cuántico, cargarías todos los números a la vez, multiplicarías todos los números a la vez y chequearías todos los números a la vez. Puesto que no operamos en secuencia, la parte de “si seguir o parar” no tiene sentido. Reemplaza este paso por anotar “sí” o “no”, según el resultado de la operación sea la solución o no lo sea.
En realidad, con un ordenador normal también podrías operar en paralelo, a costa de invertir más memoria. ¿Dos números a la vez? ¡El doble de memoria! ¿Tres números a la vez? ¡El triple! A partir de cierta cantidad de memoria, el problema es equivalente.
En el ordenador cuántico, sin embargo, el precio en memoria de operar con un número es el que tenga que ser, y con dos números o con tres números es el mismo. Es como si en vez de operar con el número en particular, operaras con un símbolo que representa todas las posibilidades. Podrías pensar que esta memoria “barata” es el origen de la ventaja de los ordenadores cuánticos y, sin duda, es parte de ella pero no lo es todo.
Piensa en una cosa, por un momento: ¡todas las posibilidades están contenidas en el mismo espacio de memoria! Hablar de “recorrer una lista” ni siquiera tiene sentido. Así que, al leer la memoria, el ordenador cuántico selecciona una entrada de la lista, al azar. En el ordenador cuántico, el precio de operar en paralelo no es la memoria pero sí la certeza.
Al tratar de leer la memoria, el ordenador cuántico respondería con un par cualquiera como (0, no) o (9, no) u (8, sí). ¡Ojo! El par es correcto: si es (8, sí) es porque tu solución era el 8. Esto es siempre cierto. El problema es obtener ese par y no otro cualquiera. Quiere decir: que no tienes la certeza de obtener el par correcto.
El algoritmo de Grover soluciona exactamente este problema. El algoritmo de Grover amplifica la probabilidad de dar con el par correcto, de forma que al final del mismo, lo normal sea encontrar la solución y, raramente, algún otro resultado.
En el algoritmo de Grover la secuencia es: carga, multiplicación, chequeo, anotación y amplificación de probabilidad. La anotación no consiste en almacenar “sí” o “no”, sino que la solución correcta "se marca" (mientras que el resto no), de tal forma que permite la amplificación de la probabilidad del resultado correcto.
Las reglas de la mecánica cuántica, que rigen la operación de los ordenadores cuánticos, permiten sustraer probabilidad de las soluciones sin marcar y dársela a la solución marcada, en un proceso llamado interferencia. Recuerda esta palabra.
Excepto la carga, el resto de pasos se repiten. Con cada repetición, la probabilidad de obtener el resultado correcto aumenta. Tras cierto número de repeticiones, la probabilidad vuelve a bajar. Las aritmética dice que el número de pasos requeridos, para que la probabilidad sea máxima, es la raíz cuadrada del número de posibilidades. Quédate con esto también. En este caso, la raíz cuadrada de diez es poco más que tres.
Llegados a este punto, me interesa que recuerdes que la media de repeticiones en la solución por fuerza bruta –la búsqueda en secuencia– es de la mitad de las posibilidades, mientras que obtener la solución en el ordenador cuántico requiere un número de repeticiones igual a la raíz cuadrada del número de posibilidades.
Fíjate en que para cualquier número de posibilidades grande, la raíz cuadrada es mucho, mucho más pequeña que la mitad y esa es la ventaja del algoritmo de Grover.
También me interesa que te des cuenta de que lo que resuelven tanto la búsqueda en secuencia como el algoritmo de Grover es precisamente, una búsqueda, no deshacer una operación. Sirve igual si los pares (numero, anotación) representan las soluciones de la multiplicación por dos, o las soluciones de elevar al cuadrado, o son los pixeles de la foto que estabas buscando.
Problemas “de verdad”
¿Qué hace que un problema sea “de verdad”? Yo diría que es su aplicación práctica pero además, un factor muy importante es la escala del problema.
La escala del problema determina los recursos que se invierten, y la utilidad del problema determina si vale la pena invertir esos recursos.
En nuestro problema "de juguete", teníamos que buscar entre 0 y 9. Un ordenador moderno puede operar con 10 números a la vez, con un consumo mínimo de espacio, solucionando el problema anterior en un solo paso, lo que ya lo hace mejor que su contrapartida cuántica.
Pero si hablamos de millones de elementos, tenemos que plantear estrategias más caras. Y llega un momento en que ya no renta, o los recursos se acaban. Es en los problemas grandes donde hablar de tiempos que crecen con la mitad de los elementos o con la raíz cuadrada tiene importancia.
Por ejemplo, buscar entre un millón de elementos le lleva al ordenador clásico quinientas mil repeticiones. Al cuántico "tan solo" mil. Pero aún más importante, el mismo problema, 1000 veces más grande, le lleva al ordenador clásico 1000 veces más repeticiones. Al cuántico, le lleva sólo 30 veces más.
Ahora bien, ¿existen problemas prácticos con tamaños tan grandes?
Sí. Muchos problemas consistentes en encontrar combinaciones que cumplen cierta propiedad pueden resolverse mucho más eficientemente en ordenadores cuánticos. Los elementos de las combinaciones sólo pueden ser de dos formas, pero el número de elementos puede ser muy grande, de forma que las combinaciones posibles explotan en número.
Sin embargo, deja que te cuente una versión muy difícil, y muy grande, de nuestro problema de juguete. Se trata de reventar una contraseña.
Piensa en la policía tratando de romper la clave del disco duro de un criminal. Estos dispositivos guardan una versión cifrada de la contraseña original. Cuando se introduce la contraseña, esta se hace pasar por una serie de operaciones llamadas, en su conjunto, función hash, que dejan la contraseña irreconocible. La función no se puede deshacer "paso por paso". Es tan complicada que sólo puede deshacerse por fuerza bruta: probando todas las combinaciones.
El problema es inmenso. Una contraseña de 10 caracteres supone encontrar la solución en un espacio de millones de trillones –trillones de los de España– de soluciones posibles.
El ordenador más poderoso hoy día, Fugaku, capaz de ejecutar quinientos miles de billones de operaciones por segundo, invertiría cientos de años de uso continuo en obtener la solución. A un ordenador cuántico –incluso miles de veces más lento en cantidad de operaciones por unidad de tiempo– le llevaría unos pocos segundos.
El algoritmo de Grover no hace uso de la cantidad de instrucciones por segundo que puede ejecutar un ordenador cuántico, sino de poder sustraer probabilidad de unas posibilidades para sumarla a la posibilidad correcta. Hace que las posibles soluciones interfieran unas con otras y se intercambien probabilidad. Esta manipulación de la probabilidad, y las reglas que rigen los fenómenos cuánticos, son los responsables de la ganancia en velocidad.
Desafortunadamente, los ordenadores cuánticos de hoy día no son lo suficientemente poderosos (ni rápidos) como para romper siquiera una contraseña modesta. La tecnología dista mucho de ser la mínima suficiente para ejecutar estas estrategias pero la teoría está ahí, esperando a que la tecnología alcance la madurez adecuada.
La computación cuántica y la dificultad de los problemas
En el ámbito de la aplicabilidad industrial, en 2019, Google reclamaba la supremacia cuántica, el momento en que un problema “de gran escala”, impracticable para un ordenador clásico, pudiera resolverse con un ordenador cuántico. La "ventaja cuántica" de IBM, exige, además, que el problema sea práctico.
Sin embargo, en informática, los problemas cambian de difíciles a fáciles conforme los algoritmos que los resuelven se perfeccionan. A principios del siglo XX, el test de primalidad, que indica si un número es primo o no, se consideraba un problema difícil. Hoy día sabemos que es fácil. En 2002, Manindra Agrawal, Neeraj Kayal, y Nitin Saxena publicaron una forma fácil (más rápida, en realidad) de resolverlo.
Ni la ventaja, ni la supremacia cuántica pueden considerarse hitos históricos únicos. Alguien podría dar con una solución clásica que convirtiera el problema en fácil de resolver, como le pasó al test de primalidad y como demostró Ewin Tang, pionera en encontrar algoritmos clásicos tan rápidos como sus homólogos cuánticos.
Ninguna ventaja sale gratis. Lo que ya sabíamos los del gremio era que, lo que te ahorras en tiempo, te lo gastas en espacio. Lo que, personalmente, no me esperaba, es que la computación cuántica convirtiera la certeza en otro recurso.
Y ¿eso es todo?
Este artículo es el último borrador tras casi dos años de intentos. Versiones anteriores iban más al detalle pero diluían los conceptos que me parecían más importantes para una introducción.
No quería que pensaras en superposición ni entrelazamiento, sospechosos habituales de los monográficos de los telediaríos que, convenientemente, dejan fuera a la interferencia, el patito feo de los fenómenos cuánticos.
¡Al contrario! Mi objetivo ha sido que entiendas que el paralelismo cuántico no hace a los ordenadores cuánticos más rápidos, eso es un tema de instrucciones por segundo, aunque el paralelismo cuántico sí que reduce la cantidad de espacio requerido. El éxito del algoritmo de Grover está intrínsecamente ligado a la interferencia cuántica de las posibilidades –¿recuerdas?–, que te permite restar probabilidad de las posibilidades erróneas para sumársela a la solución correcta y así, recuperar buena parte de la certeza perdida. La certeza es ahora otro recurso variable, como el tiempo y el espacio.
Esta básica introducción a la aplicabilidad de la computación cuántica son más de 2000 palabras. Contar qué está pasando, con más detalle, me llevaría otro tanto… aunque, sí llegaste hasta aquí y te has quedado con ganas de más, me alegra haber captado tu atención. Como decía al comenzar el texto, lo explicaré en algún artículo futuro, al tiempo que enseñaré a programar el problema de juguete.