He visto mucho más bombo sobre las computadoras cuánticas en X recientemente, así que pensé en hacer una publicación larga sobre ellas. Resumen ejecutivo: No creo que la computación cuántica llegue pronto. Creo que esto se debe a que no se ha avanzado en muchos años en el problema más sencillo para el que se pueden usar las computadoras cuánticas, que es la factorización. El registro de factorización cuántica ha estado alrededor del número 15 (¡sí, 15, 3 x 5!) durante una década, y últimamente no se ha producido ningún progreso obvio. Mi razonamiento está a continuación. Voy a desglosar las cosas para las personas que no saben mucho de matemáticas o informática, pero esto aún podría asustar a las personas con fobias a las matemáticas. La factorización de números grandes es de interés porque varios algoritmos criptográficos importantes dependen del hecho de que lleva mucho tiempo factorizar un número suficientemente grande en sus factores primos utilizando computadoras convencionales. Puedes factorizar un número pequeño (digamos 21) a mano muy rápidamente, solo intenta dividirlo por los números comenzando con 2, luego 3 y así sucesivamente, y rápidamente encontrarás que 21 es 3 x 7. Sin embargo, esto no funciona para números realmente grandes porque el espacio de todos los números que necesitarías probar se vuelve demasiado grande. Si pudieras factorizar números de más de 1200 dígitos decimales de longitud (¡no el número 1200, que tiene cuatro dígitos, números con 1200 dígitos!) podrías romper muchos sistemas criptográficos que le importan a la gente, pero nadie sabe cómo hacerlo lo suficientemente rápido en una computadora normal. (Lo suficientemente rápido significa "antes de que todas las estrellas del cielo se quemen"). Hace algunos años, Peter Shor demostró que se podían (al menos en teoría) factorizar números muy rápidamente usando computadoras cuánticas. La factorización utilizando el algoritmo de Shor es, en mi opinión, el punto de referencia más obvio y difícil de falsificar para la computación cuántica. En 2016, el número 15 (¡no un número de 15 dígitos, el número 15!) se factorizó por primera vez (obviamente en 3 x 5) en una demostración limpia y sin manipulación del algoritmo de Shor. Este es un número pequeño, pero fue un comienzo. (Existe cierta discusión sobre si el número 21 también se ha tenido en cuenta en una demostración no manipulada del algoritmo de Shor o no). Pero, de nuevo, 15 es un número de dos dígitos. Queremos tener en cuenta los números en los miles de dígitos para poder romper los sistemas criptográficos. Sin embargo, desde 2016, no se han tenido en cuenta números mayores en las demostraciones limpias del algoritmo de Shor. (Algunas personas han afirmado que han factorizado números más grandes usando el algoritmo de Shor, pero siempre han usado trucos que requerían que ya conocieran los factores para hacerlo y configurar la computadora cuántica con lo que equivale a un conocimiento previo de la respuesta, que realmente no es el punto. Estoy buscando demostraciones * sin amañar *). Hemos estado esperando mucho tiempo para que alguien demuestre factorizar incluso un número un poco mayor que 15. Habría esperado que hubiera un progreso constante en esto, con alguien factorizando (digamos) un número como 77 (7 x 11), y luego uno como 323 (17 x 19), luego algo de miles, y así sucesivamente. Sin embargo, nadie ha demostrado una máquina que pueda hacer algo mejor que el número 15 (que un niño puede tener en cuenta en su cabeza en 3 y 5 en momentos) y ese récord se ha mantenido durante mucho tiempo. Entonces, al menos en este problema, uno realmente básico que es fácil de explicar, no ha habido un progreso constante en la computación cuántica. Hemos tenido mucha publicidad, mucha gente mostrando computadoras cuánticas que supuestamente ejecutan algoritmos que no son demostraciones tan obviamente limpias, pero no hemos visto nada en mucho tiempo sobre la factorización. Creo que ha habido un progreso real en la computación cuántica cuando comencemos a ver números más grandes en demostraciones limpias y sin manipulación del algoritmo de Shor. Creo que hemos hecho un progreso real cuando podamos hacer números de cuatro dígitos decimales, es decir, números en miles. Incluso una demostración de algo que podría hacer un número de dos dígitos mucho más grande que 15 sería bienvenida. Sin embargo, ninguna máquina que pueda hacer eso está realmente en el horizonte a corto plazo. Ahora, poder descifrar códigos requiere máquinas que puedan manejar números con *miles* de dígitos, pero ni siquiera tenemos números de tres dígitos a la vista todavía (o incluso la mayoría de los números de dos dígitos). Entonces, mi punto de referencia personal es ver incluso un poco de progreso en esto. Llámame cuando tengamos computadoras cuánticas que puedan factorizar (digamos) 323 con éxito, en una demostración limpia y sin manipular del algoritmo de Shor que manejaría cualquier número compuesto de tamaño similar. Hasta entonces, no creo que haya mucho interés, al menos no para mí.

(Por cierto, no quiero dar la impresión de que creo que la computación cuántica es imposible ni nada por el estilo. Solo digo que, desde mi punto de vista, el progreso reciente no ha sido obvio y todavía estamos lejos de resolver problemas sencillos como factorizar números con él).

Por cierto, esto tampoco significa que empresas como Google sean tontas por realizar investigaciones puras sobre computación cuántica. Creo que vale la pena trabajar en ello. Simplemente no tiene ninguna aplicación práctica inminente. También puede ser que la NSA u otras organizaciones similares hayan hecho un progreso más significativo en el problema que el mundo de la investigación abierta, pero obviamente, esa no es información de la que estaría al tanto. Por último, esto no significa que la investigación sobre algoritmos criptográficos poscuánticos sea una mala idea.

En mi publicación original en la parte superior, evité mencionar lo difíciles que son los problemas de escala. Sobre todo, me concentré en el hecho de que ninguna de las escalas ha sucedido realmente. Y para estar seguros, en algún momento, es muy posible que las cosas de corrección de errores comiencen a aparecer. Pero, escalar a factorizar números serios no sucederá al día siguiente.

@defendtheworld De todos modos, de nuevo: comenzaré a creer cuando vea que la tecnología pasa de factorizar 15. Y sí, eso significa que ya se habrá hecho una enorme cantidad de trabajo, pero también dejará una enorme cantidad de trabajo por hacer.