Factorizan el número 15 usando el algoritmo de Kitaev con 5 átomos atrapados

Por Francisco R. Villatoro, el 7 marzo, 2016. Categoría(s): Ciencia • Computación cuántica • Física • Informática • Noticias • Physics • Science ✎ 4

Dibujo20160307 Circuit diagram of Kitaev version Shor algorithm for factoring 15 sciencemag org

Para factorizar el número 15 = 5 × 3 el algoritmo de Shor (1994) requiere 12 cubits, pero bastan 5 cubits con el algoritmo de Kitaev (1995). Se publica en Science una implementación del algoritmo de Kitaev usando 5 átomos atrapados. Los autores afirman que es un algoritmo escalable y muchos medios se hacen eco de esta noticia como si la seguridad informática estuviera en peligro. Lo siento, falsa alarma. Tus tarjetas de crédito siguen siendo seguras. Y lo seguirán siendo por mucho tiempo.

En 1997 se implementó el algoritmo de Shor con 12 cubits para factorizar el número 15. Un logro histórico. Desde entonces se ha repetido este logro muchas veces. La mayoría de las veces se usa información a priori (que ya sabemos los factores del número) para cablear el algoritmo de forma eficiente. El algoritmo de Kitaev no usa esta información a priori (los llamados trucos de precompilación), por ello los autores afirman que es escalable. Sin embargo, factorizar un número como 91 = 7 × 13 puede exigir varios lustros de investigación. No es concebible que el algoritmo de Kitaev permita poner en peligro los algoritmos de cifrado durante el siglo XXI.

El artículo es Thomas Monz et al., «Realization of a scalable Shor algorithm,» Science 351: 1068-1070 (04 Mar 2016), doi: 10.1126/science.aad9480arXiv:1507.08852 [quant-ph]; el algoritmo usado se publicó en A. Yu. Kitaev, «Quantum measurements and the Abelian Stabilizer Problem,» arXiv:quant-ph/9511026 (20 Nov 1995).

Más información divulgativa en Scott Aaronson, «Quantum. Crypto. Things happen. I blog,» Shtetl-Optimized, 06 Mar 2016; Jennifer Chu, «The beginning of the end for encryption schemes?» MIT News, 03 Mar 2016; Amy Nordrum, «Quantum Computer Comes Closer to Cracking RSA Encryption,» IEEE Spectrum, 03 Mar 2016.

Dibujo20160307 Experimentally obtained truth table of the controlled 2 modular 15 multiplier sciencemag org

Por supuesto, la implementación del algoritmo de Kitaev usando átomos atrapados es un gran avance en el campo de los ordenadores cuánticos. Aunque solo se hayan atrapado 5 átomos, en las próximas décadas se podrán atrapar muchos más (quizás cientos de átomos). Además, hay técnicas de teletransporte cuántico que permite entrelazar los estados de los átomos de diferentes trampas, con lo que en las próximas décadas se podrán usar cientos de cubits. Sin embargo, el nuevo artículo no usa ninguna técnica de corrección de errores, lo que penaliza el tamaño del número a factorizar conforme crece el número de cubits. Aunque el título del artículo afirme que la nueva implementación es escalable, hoy por hoy es tecnológicamente imposible lograrlo.

Factorizar un número de 256 bits con este tecnología está más allá de lo que podemos concebir en las próximas décadas. Hoy en día quien quiere estar seguro en internet usa claves de 4096 bits. Estas claves seguirán siendo seguras ante el algoritmo de Kitaev implementado con la tecnología de átomos atrapados, al menos, durante todo el siglo XXI. Aunque leas notas de prensa que afirmen que el algoritmo RSA tiene sus días contados, recuerda mis palabras, te están engañando. ¡No te dejes engañar! Disfruta de los avances de la computación cuántica, pero siempre con los pies puestos en la tierra.

 



4 Comentarios

  1. Telares. Por ahora, magníficos telares.
    Creo que si el RSA tiene los días contados es por cuestiones matemáticas no cuánticas.
    Mola Naukas!, gracias Francis.

    1. DavidG, lo cierto es que la criptografía cuántica va varias décadas (mínimo tres) por delante del criptoanálisis cuántico, luego cuando este último pueda ser útil, si llega a serlo algún día, ya nadie usará cifrado clásico.

Deja un comentario