Quantum Computing · Quantum-Safe
Google Quantum AI reduce a la mitad los qubits del algoritmo de factorización de Regev
Un preprint de Van Kirk y Gidney baja el algoritmo de Regev a unos 4n qubits para un número de n bits. Sigue por encima del de Shor y no cambia los plazos.
Lo esencial
- Van Kirk y Gidney, de Google Quantum AI, bajan el algoritmo de factorización de Regev a unos 4n qubits, la mitad que la mejor implementación anterior.
- Lo consiguen reciclando los qubits de control de la estimación de fase, algo que se creía incompatible con este algoritmo.
- Sigue por encima de los n/2 qubits de las mejores variantes de Shor y no cambia las estimaciones para romper RSA-2048.
Katherine Van Kirk y Craig Gidney, de Google Quantum AI, publicaron el 5 de octubre en arXiv un preprint, todavía sin revisión por pares, que reduce el número de qubits que necesita el algoritmo de factorización de Regev. Con el mejor multiplicador disponible, el algoritmo puede factorizar un número de n bits con unos 4n qubits, más términos de orden menor. Según los autores, es la mitad del espacio que exigía la mejor implementación anterior.
Qué es el algoritmo de Regev y cuál era su problema
Oded Regev presentó en 2023 una variante del algoritmo de Shor que lleva la búsqueda del periodo de una dimensión a varias. Hace menos multiplicaciones cuánticas en cada ejecución, pero necesita más ejecuciones. Los autores advierten de un malentendido frecuente: eso no significa que use menos puertas en total que Shor, porque la ventaja por ejecución se compensa con el mayor número de ejecuciones.
Su principal desventaja práctica era el número de qubits. La versión original de Regev usaba del orden de n1,5; Ragavan y Vaikuntanathan lo bajaron en 2024 a 11,32n. Las mejores variantes de Shor necesitan unos n/2.
Qué han hecho
El ahorro viene del reciclaje de qubits: en la estimación de fase, los qubits de control se usan, se miden y se reutilizan, en lugar de guardarlos todos a la vez. Hasta ahora se creía que el algoritmo de Regev no lo permitía, porque las implementaciones anteriores recorrían esos qubits varias veces. Los autores lo resuelven con dos técnicas: un enmascaramiento en superposición que evita que entre información no deseada en los acumuladores, y una estimación de fase con potencias de Fibonacci en lugar de potencias de dos, que ahorra conversiones entre representaciones. Así, cada qubit de control se usa una sola vez.
| Algoritmo e implementación | Qubits (orden principal) |
|---|---|
| Shor, Chevignard y otros (2025) | n/2 |
| Regev, versión original | 3n1,5 |
| Regev, Ragavan y Vaikuntanathan (2024) | 11,32n |
| Regev, Ragavan (2024) | 10,43n |
| Regev, este trabajo, con el multiplicador «dialog» | 6,33n |
| Regev, este trabajo, con el multiplicador de Luo y otros | 4n |
La parte cuántica no se ha ejecutado en ningún procesador. Lo que sí han simulado es el procedimiento de estimación de fase, con 1.000 ensayos para cada uno de 21 tamaños, de 4 a 4.096 bits. Necesita unas seis mediciones por nivel de Fibonacci, y el 99,676 % de los ensayos dio una estimación precisa y certificada.
Aviso · qué no dice este trabajo
No hace que Regev supere a Shor: los propios autores reconocen que se queda por encima de los n/2 qubits de las mejores variantes de Shor. Las cifras son qubits del circuito; el trabajo no estima qubits físicos ni tiempo de ejecución. Y, como el algoritmo de Regev, depende de una conjetura de teoría de números que no está demostrada.
Qué cambia para quien tiene que decidir
Por sí solo, nada en los calendarios de migración. La estimación de referencia para RSA-2048 sigue siendo la que el propio Gidney publicó en mayo de 2025 con el algoritmo de Shor: menos de un millón de qubits físicos ruidosos.
Lo relevante es la tendencia. Los autores escriben que no ven ningún obstáculo de fondo para seguir reduciendo el coste del algoritmo de Regev, y que el de Shor lleva décadas de optimización mientras que el de Regev tiene solo unos años. Para quien planifica, es un argumento más para no contar con que los recursos necesarios para romper RSA vayan a quedarse donde están.