Nuevo récord de factorización de números enteros usando ordenadores cuánticos con un algoritmo híbrido

Por Francisco R. Villatoro, el 27 diciembre, 2022. Categoría(s): Ciencia • Computación cuántica • Informática • Noticias • Science ✎ 10

El algoritmo de Shor para factorizar números enteros puso de moda la computación cuántica como riesgo potencial para la seguridad informática. Sin embargo, para factorizar una clave RSA-2048 se requieren millones de cúbits físicos (más allá de lo alcanzable antes del año 2050). Para superar esta barrera se pueden usar algoritmos de factorización basados en resolver un problema de factorización y entre ellos los algoritmos híbridos que combinan ordenadores cuánticos y clásicos. Se publica en arXiv un nuevo récord, la factorización de un número con 48 bits (261980999226229 = 15538213 × 16860433) usando 10 cúbits superconductores gracias a un nuevo algoritmo híbrido que requiere O(log N / log log N) cúbits para factorizar el número N. Lo más relevante es que se estima que para factorizar una clave RSA-2048 bastarían 372 cúbits físicos y una profundidad cuántica de 1118 (para un grafo de cúbits con conexión de todos con todos); un ordenador cuántico con estas características podría estar al alcance de la tecnología actual en 2030 (al menos esa es la promesa de IBM). Sin lugar a dudas el futuro de la seguridad informática está en el cifrado cuántico y los algoritmos postcuánticos.

Los ordenadores cuánticos actuales se encuentran en la era NISQ (Noisy Intermediate Scale Quantum, ordenadores cuánticos con ruidode escala intermedia). Ya se logró demostrar la ventaja cuántica con Sycamore (53 cúbits) de Google AI Quantum, aunque en la resolución de un problema académico sin interés práctico (LCMF, 23 sep 2019). El siguiente paso será demostrarla con un problema de interés práctico; para ello la única esperanza es la computación híbrida que combina ordenadores cuánticos y ordenadores clásicos. Los algoritmos más prometedores son los algoritmos cuánticos de optimización aproximada (QAOA por Quantum Approximate Optimization Algorithm), que prometen ser útiles en química cuántica, aprendizaje automático y otras áreas de la ingeniería; destaca por su impacto entre el público general la factorización de números enteros. El nuevo récord se basa en una implementación híbrida del algoritmo de Schnorr que con O(m/log m) cúbits permite factorizar un número de m bits (al algoritmo de Shor requiere O(m) cúbits), el llamado algoritmo SQIF (Sublinear-resource Quantum Integer Factorization), que usa un optimizador cuántico QAOA para ayudar a resolver la parte más costosa en tiempo del algoritmo de Schnorr. Este algoritmo requiere dos pasos: primero, encontrar ciertas relaciones entre pares (sr-pairs por smooth relation pairs) mediante la resolución del problema del vector más cercano (CVP por Closest Vector Problem) en el retículo, que es NP-duro (NP-hard), y luego resolver un sistema de ecuaciones lineales, que tiene coste lineal. Para resolver el CVP se usa una modificación del algoritmo de Babai que usa QAOA para mejorar sus soluciones.

Se ha logrado factorizar los números 1961 (11 bits), 48567227 (26 bits) y 261980999226229 (48 bits) usando un ordenador cuántico con 3, 5 y 10 cúbits superconductores. El nuevo récord con 48 bits puede parecer poco, pero hay que compararlo con los récords anteriores: 291311 de 19 bits (LCMF, 01 jul 2017) y 1099551473989 de 41 bits (https://doi.org/jq9m), aunque estos números tienen trampa, pues se aprovecha su estructura especial; para un número general el récord actual es 249919 de 18 bits usando D-Wave 2000Q (LCMF, 11 feb 2019). Quizás a muchos les deje fríos un récord en la factorización cuántica de números enteros usando un algoritmo híbrido, pero con la tecnología NISQ actual es la única posibilidad para lograr nuevos récords. El artículo es Bao Yan, Ziqi Tan, …, Gui-Lu Long, «Factoring integers with sublinear resources on a superconducting quantum processor,» arXiv:2212.12372 [quant-ph] (23 Dec 2022), doi: https://doi.org/10.48550/arXiv.2212.12372.

[PS 06 ene 2023] El gran problema de la implementación híbrida del algoritmo de Schnorr es la escalabilidad del optimizador cuántico QAOA; su convergencia se degrada conforme se incrementa el número de cúbits, con lo que para cientos de cúbits no se espera que dicho algoritmo converja (no hay demostración de que lo haga con tecnología NISQ); por tanto, el nuevo algoritmo será inútil para cientos de cúbits y nunca será capaz de factorizar una clave RSA-2048. Así nos lo cuenta Scott Aaronson (que fue revisor (reviewer) de este artículo para una revista científica, donde lo rechazó (summary rejection) sin paliativos), en «Cargo Cult Quantum Factoring,» Shtetl-Optimized, 04 Jan 2023. Scott lo resume en «Schnorr ≠ Shor» y comenta que tras cientos de artículos sobre la posible ventaja de usar QAOA en el algoritmo de Schnorr la conclusión es que no hay ninguna prueba de que haya una ventaja cuántica conforme el número de cúbits crece. Un duro varapalo al artículo del que me he hecho eco. [/PS]

El algoritmo cuántico usado es relativamente sencillo, pues se basaen aplicar de forma reiterado unos bloques de intercambio (SWAP). No entraré en los detalles, solo quiero destacar que la profundidad cuántica (el número de bloques SWAP) es proporcional al número de cúbitsm, con lo que se necesita un ordenador cuánticos cuyos cúbits tengan alta calidad para factorizar números grandes. Como el algoritmo híbrido requiere solo O(m/log m) cúbits para factorizar un número de m bits, por ahora, es el algoritmo que requiere menos cúbits entre todos los algoritmos de factorización de un número entero arbitrario. En la implementación hardware se han usado cúbits superconductores de tipo transmón con fidelidades del 99.9 % para operaciones unarias de rotación (Rz) y de Hadamard (H) sobre un cúbit y del 99.5 % para operaciones binarias tipo CZ sobre dos cúbits.

En el paisaje energético del problema hamiltoniano que resuelve el algoritmo QAOA, como ilustra esta figura, la convergencia al mínimo global es muy rápida, bastan tres pasos; en la figura, la parte izquierda muestra la aplicación del algoritmo del descenso más rápido mientras que la parte derecha muestra el resultado del algoritmo cuántico. Por supuesto, el camino recorrido por el algoritmo cuántico difiere en cada ejecución, siendo diferente del resultado de la simulación numérica. Sin embargo, el óptimo al que converge es independiente de dicho camino, lo que indica que el algoritmo QAOA usado es robusto al ruido.

El nuevo algoritmo aún está muy lejos de ofrecer una ventaja cuántica (que exige usar más de cincuenta y pico cúbits). Gracias a ello se puede comparar su resultado con la predicción teórica para una simulación de dicho algoritmo. Como muestra esta figura el nivel de ruido del ordenador cuántico usado es bastante elevado, con lo que el resultado experimental está lejos de ser una buena aproximación a la predicción teórica. A pesar de ello es suficiente para lograr la factorización récord de un número de entero de 48 bits.

Para público general, quizás, lo más interesante es esta tabla que estima el número de cúbits y la profundidad (número de puertas lógicas) necesarios para factorizar cinco claves, de RSA-128 hasta RSA-2048. La profundidad depende de la topología del grafo que conecta los cúbits; en la tabla aparecen tres posibilidades, conexión todos con todos (Kn), una retícula 2D (2DSL) y una cadena 1D (LNN). La menor profundidad se obtiene para la conectividad de todos con todos. Para RSA-2048 se requieren 372 cúbits y una profundidad de 1118 para Kn y de 1490 para LNN. Estos números parecen alcanzables con la tecnología actual para el año 2030 (si se cumplen las promesas de las grandes tecnológicas, como IBM, incluso podría ser antes). Sin lugar a dudas la computación híbrida tiene un espléndido futuro.



10 Comentarios

        1. Pedro, la implementación distribuida de un algoritmo, usando múltiples ordenadores conectados en red usando microprocesadores diferentes, no permite estimar el coste computacional en tiempo de ejecución de forma sencilla; en su lugar se usa el tiempo de ejecución equivalente a una unidad de cómputo por unidad de tiempo, en este caso un núcleo (core) de un procesador Intel Xeon Gold 6130 CPU (que tiene 16 núcleos) a 2.1 GHz y como unidad de tiempo se ha usado un año. Obviamente, la estimación es aproximada.

      1. La intuición de Francis era correcta. En un procesador actual de gama media‐alta tarda unos 35 μs:
        $ time for ((i=0; i<100000; i++)); do echo 1961 48567227 261980999226229; done | factor >/dev/null
        real 0m3.469s

        La herramienta «factor» está disponible en cualquier GNU/Linux porque forma parte del paquete «GNU coreutils». La comparación es más justa contra C dedicado y compilado, que contra Matlab genérico e interpretado.

  1. Nos va a comer la siguiente evolución, la cuántica. Nos va a dejar a todos en pañales. Espero verlo, espero que sea la definitiva, y lo será, espérate a ver una IA cuántica, wooow 😀

Deja un comentario