Factorizan un número entero de 20.000 bits utilizando el algoritmo cuántico de Shor pero con “truco”

Dibujo20130710 Experimental data from unbiased coins - Shor compiled algorithm

El paradigma de los algoritmos cuánticos es el algoritmo de Shor para factorizar números enteros. Para reducir el número de cubits necesarios se puede utilizar un truco llamado “precompilación” basado en conocer a priori los factores del número. Gracias a esta técnica, usando dos cubits en una implementación semiclásica, se han factorizado el número RSA-768 (de 768 bits) y el llamado N-20000 (de 20.000 bits). Sin el truco de la precompilación del algoritmo de Shor hubieran sido necesarios 1.154 cubits y 30.002 cubits, resp. Dicho truco no es aplicable cuando no se conocen los factores del número por lo que no puede utilizarse en criptoanálisis de claves públicas. Además, dicho truco puede utilizarse incluso en una implementación clásica del algoritmo de Shor utilizando números aleatorios generados tirando monedas (que salga cara H o cruz T); el nuevo récord se ha obtenido usando dicho truco. Pero lo importante a destacar es que, hasta el momento, el algoritmo de Shor nunca ha sido implementado en un ordenador cuántico de forma completa (sin “precompilación”). El artículo técnico es John A. Smolin, Graeme Smith, Alexander Vargo, “Oversimplifying quantum factoring,” Nature 499: 163–165, 11 Jul 2013. Este artículo me viene ni que pintado porque el viernes 12 de julio imparto el curso “Presente y futuro de la computación cuántica” en un curso de verano “Alan M. Turing: Enigmático, visionario y condenado,” coordinado por Ernesto Pimentel, director de la E.T.S.I. Informática de la Universidad de Málaga, que se imparte en Veléz Málaga.

Sigue leyendo

El algoritmo cuántico de Shor implementado en un chip cuántico con tecnologías fotónicas

Dibujo20090904_compiled_peter_shor_factorization_algorithm_using_photonic_quantum_chip

Factorizar el número 15 parece una trivialidad. Factorizar el número 15 con un ordenador cuántico que implemente el algoritmo de Peter Shor no es fácil, pero se ha logrado con un gran número de tecnologías. En la mayoría de los casos, dichas tecnologías no son fácilmente escalables a la factorización por dicho algoritmo de números más grandes. Alberto Politi et al. han logrado hacerlo utilizando un chip (circuito integrado) con tecnologías fotónicas. En esta implementación, la mayor limitación es que el algoritmo de Shor ha de ser “compilado” (según los autores), yo diría que “expandido” (desarrollando todos su bucles de forma explícita), lo que para números con un mayor número de cubits requiere un coste muy alto. Sin embargo, las tecnologías fotónicas utilizadas parece que ofrecen una nueva vía para la escalabilidad de los ordenadores cuánticos. El artículo técnico es Alberto Politi, Jonathan C. F. Matthews, Jeremy L. O’Brien, “Shor’s Quantum Factoring Algorithm on a Photonic Chip,” Science 325: 1221, 4 September 2009.

Para los que sepáis algo de computación cuántica, la figura que abre esta entrada es autoexplicativa. Para los demás, no entraré en más detalles. Sólo quisiera recordar que a mí se me antoja que las tecnologías de computadores cuánticos basados en redes de guías de ondas (chips fotónicos) tienen un futuro muy alagüeño, sobre todo porque permiten realizar computadores cuánticos a temperatura ambiente, y nos ofrecerán sorpresas importantes en los próximos años. Abajo os dejo la foto del chip fotónico utilizado, para los curiosos.

Dibujo20090904_photonic_waveguide_chip

PS (11 nov 2009): El artículo ya está disponible gratis en ArXiv para los que no tengan acceso a Science.