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

Por Francisco R. Villatoro, el 10 julio, 2013. Categoría(s): Ciencia • Computación cuántica • Física • Informática • Noticias • Physics • Science ✎ 13

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.

Dibujo20130710 qubits required shor algorithm and experimental results

Te recuerdo. El algoritmo cuántico de Shor para factorizar el número N=pq calcula sus dos factores p y q utilizando O(log N) cubits (el algoritmo original usa 3 log N cubits, pero hay versiones posteriores con sólo 2+(3/2) log N cubits, aunque la adición de algoritmos de corrección de errores requiere muchos más) y un tiempo de cálculo de O((log N)3), donde log N es el número de dígitos de N. El mejor algoritmo clásico requiere un coste exponencial en el número de dígitos. En 2001 (Nature) se factorizó el número 15 utilizando 7 cubits en lugar de 8; en 2009 (Science) se utilizaron 5 cubits, en 2007 (PRL,PRL) fueron 4 cubits y en 2012 (Nat.Phys.) sólo 3 cubits. El récord se obtuvo en 2012 (Nat.Phot. cuyo primer autor es el español Enrique Martín-López) con la factorización del número 21 utilizando 1+log 3 cubits en lugar de 10 cubits (en realidad son dos cubits, pero uno se usa siempre y el otro sólo en ciertos pasos del algoritmo, de ahí el valor log 3). El truco que se utiliza para reducir el número de cubits es «precompilar» el algoritmo en el «cableado» de la implementación (ya que se conocen los factores), lo que permite reducir el número de cubits hasta solamente 1 cubit.

Dibujo20130710 rsa-768 factoring

Por supuesto, el nuevo récord no se puede considerar una demostración «de verdad» del algoritmo de Shor. Sin embargo, como en anteriores ilustraciones tampoco se utilizaron el número mínimo de cubits necesario, este nuevo récord (obtenido en una implementación semiclásica) se pone en el mismo lugar que las anteriores demostraciones. Y además pone en su lugar dichas demostraciones. La versión «precompilada» del algoritmo de Shor no es una demostración del algoritmo de Shor stricto sensu. Según los autores, el algoritmo de Shor aún no ha sido implementado en un ordenador cuántico. Obviamente, los expertos se pondrán a ello y pronto se publicará la primera demostración del algoritmo de Shor, pero esta vez de verdad.

Lo dicho, a mí me viene ni que pintado este artículo de Nature para mi charla de pasado mañana viernes.



13 Comentarios

  1. Esto es un chiste, no? Factorizan un numero conociendo sus factores? haha, Por favor, que haya salido en Nature no refleja mas que la lamentable politica de publicacion de esta revista, que equivale al Hola! para cientificos. Estuve en QIP13 en Pekin donde Smolin presento su ultraalgotirmo de Shor… en la “Rump Session”… por si no queda claro, la Rump Session es la sesion que se dedica a chistes, chorradas y cosas que no son cientificas. Personalmente, considero que la contribucion de Smolin fue genial y tenia como objetivo terminar de una vez por todas con la fiebre de implementar el algoritmo de Shor con “ever less qubits”, pues es como jugar al ajedrez contra uno mismo. El approach de su charla era mas chistoso que otra cosa. Que lo hayan colado en Nature solo añade a la ironia…

    1. Gracias por la información, Alex, no lo sabía y me ha gustado que ese toque de ironía de Smolin et al. en Nature se transforme en un toque gracioso en vivo y en directo.

  2. visto en perspectiva, quizas el articulo original no es tan ironico como quizas hubiera esperado, a tenor de la charla que dio (que era para troncharse de risa). El articulo en Nature parece ser serio, y simplemente dice, alto y claro, que «el rey esta desnudo»

  3. Hola Francis, me gustaría puntualizar algunas cosas:

    En primer lugar, como seguidor diario de tu blog, permíteme indicarte algunas imprecisiones en tu entrada. Si hablamos del mayor número factorizado, este no sería el que citas (E. Lucero et al. Nat. Phys.) ya que factorizan N=15 como los 4 papers anteriores, sino http://www.nature.com/nphoton/journal/v6/n11/full/nphoton.2012.259.html o en su versión arXiv http://arxiv.org/abs/1111.4147. En este paper, del cual soy el primer autor, factorizamos N = 21 utilizando un qubit en el registro de control usando «la técnica de reciclado» y un qutrit en el registro de trabajo. También hay un fallo sobre el paper de Science 2009 en el que se utilizan 4 qubits, no 5. Y para factorizar N=15 en general se necesitan 12 qubits, no 8.

    Los autores de este artículo ponen de manifiesto la aparente incongruencia de factorizar conociendo el orden (que es un número que permite extraer los factores a posteriori). Esto es cierto, pero no es noticia ya que es bien conocido, y bien especificado en los artículos por todos los autores, sin embargo es necesario hacer uso de este atajo de la precompilación para motivar y descubrir las dificultades que aparecen a medida que se incrementan tanto el número de qubits necesarios como el número de puertas cuánticas.

    Para implementar el algoritmo de Shor de forma completa se necesitaría un ordenador cuántico universal, lo cual está aún a años de distancia. Además del número de qubits exigido por el algoritmo se necesitarían muchos más para poder implementarlo con corrección de errores, etc. En cuanto a demostraciones experimentales, la precompilación es necesaria para poder explorar implementaciones del algoritmo mayores según avanzan los recursos técnicos disponibles. Este tipo de experimentos motiva tanto la investigación teórica para la optimización del algoritmo en función de las arquitecturas disponibles como la investigación experimental para conseguir mayor control sobre sistemas cuánticos.

    Finalmente tampoco creo que este artículo pueda ponerse en la línea de demostraciones anteriores. Cuando lo leí en arXiv hace algún tiempo, no realizan experimento alguno, salvo lanzar una moneda, pero esas monedas no interfieren de forma cuántica ni demuestran entrelazamiento, cosa que sí hace nuestro trabajo, en el que además, por primera vez, demuestra que sin la presencia de estos elementos no se obtiene el resultado correcto.

    1. Gracias por tu comentario, Enrique. Tienes razón en cuanto a que el algoritmo de Shor original requiere 3 log N cubits de ahí que sean 12 para N=15; he omitido esos detalles y estå muy bien que los aclares. Y por supuesto, mi entrada tiene un cierto toque de ironía (la implementación semiclásica es equivalente a las propias simulaciones clásicas que realizó Shor en su artículo original y factorizó un número más grande, del orden de 256). Por supuesto, una implementación de verdad es otra cosa muy diferente.

  4. Roberto, parece que no, pero se ha avanzado mucho en los últimos 15 años hacia el cubit ideal. Dentro de 35 años estoy seguro de que habrá ordenadores cuánticos con cientos de cubits (y para ellos un ordenador clásico no determinista no puede competir en ningún caso).

  5. Question. Los ordenadores cuánticos mejoran la complejidad algorítmica de problemas tradicionales? O(n^2) …. O(logn)? Esto esta probado? Me gustaría entender esto, en ciertos aspectos soy un amater. Gracias.

Deja un comentario