El algoritmo cuántico de Peter Shor permite factorizar un número de n dígitos binarios usando O(n) cúbits conectados por O(n² log n) puertas lógicas cuánticas (operaciones individuales), finalizando con O(1) medidas cuánticas (ejecuciones repetidas) y un prostprocesado clásico en tiempo polinómico. Oded Regev publicó el año pasado en arXiv un nuevo algoritmo de factorización que requiere O(n^3/2) puertas lógicas cuánticas, aunque con O(n^3/2) cúbits, O(n^1/2) medidas cuánticas y un nuevo postprocesado clásico en tiempo polinómico. Vinod Vaikuntanathan y Seyoon Ragavan publicaron unos meses más tarde una mejora de dicho algoritmo para la que bastan O(n^3/2 log n) puertas lógicas cuánticas, O(n log n) cúbits, O(n^1/2) medidas cuánticas y el postprocesado clásico de Regev. Este último algoritmo es más robusto porque reduce la constante de complejidad que multiplica el número O(n^1/2) de medidas, gracias a que tolera mejor los errores en las puertas lógicas. Podría pensarse que estos nuevos algoritmos podrían ser útiles para luchar contra la decoherencia reduciendo el tiempo de cálculo disminuyendo el número de puertas (operaciones). Sin embargo, los nuevos algoritmos solo lo logran para n grande; de hecho, no se han calculado las constantes de complejidad de dichos algoritmos, luego para n pequeño el algoritmo de Shor podría seguir siendo más eficiente. Aún así, factorizar números de interés en la criptografía actual, como RSA-2048 de 2048 bits, está más allá de lo concebible en las próximas décadas, tanto con el algoritmo de Shor, como con los dos nuevos algoritmos.

Estos dos nuevos algoritmos son el primer gran avance en la factorización cuántica de números en los últimos 30 años (ya se han publicado varios artículos que optimizan ambos algoritmos). Hay que recordar que el principal factor que limita la potencia de los ordenadores cuánticos actuales es el volumen cuántico, una medida de la cantidad máxima de puertas lógicas que puede tener el circuito cuántico que representa un algoritmo que se ejecute de forma correcta en el ordenador. El volumen cuántico de un ordenador depende de las tasas de error de sus cúbits y de la de sus puertas lógicas (las operaciones que se pueden ejecutar sobre dichos cúbits). Con la tecnología actual (estamos en la era NISQ, por Noisy Intermediate-Scale Quantum era), el volumen cuántico es muy pequeño; el récord actual (abril 2024) lo ostenta el ordenador H1-1 de 20 cúbits de la empresa Quantinuum, cuyo volumen cuántico alcanza un mega (2²⁰), gracias a usar puertas lógicas binarias con una fidelidad del 99.914(3) % (la primera vez que se alcanzan los tres nueves). No me consta que se haya ejecutado el algoritmo de Shor en dicho ordenador, pero solo logrará factorizar un número muy pequeño.

Quizás conviene resaltar que el número más grande que se ha factorizado con el algoritmo de Shor en un ordenador cuántico ha sido 21 = 7 × 3 en el año 2012. En 2019 se intentó factorizar el número 35 = 7 × 5 con dicho algoritmo en un ordenador cuántico IBM Q System One (20 cúbits), pero fue imposible pues no tenía suficiente volumen cuántico; el premio de consolación fue factorizar el número 35 usando un algoritmo híbrido basado en el de Shor. Usando un algoritmo híbrido, en 2022 se logró factorizar un número de 48 bits usando 10 cúbits (LCMF, 27 dic 2022). ¿Permitirá el algoritmo de Regev factorizar números mayores de 21 en los ordenadores cuánticos de IBM o de Quantinuum? El propio Regev dice que no lo sabe. Yo soyo optimista y creo que sí, por lo que espero que se publique dicho hito a finales de este año. Por desgracia, no espero que se puedan factorizar números mucho más grandes de 35. Un número como RSA-2048 sigue siendo un número «infinito» para los ordenadores NISQ actuales.

Los nuevos algoritmos se han publicado en Oded Regev, «An Efficient Quantum Factoring Algorithm,» arXiv:2308.06572 [quant-ph] (12 Aug 2023), doi: https://doi.org/10.48550/arXiv.2308.06572; Seyoon Ragavan, Vinod Vaikuntanathan, «Space-Efficient and Noise-Robust Quantum Factoring,» arXiv:2310.00899 [quant-ph] (02 Oct 2023), doi: https://doi.org/10.48550/arXiv.2310.00899. Más información divulgativa en Ben Brubaker, «Thirty Years Later, a Speed Boost for Quantum Factoring,» Quanta Magazine, 17 Oct 2023. También cito Craig Gidney, Martin Ekerå, «How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,» Quantum 5: 433 (2021), doi: https://doi.org/10.22331/q-2021-04-15-433, arXiv:1905.09749 [quant-ph] (23 May 2019); Cédric Pilatte, «Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms,» arXiv:2404.16450 [math.NT] (25 Apr 2024), doi: https://doi.org/10.48550/arXiv.2404.16450; Martin Ekerå, Joel Gärtner, «Extending Regev’s factoring algorithm to compute discrete logarithms,» PQCrypto 2024, Lecture Notes in Computer Science 14772: 211-242 (2024), doi: https://doi.org/10.1007/978-3-031-62746-0_10, arXiv:2311.05545 [cs.CR] (09 Nov 2023); ; .

En esencia, el algoritmo de Shor para factorizar el número N parte de un número a < N que sea coprimo con N y busca el periodo r > 0 tal que a^r = 1 mod N usando la transformada discreta de Fourier cuántica (QFT); una vez obtenido el periodo r se usa un postprocesado clásico en tiempo polinómico que permite determinar un factor primo de N. La clave del algoritmo es el cálculo de productos módulo N (para calcular a^r mod N) usando transformaciones unitarias. En cierto sentido el algoritmo de Shor es unidimensional (como intenta ilustrar esta figura de Quanta Magazine). La idea de Regev es usar una versión muldimensional de dicho algoritmo (como intenta ilustrar la figura que abre esta pieza, que te recomiendo volver a ojear). En lugar de tomar un número a se toman d > 0 números b₁, …, b_d y se define a_i = b_i²; en sendos retículos en d dimensiones 𝓛 = {z | ∏ a_i^z_i = 1 mod N} y 𝓛₀ = {z | ∏ b_i^z_i ∈ {−1,1} mod N} se buscan multiperiodos z = (z₁, …, z_d) usando la QFT. Finalmente, se aplica un postprocesado clásico en tiempo polinómico, a partir de un z^∗ ∈ 𝓛−𝓛₀ se obtiene un factor primo de N. Por cierto, Shor también presentó un algoritmo para calcular el logaritmo discreto; Martin Ekerå y Joel Gärtner han extendido en 2024 el algoritmo de Regev para calcular el logaritmo discreto.

Regev no ha logrado demostrar matemáticamente que su algoritmo funciona en tiempo polinómico. El postprocesado clásico final, la determinación en tiempo polinómico de un z^∗ ∈ 𝓛−𝓛₀, no está asegurada por ningún teorema matemático. En su lugar, Regev lo ha propuesto como conjetura; así que su algoritmo funciona módulo dicha hipótesis. Cédric Pilatte en 2024 ha mostrado que dicha hipótesis se puede eliminar, aunque  hay que incrementar con factores polilogarítmicos el número de cúbits y el de puertas lógicas cuánticas.

No pretendo entrar en los detalles de estos algoritmos cuánticos (que si bien no son complicados, requieren conocer el algoritmo de Shor); mi intención se limita a dar a una idea de lo que se ha logrado. Al grano, Vaikuntanathan y Ragavan modifican el método de multiplicación en el retículo usado por Regev, basado en usar potencias de dos, usando una técnica de multiplicación reiterada basada en potencias con números de Fibonacci. Un gran problema del algoritmo de Shor es que falla en presencia de ruido (no corregido), como demostró Jin-Yi Cai en 2023. El nuevo algoritmo de Vaikuntanathan y Ragavan usa una mejora en la toma de medidas cuánticas que permite cierta tolerancia a errores en el cálculo cuántico de la QFT. Pero al final hay que aplicar el mismo postprocesamiento de Regev (con lo que se requiere la misma hipótesis). En cualquier caso la mejora en la tolerancia a errores es pequeña y los algoritmos de corrección de errores son imprescindibles en los dos nuevos algoritmos, como lo son en el algoritmo de Shor. Por ejemplo, Craig Gidney y Martin Ekerå estimaron en 2021 que con el algoritmo Shor la factorización del número RSA-2048 requiere unos 20 millones de cúbits físicos que simulen los cúbits lógicos necesarios.

En resumen, se ha logrado avanzar en un tema que ha estado bastante parado durante tres décadas. El nuevo impulso hará que se active este campo. Todos deseamos que aparezcan nuevas optimizaciones algorítmicas que permitan factorizar números mayores de 21 en ordenadores cuánticos NISQ actuales. Pero que nadie se engañe, factorizar números de interés en criptografía y seguridad informática no se logrará hasta la segunda mitad de este siglo.