fernando_acero (fernando_acero) wrote,
fernando_acero
fernando_acero

Implicaciones criptográficas del ordenador cuántico D-Wave One



Hace unos meses se publicó en los medios que la empresa norteamericana Lockheed Martin, ampliamente conocida por su división de Defensa, había adquirido, por la nada despreciable cantidad de 10 millones de dólares, el primer ordenador cuántico comercial, el D-Wave One. Al poco tiempo, comencé a recibir correos en  los que se me preguntaba por las implicaciones para la criptografía de  dicho ordenador y de su compra por la empresa Lockheed Martin.

La verdad es que es algo que no es sencillo de contestar, puesto que hay relativa poca información sobre dicha máquina y la empresa D-Wave, casi por sistema, no publica información sobre las prestaciones del mismo, por lo que solamente podemos especular y con limitaciones. Por si fuera poco, en Internet hay opiniones de todo tipo y para todos los gustos, sobre las capacidades de la máquina de D-Wave, lo que tampoco facilita las cosas a la hora de hablar de ella. Ya se sabe, la polémica en Internet sobre un determinado asunto, es inversamente proporcional a la calidad de la información que existe sobre ese mismo asunto en Internet.Recordemos que en el año 2007 D-Wave reconoció que sus sistemas no eran ordenadores cuánticos de propósito general, algo que ya habíamos adelantado algunos. A pesar de ello, y sin ánimo de polemizar demasiado, voy a intentar dar mi punto de vista sobre este controvertido ordenador.

No es la primera vez que escribo algo sobre la empresa D-Wave, sobre sus progresos en la computación cuántica, o sobre sus productos, por lo que supondré que el D-Wave One es una evolución lógica de las investigaciones y los desarrollos realizados por esta empresa Canadiense fundada en 1.999.

El procesador del D-Wave One se denomina "Ranier" y es un procesador cuántico superconductor adiabático, que funciona en ambiente criogénico y que tiene 128 qbits. El D-Wave One tiene que funcionar asociado a un ordenador tradicional y usa los paquetes libres Python 2.7 y Natural Languaje Toolkit 2.0, para ser programado, mejor dicho, para caracterizar sus Qbits y sus acopladores inductivos, de forma que pueda resolver de forma eficiente problemas de optimización industrial, lo que ocurre cuando llega al estado de mínima energía y máxima entropía, es decir, es un ordenador cuántico adiabático.

Aunque parece algo de ciencia ficción y es un hardware ciertamente complejo, el ordenador está diseñado para que pueda utilizar por sus usuarios con la misma facilidad que un ordenador tradicional y para que la compleja parte cuántica, sea transparente para ellos. Esto se logra mediante un conjunto de sencillos protocolos, llamados API's, o interfaces de programación de aplicaciones, que facilitan la programación y el uso del D-Wave One como si fuera un ordenador convencional.

Como hemos dicho, el D-Wave One es un ordenador cuántico de los denominados adiabáticos, que poco tiene que ver con los ordenadores cuánticos del tipo "general-gate" y está especialmente diseñado para ejecutar un algoritmo de optimización de soluciones,.de nominado "algoritmo de optimización binaria cuadrática sin restricciones" o "qubo", con un máximo de 128 variables. En teoría, este algoritmo es lo suficientemente flexible, como para hacer otras cosas, puede que hasta la factorización de números enteros, pero dadas las limitaciones del hardware, el tamaño máximo del entero a factorizar seria de 128 solamente bits, aunque también es cierto, que falta una programación, o una caracterízación específica del ordenador, para que pueda factorizar números enteros a partir del algoritmo qubo.

Aunque parezca que Ranier tiene poca potencia para factorizar números enteros, lo cierto es que para otras cosas es bastante potente, por ejemplo, puede optimizar y en muy poco tiempo, sistemas complejos con 2^128 estados diferentes, lo que implica que D-Wave One debe ser capaz de enlazar 128 qbits, algo que creo que no ha quedado demostrado hasta el momento, aunque me consta hay gente trabajando en ello y en la caracterización cuántica del chip.

De-Wave One se denomina ordenador cuántico adiabático ya que recurre al "quantum annealing", o "templado cuántico", para resolver esos complejos problemas de optimización y este algoritmo, denominado qubo, está incrustado en el hardware de la máquina como si fuera su firmware. Los datos se traducen en valores qubit y en la configuración de los acopladores que los conectan unos con otros. Después de eso, los 128 qubits, que como hemos dicho, deben estar entrelazados, pasan por una serie de procesos cuánticos que proporcionan una solución al problema.

Dicho esto, parece que el hardware del D-Wave One está limitado a un problema muy concreto, aunque el fabricante sostiene que este algoritmo lo suficientemente flexible como para hacer otras cosas y puede resolver sin dificultad otros problemas costosos de calcular con métodos y hardware tradicionales. Es como si el ordenador filtrase los estados posibles en base al fenómeno por el que todos los sistemas físicos intentan llegar a un nivel de energía lo más bajo y con la mayor cantidad de entropía posible. Cuando el sistema de D-Wave llega a esa situación de baja energía y alta entropía, lo que proporciona realmente,o al menos eso dice la empresa fabricante, es una solución optimizada.

Bueno, como parece complejo, intentemos explicar en lo que consiste esto recurriendo a un símil metalúrgico. Cuando tenemos un metal con imperfecciones, podemos recurrir al templado, es decir, podemos elevar la energía de sus átomos y tras un proceso térmico determinado, cuando sus átomos alcanzan un estado de baja energía, obtenemos un metal más perfecto que antes. En el caso de los ordenadores cuánticos adiabáticos que usan el fenómeno "quantum annealing" , ocurre algo similar, cuando los qbits pasan a un estado de baja energía, obtenemos un resultado optimizado para el problema, al igual que cuando se enfría el metal, es mejor que antes.

Desde el punto de vista técnico, al alcanzar la estabilidad de los qbits en un estado de baja energía, los ordenadores cuánticos adiabáticos son más fáciles de construir y de operar que los ordenadorescuánticos con puertas de propósito general, que serían mucho más inestables y podrían ser afectados por el ruido y sobre todo, por la "decoherence",es decir, por las influencias del entorno y de hecho, que yo sepa, todavía no hay ningún ordenador cuántico comercial con puertas de propósito general que funcione adecuadamente para explotar el algoritmo de Shor.

A pesar de que consideramos que un ordenador cuántico de propósito general de 2048 qbits ejecutando el algoritmo de Shor es una seria amenaza para la criptografía moderna de clave pública, los resultados que se podrían obtener con un hipotético ordenador de propósito general puede que no fueran demasiado precisos y siguieran teniendo una fuerte componente heurística, es decir, que solamente proporcionarían una solución con una determinada probabilidad de que fuera correcta. Para que los resultados fueran precisos sería necesario solucionar antes y de forma eficiente, todos los problemas de estabilidad, ruido y decoherencia que afectan a esta arquitectura de puertas de propósito general.

Además se han mitificado mucho estos ordenadores cuánticos. A pesar de que en ocasiones se ha dicho que los ordenadores cuánticos pueden resolver problemas NP-Completos (por ejemplo, el empaquetamiento en cajas, o el mapa de colores), lo cierto es que dicha afirmación es errónea y no pueden hacerlo. De hecho, la factorización de números grandes es un problema BQP (problemas que pueden resolverse en tiempo polinómico con un ordenador cuántico), que está dentro de la clase NP. Una de las características más interesantes de la clase NP, es que las soluciones, aunque son complicadas de conseguir con un ordenador convencional, como es el caso de la factorización de números muy grandes, los resultados se pueden verificar de forma sencilla y rápida, por ejemplo, multiplicando los factores obtenidos.

Desde que apareció el algoritmo de Shor, no podemos decir que la factorización de números grandes sea un problema NP-Completo, que son los problemas más complejos que se pueden establecer dentro de la clase NP. En este momento, no conocemos algoritmos que puedan resolver estos problemas NP-Completos de forma eficiente, es decir, en tiempo polinómico y si somos estrictos, salvo por los algoritmos de Shor (factorización cuántica), de Groover (ordenación cuántica) y qubo (optimización cuadrática), tampoco sabemos de lo que se puede resolver realmente con un ordenador cuántico en un futuro próximo o lejano, por lo que los límites de esta tecnología incipiente no están demasiado bien definidos y hay cierto debate al respecto.

Si se encontrase un algoritmo que resolviera de forma eficiente y en tiempo polinómico un problema NP-Completo, se podría adaptar para intentar solucionar cualquier otro problema NP-Complerto, al menos, en teoría. Y si se encontrase un algoritmo para resolver problemas NP-Completos en tiempo polinómico, esto significaría que toda la teoría de complejidad computacional estaba equivocada y podríamos decir que realmente los problemas NP-Completos serían realmente problemas de la clase P (problemas que se pueden resolver de forma eficiente en tiempo polinómico con un ordenador convencional), es decir, que P=NP, el Santo Grial de la complejidad computacional y de paso, la muerte de la mayor parte de la criptografía actual de clave pública. Si alguien lo demuestra, tendrá un premio de un millón de dólares pagado por el Clay Math Institute de Cambridge, pero aviso a los navegantes, este es un camino duro para cualquiera que lo intente.

Pero, un ordenador cuántico adiabático ¿puede hacer más cosas que optimizar un resultado de un problema de ingeniería mediante el algoritmo qubo?. Bueno, algoritmos cuánticos específicos para esta arquitectura aparte, hay un interesante artículo titulado "Adiabatic quantum computation is equivalent to standard quantum computación", de Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd y Oded Regev, que puede ayudarnos a contestar esta pregunta tan trascendente.

Es más, al no estar tan afectados estos ordenadores adibáticos por los problemas de decoherencia y del ruido térmico, puede que sean más efectivos y precisos que los de propósito general a efectos criptográficos, pero para ello, es necesario crear algoritmos cuánticos específicos para la factorización de grandes números sobre esta nueva arquitectura adiabática, adaptar para la misma el actual algoritmo de Shor o incluso, modificar y ampliar la arquitectura adiabática actual, basada en el flexible algoritmo qubo, para que pueda factorizar números grandes. Por el momento, 10 millones de dólares nos separan de poder trabajar en este campo de los algoritmos cuánticos adiabáticos con un flamante D-Wave One.

La realidad, es que a fecha de hoy, a pesar de que se ha construido el primer ordenador adiabático cuántico comercial y se ha vendido a una importante empresa para su uso intensivo, poco se sabe realmente de la utilidad de estos nuevos ordenadores para otros usos distintos a la optimización de procesos de ingeniería, o si se puede "caracterizar" su hardware para otras funciones distintas, como por ejemplo, para la criptografía, pero también hay otras pistas interesantes sobre otros usos posibles de la máquina de D-Wave.

De esta forma, también se ha comprobado que D-Wave One es capaz de aprender cosas, como por ejemplo, puede reconocer la forma de objetos o de caras particulares en fotos, con una precisión que supera en un 9% a los sistemas tradicionales, pero no solamente es un problema de precisión, lo bueno es que D-Wave One también lo hace muy rápido. Esta característica ha sido experimentada por Google durante varios años como forma de acelerar el software capaz de interpretar las fotos, con todo lo que ello supone, por ejemplo para la privacidad de los usuarios, si se usa como sistema de reconocimiento de caras o lugares en Internet.

Los ingenieros de software de Google lo han usado como una especie de servicio en la nube, accediendo a un sistema cuántico adiabático situado en la sede de D-Wave en Vancouver a través de Internet. Si alguien está interesado en esta capacidad de D-Wave-One, recomiendo este vídeo Training a Binary Classifier with the Quantum Adiabatic Algorithm y este interesante "paper" que tiene el mismo título. Para este proyecto, Google utilizó un chip de D-Wave, también de 128 qbits, llamado Quimera (Chimera), que  permite reconocer y ordenar en un segundo más de 20.000 fotografías. De hecho, Google ha estado buscando algoritmos cuánticos adiabáticos desde 2007, posiblemente, orientados a la resolución de problemas NP o al reconocimiento de caras y formas.

Otro campo en el que puede ser útil D-Wave One, es en el campo de la inteligencia artificial y en especial, en el caso de las Redes de Markov, de hecho, cualquier aplicación de inteligencia artificial que se pueda representar como una Red de Markov, puede ser ejecutada en el D-Wave One sin problemas. Las Redes de Marlov son similares a las Redes Bayesianas, pero hay diferencias entre las dependencias que pueden representar unas y otras. Por ejemplo, las Redes de Markov pueden representar dependencias cíclicas, mientras que las Bayesianas pueden representar dependencias inducidas. Las Redes de Markov tienen muchas aplicaciones, por ejemplo son fundamentales para el reconocimiento automático de imágenes, textos y sonido, o para visión computerizada y diversas aplicaciones 3D, que ahora están tan de moda.

Desde mi punto de vista, el ordenador de D-Wave no supone un riesgo a corto plazo para la seguridad criptográfica con lo que hay sobre la mesa. Pero teniendo en cuenta que la computación cuántica adiabática no es equivalente a la computación cuántica de puertas de propósito general, si se ampliase su capacidad de estos ordenadores adiabáticos hasta los 2048 qbits o más, aparecieran algoritmos específicos de factorización basados en qubo, o se adaptase el hardware de los sistemas adiabáticos para la factorización de grandes números, tendríamos un serio problema de seguridad. Pero ¿quién nos dice que alguien no lo ha hecho ya y no nos lo ha contado?

"Copyleft 2011 Fernando Acero Martí­n. Verbatim copying, translation and distribution of this entire article is permitted in any digital medium, provided this notice is preserved. Quotation is allowed."

Tags: adiabático, criptografía, d-wave one, ordenador cuántico
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments