Tomado de Francisco R. Villatoro

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(n2 log n) puertas lógicas cuánticas (operaciones individuales), finalizando con O(1) medidas cuánticas (ejecuciones repetidas) y un prost procesado clásico en tiempo polinómico.

Oded Regev publicó el año pasado en arXiv un nuevo algoritmo de factorización que requiere O(n3/2) puertas lógicas cuánticas, aunque con O(n3/2) cúbits, O(n1/2) medidas cuánticas y un nuevo post procesado 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(n3/2 log n) puertas lógicas cuánticas, O(n log n) cúbits, O(n1/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(n1/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 deco herencia 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 (220), 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 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;

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 ar = 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 ar 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 multi dimensional 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 b1, …, bd y se define ai = bi2; en sendos retículos en d dimensiones ? = {z | ∏ aizi = 1 mod N} y ?0 = {z | ∏ bizi ∈ {−1,1} mod N} se buscan multiperiodos z = (z1, …, zd) usando la QFT.

Finalmente, se aplica un postprocesado clásico en tiempo polinómico, a partir de un z∗ ∈ ?−?0 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 post procesado clásico final, la determinación en tiempo polinómico de un z∗ ∈ ?−?0, 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 post procesamiento 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 si

NO SE DEBE SER DÉBIL, SI SE QUIERE SER LIBRE