Las computadoras cuánticas son cada vez mejores en la factorización de grandes números. ¿Cuánto tiempo queda para el temido Día Q?

Es el espectro que acecha a todas las agencias de inteligencia: un ataque exitoso al criptosistema RSA. Gobiernos, bancos y el ejército utilizan este método para cifrar información secreta que nunca debería caer en manos indebidas. El criptosistema RSA no se puede descifrar con computadoras convencionales. Pero el rápido desarrollo de las computadoras cuánticas preocupa a los expertos.

Por lo tanto, empresas y gobiernos de todo el mundo han comenzado a implementar nuevos métodos de cifrado que ni siquiera las computadoras cuánticas pueden descifrar . La gran pregunta es: ¿cuánto tiempo queda para el Día Q, cuando las computadoras cuánticas podrán descifrar el algoritmo RSA?

La seguridad del algoritmo RSA se basa en la enorme dificultad de factorizar un número grande en sus factores primos; es decir, encontrar dos números primos que, al multiplicarse, den el número deseado. Para números pequeños, la solución es fácil de adivinar (por ejemplo, 33 = 3 × 11). Sin embargo, el algoritmo RSA-2048 utiliza números con más de 600 decimales para el cifrado (lo que corresponde a 2048 bits en notación binaria). Incluso las mejores supercomputadoras fallan en esto. El mayor número factorizado con RSA hasta la fecha tiene 250 decimales. El cálculo tardó varios meses. Dado que el tiempo de cálculo aumenta exponencialmente con el tamaño del número, las supercomputadoras no representan una amenaza.

Las computadoras cuánticas actuales están aún más lejos de poder factorizar un número de 2048 bits. El récord lo ostentan investigadores chinos . Combinando un algoritmo clásico con uno cuántico, recientemente factorizaron el número de 25 dígitos 1.034.879.359.475.633.166.138.643 (el resultado es 1.001.721.172.891 × 1.033.101.213.673).

Estos registros suelen ser noticia, especialmente cuando provienen de China. Esto se debe a que suscitan temores de que las computadoras cuánticas puedan acelerar significativamente la descomposición de grandes números. Este temor no es del todo infundado. Sin embargo, no siempre es acertado. Que una computadora cuántica pueda calcular más rápido que una supercomputadora también depende del algoritmo utilizado.

Desde 1994 se sabe que las computadoras cuánticas pueden representar una amenaza potencial para el algoritmo RSA. En aquel entonces, el matemático Peter Shor presentó un algoritmo de factorización que utiliza ciertos efectos cuánticos.

Shor demostró que la computación puede acelerarse enormemente mediante la hábil coreografía de los efectos cuánticos. Mientras que el tiempo de computación con los mejores algoritmos clásicos crece exponencialmente con el tamaño del número, con el algoritmo de Shor solo escala con una pequeña potencia del tamaño del número. En concreto, esto significa que si una computadora cuántica es capaz de factorizar un número decimal de 250 dígitos, factorizar un número con más de 600 decimales no es una tarea inalcanzable para ella.

Cuando Shor publicó su algoritmo, las computadoras cuánticas aún no existían. Y las computadoras cuánticas actuales tampoco representan una amenaza para el algoritmo RSA. El mayor número factorizado hasta la fecha con el algoritmo de Shor en una computadora cuántica es 21=3×7 . Para eso ni siquiera se necesita calculadora.

La razón de este modesto rendimiento radica en que las computadoras cuánticas actuales son propensas a errores. Incluso la más mínima perturbación puede provocar el deterioro de los estados especiales de los bits cuánticos con los que una computadora cuántica calcula. Cuantos más cálculos se realicen, mayor será la probabilidad de obtener un resultado incorrecto. Y descomponer grandes números requiere una gran cantidad de cálculos.

En principio, sabemos qué hacer al respecto. Al combinar suficientes bits cuánticos defectuosos en una sola unidad, se pueden corregir los errores que ocurren durante el cálculo. Empresas como IBM y Google están desarrollando actualmente computadoras cuánticas tolerantes a fallos . Sin embargo, aún pasarán años antes de que se puedan construir computadoras cuánticas lo suficientemente grandes como para resolver problemas complejos.

Un tipo diferente de computadora cuántica podría lograr el objetivo con mayor rapidez. El algoritmo desarrollado por Peter Shor requiere una computadora cuántica digital que procese información en formato binario. Sin embargo, también existen computadoras cuánticas que operan de forma análoga, es decir, con magnitudes físicas en constante cambio.

La empresa canadiense D-Wave ofrece este tipo de ordenadores cuánticos analógicos desde 2011. Si bien no son tan versátiles como sus homólogos digitales, son menos propensos a errores.

«Inicialmente, los ordenadores cuánticos de D-Wave fueron ridiculizados por los académicos», afirma Dennis Willsch, del Centro de Supercomputación de Jülich. Esto ha cambiado desde entonces. «Los ordenadores cuánticos analógicos de D-Wave pueden resolver ciertos problemas de optimización mejor y, a menudo, con mayor eficiencia energética que los ordenadores cuánticos digitales actuales».

La tarea de factorizar un número también puede reformularse como un problema de optimización (definiendo una función de coste minimizada por los números primos deseados). Hace un año, el grupo de Roberto Sebastiani en la Universidad de Trento logró factorizar el número 8.219.999. El resultado es 32.749×251. Este es el número más grande jamás factorizado sin la intervención significativa de una computadora clásica, afirma Sebastiani. Su grupo utilizó una computadora cuántica D-Wave con más de 5.000 bits cuánticos.

¿Podrían las computadoras cuánticas analógicas de D-Wave representar una amenaza para el algoritmo RSA antes de que las computadoras cuánticas digitales con tolerancia a fallos estén disponibles? «Eso depende de cómo se escale el tiempo de computación», afirma Willsch. Hasta ahora, solo el algoritmo de Shor ha demostrado ser más rápido que el mejor algoritmo clásico conocido hasta la fecha.

Junto con otros investigadores, Willsch investigó el tiempo de cálculo de tres métodos de factorización desarrollados específicamente para computadoras cuánticas analógicas. Al igual que el grupo de Sebastiani, utilizó una computadora cuántica de D-Wave con más de 5000 bits cuánticos. En los tres casos, los resultados sugieren un aumento exponencial del tiempo de cálculo. Esto significaría que la factorización de números grandes no puede acelerarse significativamente.

Lo que el grupo de Willsch aún no ha investigado es el comportamiento de escalado de métodos híbridos como los utilizados por los investigadores chinos. Utilizaron un algoritmo clásico para la factorización. La computadora cuántica de D-Wave solo se encargó de una subtarea particularmente intensiva en computación.

"Las técnicas híbridas no tienen nada de malo", afirma Sebastiani. "Son un intento de obtener lo mejor de ambos mundos". Sin embargo, es casi imposible cuantificar las contribuciones respectivas de la computación cuántica y clásica a la solución del problema. Por lo tanto, la pregunta crucial de si el enfoque híbrido ofrece una ventaja exponencial en velocidad no es fácil de responder.

Willsch considera improbable que los métodos híbridos actuales representen una amenaza para el criptosistema RSA. Sin embargo, no descarta la posibilidad de encontrar algoritmos con mayor escalabilidad. «La oportunidad para los métodos híbridos sin duda existe», concluye.

Mientras no existan tales algoritmos, las computadoras cuánticas digitales seguirán siendo la mayor amenaza para el algoritmo RSA. El día Q podría incluso llegar antes de lo previsto. El algoritmo Shor se mejora constantemente, lo que reduce la necesidad de bits cuánticos.

Por ejemplo, el investigador de Google Craig Gidney demostró recientemente que una computadora cuántica tolerante a fallos con menos de un millón de bits cuánticos sería suficiente para factorizar un número de 2048 dígitos binarios. Anteriormente, se suponía que se necesitarían al menos 20 millones de bits cuánticos. Quizás incluso cien mil bits cuánticos serían suficientes utilizando métodos eficientes de corrección de errores, como los introducidos recientemente por IBM .

Estos desarrollos imprevistos dificultan predecir cuánto tiempo queda para la transición a métodos de cifrado cuántico seguros. Gidney recomienda que los criptosistemas vulnerables se abandonen después de 2030 y que no se permitan después de 2035. Si bien no prevé que existan ordenadores cuánticos suficientemente grandes para 2030, prefiere no condicionar la seguridad a la lentitud del desarrollo.