El récord de factorización de números utilizando computadores cuánticos

Por Francisco R. Villatoro, el 18 febrero, 2009. Categoría(s): Ciencia • Computación cuántica • Física • Informática • Mecánica Cuántica • Noticias • Physics • Science ✎ 2

dibujo20090218beautifuldiagramspacetimeprobability

El récord, el número más grande factorizado por un algoritmo cuántico, se ha logrado mediante una implementación cuántica del algoritmo de las sumas de Gauss utilizando tecnología de resonancia magnética nuclear (NMR). Hasta donde yo tengo constancia, el récord corresponde a la siguiente factorización

N = 32.193.216.510.801.043 = 179.424.673 x 179.424.691

dibujo20090218factorizationrecordopticalgausssums

Fue obtenido por Xinhua Peng y Dieter Sute, «NMR implementation of Factoring Large Numbers with Gauss Sums: Suppression of Ghost Factors,» ArXiv preprint 24 March 2008 . El récord no es ninguna maravilla pero es un claro indicativo de que la computación cuántica avanza, a pequeños pasos, pero sin pausa.

Peter Shor desmostró que los algoritmos cuánticos son más eficientes que los algoritmos clásicos en ciertos problemas, como la factorización de números. Su algoritmo, basado en usar la transformada de Fourier implementada mediante un algoritmo cuántico, así lo demostró. Este algoritmo fue utilizado en 2001, por IBM, para factorizar 15 = 3×5, utilizando una implementación basada en resonancia magnética nuclear (NMR) de un ordenador cuántico de 7 cubits. Parece poco, pero fue un gran logro en su momento. De hecho, incluso algunos dudan de que fuera una implementación cuántica «correcta» por lo que dicho logro ha sido repetido en 2007 por otros autores «supuestamente» haciéndolo del todo bien (unos, otros). Que yo tenga constancia, nadie ha factorizado un número mayor de 15 mediante al algoritmo cuántico de Shor.

Sin embargo, hay otros algoritmos de factorización de números utilizando ordenadores cuánticos. Que no resuenen las campanas, la mayoría de estos otros algoritmos cuánticos no son más eficientes que un algoritmo clásico equivalente. Pero son algoritmos cuánticos más fáciles de implementar con las incipientes tecnologías cuánticas actuales. Una implementación cuántica del algoritmo de las sumas de Gauss utilizando tecnología NMR (como la usada por IBM). Michael Mehring et al., «NMR Experiment Factors Numbers with Gauss Sums,» Phys. Rev. Lett. 98: Art. No. 120502, 2007 , logró factorizar, tatachín, tatachán, el número

N = 157573 = 13 x 17 x 23 x 31

No es mucho, pero tampoco es poco. La técnica parece «escalable» aunque «sufre», en su estado actual, mucha decoherencia cuántica. Los autores han tratado de factorizar un número un «poco» más grande

N = 1062885837863046188098307 = 790645490053 x «ruido cuántico»

pero sólo con un éxito parcial: La decoherencia sólo les ha permitido observar experimentalmente uno de sus factores (el indicado arriba), el resto de los factores aparecen «ocultos por el ruido cuántico».

Un poquito más tarde, los mismos autores avanzaron un poquito más aún: M. Stefanak et al., «NMR implementation of exponential sums for integer factorization,» WSPC Proceedings, September 6, 2007 , lograron factorizar

N = 6920989 = 17 x 443 x 919

Sin embargo, les salió competencia. Usando la misma técnica (con ligeros avances) T. S. Mahesh et al., «Factorizing numbers with the Gauss sum technique: NMR implementations,» Phys. Rev. A 75: Art. No. 062303, 2007 , lograron factorizar un número un poquito más grande (la figura muestra el resultado experimental «limpiado»)

N = 52 882 363 = 67 x 79 x 97 x 103

dibujo20090218quantumfactorizationbygausssums

 

Estos avances pueden parecer poco. El algoritmo cuántico de factorización de números basado en resonancia magnética nuclear (NMR) que se ha utilizado no es más eficiente que un algoritmo clásico equivalente (no tiene nada que ver con el famoso algoritmo de Peter Shor) por lo que alguien podría decir que el récord sigue siendo N=15. En mi opinión, este avance es importante porque nos muestra los progresos que se están realizando actualmente en la computación cuántica «escalable». La NMR está considerada la técnica más prometedora para el desarrollo de un futuro ordenador cuántico «útil». Y, en mi opinión, no está defraudando.

dibujo20090218factorization33withpeakshighlight

Para números más grandes el problema más importante de esta técnica es que a veces no es fácil distinguir en los picos de la NMR factores próximos, es decir, el pico cubre más de un entero (por ejemplo, p y p+1) y aunque es fácil decir cuál de los dos es el factor correcto no podemos afirmar rotundamente que el algoritmo haya determinado dicho factor unívocamente. Nos lo recuerda Jonathan A. Jones, «NMR implementations of Gauss sums,» Physics Letters A 372: 5758-5759, 1 September 2008 . La tesis doctoral de Wolfgang Merkel, «Factorization of numbers with physical systems,» 2007 , será una buena fuente de más información sobre la técnica NMR y las sumas de Gauss.



2 Comentarios

  1. Que tal, emulenews?
    Desde que recibo tus Post en mi e-mail, disfruto como un enano leyéndolos. Me encantan.
    Lo que me pregunto en este momento es que aporta a la ciencia ser capaces de factorizar números enormes.
    Por lo pronto nos cargaríamos el protocolo de encriptación RSA, lo cual es más bien perjudicial.
    No veo ventajas.
    ¿Que aplicaciones tendría para la ciencia, ser capaces de factorizar un número de 1000 dígitos, por ejemplo?.
    Saludos…!

    1. Perjudicial????????

      no digas que seria perjudicia. Los avances cientificos son como una herramienta que pude ser usada de diferentes formas, entre ellas algunas perversas

      Mas bien, ¿no se te ocurre que podrian hacer un algoritmo para encriptar mas avanzado gracias a la computacion cuantica?

      y la computacion cuantica no solo serviria para factorizar numeros grandes, sino que segun lei, se podrian simular experimentos de fenomenos que tienen que ver la fisica cuantica, cosa que no es posible con las computadoras actuales.

      Saludos!.

Deja un comentario