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.
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.
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 Shorstricto 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.
En teoría de números computacional, el algoritmo p + 1 de Williams es un algoritmo de factorización de enteros, uno de la familia de algoritmos de factorización de grupos algebraicos. Fue inventado por Hugh C. Williams en 1982.
Este funciona bien si el número N a ser factorizado contiene uno o más factores primos p tales que
- p + 1
es liso, i.e. p + 1 contiene únicamente factores pequeños. Este usa sucesiones de Lucas para realizar la exponenciación en un cuerpo cuadrático.
Es análogo al algoritmo p − 1 de Pollard.
No hay comentarios:
Publicar un comentario