Por qué las computadoras cuánticas todavía no han logrado factorizar 21

• Explicación de por qué parece que no ha habido avances desde que en 2001 una computadora cuántica factorizó 15
• Un circuito para factorizar 21 requiere 100 veces más compuertas de entrelazamiento que uno para factorizar 15
• Esta diferencia se debe a la complejidad de la multiplicación modular condicional y a optimizaciones especiales que solo aplican a 15
• La corrección de errores cuánticos y las limitaciones del hardware también elevan aún más la barrera para factorizar 21
• La mayoría de los casos reportados hasta ahora de factorización de 21 usan trucos sin realizar multiplicaciones reales en el sentido estricto

---

Por qué las computadoras cuánticas todavía no han logrado factorizar 21

Por qué no ha aparecido la factorización de 21 después de factorizar 15

• En 2001 hubo un experimento que factorizó 15 con una computadora cuántica
• Ya estamos en 2025, pero todavía no hay casos exitosos de factorización de 21
• A partir de esto se ha extendido la percepción de que las computadoras cuánticas no han avanzado en absoluto
• Pero en realidad, al comparar los circuitos para factorizar 15 y 21, hay una razón mucho más sorprendente

Diferencias estructurales entre el circuito para factorizar 15 y el circuito para factorizar 21

• El circuito para factorizar 15 se implementa con apenas 21 compuertas cuánticas (21 compuertas de entrelazamiento)
  • Está compuesto por 6 compuertas de entrelazamiento de cúbits (compuertas CNOT y CPHASE) y
  • 2 compuertas Toffoli (cada una descompuesta en 6 compuertas de entrelazamiento), para un total de 21 compuertas de entrelazamiento
• El circuito para factorizar 21 requiere 191 CNOT, 369 Toffoli y un total de 2405 compuertas de entrelazamiento
  • Esto implica una carga de compuertas de entrelazamiento 115 veces mayor que al factorizar 15
  • El tamaño del circuito no crece simplemente 25% o al doble, sino que se vuelve más de 100 veces más costoso
• Incluso considerando el nivel de optimización del circuito, parece realista una diferencia de hasta 500 veces

Por qué surge una diferencia tan grande

• En los circuitos cuánticos de factorización (algoritmo de Shor), el costo dominante es la multiplicación modular condicional
  • Para un número N de n bits, hay que realizar varias multiplicaciones modulares de forma condicional sobre un acumulador
  • En el caso de 15, de las 8 multiplicaciones condicionales, 6 pueden resolverse como multiplicación por 1 (sin hacer nada)
    • La primera multiplicación puede implementarse casi gratis porque la entrada es 1
    • La segunda (la única restante) también puede resolverse de forma barata con dos CSWAP
    • Como resultado, en la práctica solo hay que pagar el costo de 2
    • Esta estructura es una propiedad especial que solo aplica a 15: como hay muchas multiplicaciones cercanas a 1, la carga disminuye de forma notable
• Pero en el caso de 21, las multiplicaciones no son todas por 1 y los valores son variados, así que todas tienen costo
  • Las 8 multiplicaciones tienen costo, lo que eleva el costo no solo 4 o 5 veces, sino entre 20 y 100 veces
  • Multiplicaciones como por 4 o 16 no tienen una estructura que permita implementarlas con CSWAP (intercambio condicional)
  • La complejidad de la multiplicación varía en cada caso y no es fácil de optimizar

Límites prácticos del hardware y de la corrección de errores

• La factorización de 15 en el pasado (2001) se implementó con una computadora cuántica NMR, con muchas limitaciones para escalar
• Además, la necesidad de corrección de errores cuánticos también aumenta
  • Si el número de compuertas aumenta 100 veces, la tasa de error tendría que ser 100 veces menor
  • En la práctica, incluso podría ser necesario aumentar el número de qubits 100 veces, por lo que el costo total podría subir hasta 10,000 veces

Controversias sobre intentos de factorización y resultados erróneos

• En algunos artículos recientes se afirma que se logró factorizar 21 con una computadora cuántica, pero
  • en realidad, muchas veces se omite la multiplicación del algoritmo o se simplifica el circuito conociendo de antemano el resultado
  • Si no se realiza la operación real de multiplicación, eso no puede considerarse factorización
  • Son resultados que ignoran la diferencia esencial entre la simple "búsqueda de período" y la factorización en sí
• Algunos artículos usan trucos de forma descarada, e incluso han aparecido artículos satíricos sobre esos trabajos
  • Existen varios artículos satíricos, incluidos experimentos que reproducen récords de campeones de factorización
  • Siguen apareciendo benchmarks como Variational factoring sin fundamento para justificar escalabilidad

Cuál es un indicador adecuado del progreso real en computación cuántica

• En este momento, la factorización no es el principal benchmark del progreso en computación cuántica
  • Más allá de 15, el costo se dispara y hace difícil una validación práctica
• Más bien, la introducción de corrección de errores cuánticos (por ejemplo, mejoras en el surface code) o
  • cambios en la arquitectura de hardware para resolver problemas de escalado (por ejemplo, reemplazo continuo en átomos neutros)
  • son puntos de observación más importantes para mostrar avances reales

[GN⁺]

Comentarios en Hacker News

• Se debe a que hasta ahora nunca se había factorizado realmente un número más pequeño. Si el proceso de compilación del programa solo funciona porque ya conoce la respuesta, entonces no es una factorización real, sino simplemente "imprimir 3"

• Me pregunto cuántas quantum gates se necesitan realmente para factorizar un número criptográficamente significativo. También quisiera saber si existe una ruta práctica para que aparezca una computadora cuántica útil dentro de este siglo

  • Como ejemplo, se puede citar la estimación de la Tabla 5 de este artículo, que indica que factorizar RSA de 2048 bits requeriría alrededor de 7 mil millones de compuertas Toffoli (enlace al artículo). La forma de lograr decenas de miles de millones de operaciones es precisamente la corrección de errores cuántica, y el artículo señala que un surface code de distancia 25 sería suficiente. En ese caso, se escala de 1,400 qubits lógicos a cerca de 1 millón de qubits físicos ruidosos. También vale la pena revisar la charla de Samuel Jacques en PQCrypto (YouTube). Yo soy el autor de este blog y del artículo relacionado
  • Hay dos razones por las que esta pregunta es difícil. Primero, no se puede trazar claramente la frontera de qué significa "criptográficamente significativo". Segundo, todavía no se conoce con claridad la arquitectura de una QC capaz de realizar realmente esta operación. Es parecido a estimar en 1985 cuántas compuertas lógicas tradicionales harían falta para construir una red neuronal. Aun así, parece claro que se necesitarían más de millones de compuertas. En tercer lugar, en la corrección de errores cuántica existe un trade-off entre menores tasas de error en qubits físicos y la cantidad de gates necesaria para construir qubits virtuales confiables con corrección de errores. Hoy no sabemos hasta qué punto bajará la tasa de error de los qubits físicos. Si las computadoras cuánticas tienen un desarrollo parecido al de la computación en los últimos 75 años, estimo que para 2100 la criptografía actual quedará completamente anulada. Hasta que aparezca una sola innovación del tipo transistor, es difícil hacer predicciones. El avance tecnológico siempre parece imposible, hasta que alguien encuentra la primera forma de hacerlo. (Descripción de UNIVAC I)
  • También sirve de referencia este tuit reciente (enlace al tuit). Desde la perspectiva de una persona común, esa ruta parece estar oculta detrás de varias innovaciones enormes en ciencia de materiales
  • Para RSA 4096, a grandes rasgos harían falta 10^7 qubits con una tasa de error de 10^-4. Ya es posible hacer cálculos útiles de química cuántica con solo unos 100 qubits, y a medida que los algoritmos poscuánticos se expanden, disminuye el incentivo para desarrollar computadoras cuánticas destinadas a romper criptografía. Creo que la computación cuántica avanzará más rápido en direcciones no relacionadas con criptografía
  • La cifra más reciente es que se necesitarían alrededor de 1 millón de qubits con una tasa de error de 1e-4 (enlace al artículo). El número de gates se mide de forma distinta según la operación real a nivel de código, y con un "reloj" de 1 MHz (tiempo de ciclo del código) el tiempo total de cómputo sería de alrededor de una semana. Lograr ese tiempo de cómputo es una métrica más difícil que alcanzar el número de qubits. Gracias al efecto casi mágico de la corrección de errores cuántica —que reduce mucho la cantidad de qubits necesarios cuando baja la tasa de error—, una mejora de un nivel en la calidad de los qubits hace que el requisito de qubits caiga de golpe. En cambio, si hay que repartir las operaciones entre varios sistemas, la situación empeora muchísimo

• El artículo 'Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog' me pareció interesante (leer artículo)

• Me interesa el tamaño del circuito y la viabilidad de implementar la factorización de números criptográficamente significativos como RSA1024

  • La estimación de costo para RSA1024 no se obtuvo extrapolando sin más desde números pequeños (como 4 bits), sino mediante un diseño de circuito acorde a la escala real. Es decir, ya incorpora implícitamente el problema de discontinuidad mencionado en este artículo. Por lo tanto, esta publicación no afecta las estimaciones de costo existentes
  • (Como referencia: la optimización del circuito para factorizar 21 sería difícil de aplicar al factorizar números grandes. Un costo 500 veces mayor que el circuito para factorizar 15 podría ser más realista. Claro, incluso un sobrecosto de 100x basta para ilustrar el argumento. Agradezco especialmente a Noah Shutty por haber realizado una costosa búsqueda computacional para esa optimización de circuito)
  • Esto se sale un poco del tema, pero me pregunto si los criptógrafos realmente están convencidos de que incluso en centros de datos gigantescos sigue siendo prácticamente imposible factorizar RSA1024. Por ahora, ni siquiera el algoritmo más rápido puede factorizarlo en un tiempo realista. Pero me interesa saber si también hay consenso en que no habrá pronto una mejora revolucionaria de ese algoritmo

• Me pregunto si algún día una computadora cuántica podría apuntar a post-quantum RSA (artículo relacionado). También existe la postura de que las operaciones normales de RSA (generación de claves, cifrado, descifrado) son asimétricamente favorables frente al algoritmo de Shor, así que bastaría con usar claves lo bastante grandes. Eso produce un efecto parecido al de los rompecabezas de Merkle, con la condición adicional de que el atacante necesariamente debe usar una computadora cuántica. Alguna vez hice una clave pública RSA de gigabits (archivo de clave). El formato es: 4 bytes little-endian para el número de bytes de la clave, luego la clave, y luego su inverso (mod con 256^bytes). El exponente público es 3

  • Post-Quantum RSA es una broma que hizo djb para responder a la pregunta de "¿no sería seguro si solo usamos claves más grandes?". Está diseñado para que cada cifrado tarde 100 horas con una clave de 1 TB. Ni siquiera una computadora cuántica podría romperlo

• Me dio mucha risa ver el error tipográfico "error corection"

• Me cuesta entender la parte de "costo de circuito 500 veces mayor en comparación con factorizar 15". El autor ya dio un caso de 115x, así que me pregunto cómo una optimización adicional podría terminar dando un resultado peor

  • Significa que la enorme cantidad de trabajo de optimización invertida en construir circuitos para factorizar números pequeños es algo imposible de repetir de forma realista para números grandes. Es decir, intuitivamente, cuando crece el número a factorizar normalmente se necesitaría un aumento de compuertas de alrededor de 500x, no algo tan bajo como 115x
  • En la práctica, a gran escala el efecto de la optimización disminuye, y no habría una ganancia tan grande como en el circuito para N=21
  • Una implementación mínima es inestable y difícil de garantizar en confiabilidad. Para desarrollar circuitos prácticos hace falta mucha investigación para conseguir qubits estables, y también se mencionan conceptos como el "tiempo de decoherencia". Por eso la cantidad de qubits inevitablemente se dispara
  • El 115x es el resultado de aplicar una gran cantidad de optimizaciones (poco realistas)

• Me pregunto si la idea central de esta publicación implica que el requerimiento Big-O de circuitos para la factorización de Schorr es superpolinómico

  • Según el contenido del artículo, el costo en compuertas proviene principalmente de O(n) operaciones de multiplicación modular, y cada una puede implementarse con O(n^2) compuertas. En conjunto, incluso en el peor caso, parece una complejidad aproximadamente cúbica

• La razón para adoptar criptografía PQ (poscuántica) no es necesariamente que exista la certeza de que una QC llegará pronto. Sigue siendo incierto cuándo aparecerá, dependiendo de la velocidad del desarrollo tecnológico. El objetivo de la criptografía es encontrar métodos que, incluso en teoría, sean casi imposibles de romper; y si en teoría un ataque es posible, entonces también lo es físicamente, así que hay que prepararse. En ECC y RSA ya se confirmó una ruta teórica de ataque, por lo que se consideran vulnerables incluso sin que exista todavía el equipo real. Por eso es totalmente razonable prepararse con anticipación, antes de que haya una QC. En cambio, para SHA2, AES, ChaCha y similares no se ve una ruta de ataque práctica, así que no hay un plan inmediato de reemplazo. El cifrado no es la única ni la aplicación más importante de la QC. Se espera que aún aparezcan innovaciones desconocidas en áreas como sistemas físicos, plegamiento de proteínas y aprendizaje automático

  • Me pregunto si todavía hay espacio para más avances en áreas como el plegamiento de proteínas (incluso después de AlphaFold). (artículo de referencia)

  • En el caso de la criptografía de clave simétrica (AES, ChaCha, SHA-2), un ataque cuántico en la práctica equivale a debilitar la longitud de clave a la mitad, como en los casos de 3DES y 2DES. En la práctica no se puede afirmar simplemente que sea la mitad, porque el rendimiento de una computadora cuántica real no sería equivalente ni idéntico, pero cambiar a AES-256 resuelve el problema. Donde sí hay que poner atención es en el Key Exchange. La razón es que Key Exchange se usa para acordar una clave secreta entre ambas partes sin revelarla directamente. Si existiera una computadora cuántica, también se podrían leer conversaciones pasadas que hayan sido grabadas. Aunque romper un algoritmo de firma no te permite volver al pasado y firmar algo retroactivamente, si se rompe Key Exchange entonces también quedan expuestas todas las conversaciones pasadas, por lo que es urgente contar con un reemplazo seguro para Key Exchange