Lenguajes de alto nivel para la computación cuántica (o computación cuántica para informáticos)

 Los lenguajes de programación cuántica se pueden dividir en cuatro grandes clases (A) imperativos, (B) declarativos (normalmente, funcionales), y (C) otros (algunos son sólo formalismos matemáticos). Hay muchos lenguajes de programación útiles para la computación cuántica, algunos incluso de alto nivel. En la página web de I. Glendinning “Quantum programming languages and tools,” tienes un listado de los más interesantes. El artículo Donald A. Sofge, “A Survey of Quantum Programming Languages: History, Methods, and Tools,” ArXiv Preprint, 7 Apr 2008, presenta una revisión bastante completa de este tipo de lenguajes. Un artículo que también merece la pena leer, pero que es más antiguo, es Roland Rüdiger, “Quantum Programming Languages: An Introductory Overview,” The Computer Journal, Volume 50, Number 2, Pp. 134-150, 2006 (web). 

 

 El primer lenguaje de computación cuántica es la Máquina de Turing Cuántica o Máquina de Deutsch, sin embargo, no resulta nada práctica para implementar algoritmos cuánticas (¿quién usa la Máquina de Turing (Clásica) para programar?). Aún así, si conoces Mathematica, puedes usar el notebook de Joachim Hertel, “Quantum Turing Machine Simulator,” The Mathematica Journal, vol. 8, no. 3, 2002. La implementación de los algoritmos Deutsch-Jozsa, de factorización de Shor, y de búsqueda de Grover, son prácticas muy interesantes utilizando dicho simulador pero requerirían un trabajo “inmenso” (si lo logras no dejes de informarme).

El pseudocódigo propuesto por Knill acabó resultando en el primer lenguaje imperativo cuántico, C quántico (QCL http://tph.tuwien.ac.at/~oemer/qcl.html). Estos lenguajes se basan en utilizar una memoria RAM cuántica (QRAM), con un flujo de control clásico que involucra tantos datos clásicos como cuánticos. Merece la pena leer el proyecto fin de carrera (master thesis) de Bernhard Ömer, “Quantum Programming in QCL,” que incluye implementaciones QCL de los algoritmos cuánticos más populares. Por ejemplo, el algoritmo de Peter Shor para factorización de números requiere 9 páginas de texto en QCL, aunque en pesudocódigo es extraordinariamente corto.

Otro lenguaje cuántico basado en C++ es Q Language. Incluyo construcciones cuánticas básicas para todas las operaciones cuánticas más utilizadas, como QHadamard, QFourier, QNot, QSwap, and Qop. Permite definir nuevos operadores y todo en un contexto “orientado a objetos”.  Discutir otros lenguajes imperativos, como qGCL (quantum Guarded Command Language) de Sanders-Zuliani o LanQ de Mlnarik nos llevaría lejos.

Los lenguajes cuánticos declarativos se basan en el paradigma funcional utilizando una variante cuántica del Lambda cálculo de Church, por ejemplo, el lenguaje introducido por Maymin que ha sido la base de QFC (Quantum Flow Charts) de Selinger que ha dado lugar a QPL (Quantum Programming Language) y a cQPL.

Más información en la Wiki http://www.quantiki.org/wiki/index.php/Quantum_Programming_Language 

Computación cuántica óptica sobre silicio (o primeras puertas lógicas cuánticas en guías ópticas planares integradas)

La portada del número de hoy de Science nos remite a la implementación de puertas lógicas cuánticas basadas en tecnología fotónica integrada en sustratos de silicio, en concreto, utilizando guías ópticas; los autores del trabajo han mostrado que circuitos cuánticos arbitrarios se pueden implementar utilizando guías ópticas planares integradas sobre un sustrato de silicio, en chips convencionales, cuando sobre ellas se propagan fotones individuales. El futuro de esta tecnología es muy prometedor.

Alberto Politi, Martin J. Cryan, John G. Rarity, Siyuan Yu, Jeremy L. O’Brien, “Silica-on-Silicon Waveguide Quantum Circuits,” Science, Vol. 320. no. 5876, pp. 646 - 649, 2 May 2008, ArXiv preprint, han mostrado por primera vez el sueño de muchos especialistas en computación cuántica, cómo usar la luz (fotones) para desarrollar tecnologías cuánticas utilizando arquitecturas basadas en óptica integrada que permiten implementaciones escalables, de gran miniaturización y, como han mostrado para puertas simples, de gran calidad (alta fidelidad “cuántica”). Como primer paso solamente han logrado implementar las puertas lógicas cuánticas más sencillas: la interferencia cuántica de 2 fotones con una visibiliad del 94.8 ± 0.5%, una puerta NO-controlada (CNOT) con una fidelidad en sus estados lógicos del 94.3 ± 0.2%, y un estado con 2 fotones entreladzados con una fidelidad mayor del 92%. Estos resultados muestras cómo es posible “escribir” en una oblea de silicio circuitos cuánticos sofisticados, gérmen de una futura tecnología cuántica basada en fotones, incluyendo computación cuántica y otras tecnologías basadas en información cuántica.

Un bit es la mínima unidad de información “clásica determinista” y representa un 0 o un 1, en la que se basa el ordenador que usas para leer ésto. Un pbit (bit probabilístico) es la mínima unidad de información “clásica no determinista”, representa un 0 con probabilidad p y un 1 con probabilidad 1-p (donde p es un número real entre 0 y 1, con propiedades de probabilidad). Un qubit (bit cuántico) es la mínima unidad de información “cuántica”, representa un estado de superposición (entanglement) entre un estado |0> con amplitud de probabilidad α y un estado |1> con amplitud de probabilidad β (donde α y β son dos números complejos, con módulo y fase; en realidad sólo se necesitan dos números reales para describir un qubit, ya que hay una fase común entre α y β, sólo necesitamos conocer la diferencia de fase, y la suma del cuadrado de las amplitudes de probabilidad debe ser la unidad |α|² + |β|² = 1). La mejor manera de representar un qubit es la esfera de Bloch (ver figura de arriba).

La característica fundamental de los qubits es que cuando son medidos (medida cuántica del estado) se obtiene como resultado un pbit (ver arriba). La puerta lógica NOT (invertir el bit o qubit) en su versión cuántica toma la siguiente forma (ver abajo). Esta puerta tiene como entrada un qubit y como salida también un solo qubit, e “invierte” las amplitudes de probabilidad de ambos estados.

La puerta con dos qubits más sencilla con dos qubits de entrada y dos qubits de salida es el NO-controlado (C-NOT o CNOT). El primer qubit controla si se aplica (1) o no (0) la operación NOT sobre el segundo qubit, de forma que si el primer qubit es 0, la salida coincide con la entrada, pero si es 1, se invierte en el salida el segundo qubit.

Para implementar esta puerta lógica han utilizado la combinación de guías ópticas sobre la oblea de silicio qeu se muestra en esta figura, que muestra además el resultado esperado de las medidas cuánticas del estado del par de qubits a a la salida de esta configuración, así como los resultados experimentalmente medidos. Un resultado muy espectacular. 

Entre las puertas lógicas cuánticas de un qubit de entrada y otro de salida, la más famosa es la que entrelaza el qubit de entrada de forma “equipartita”, la llamada puerta de Hadamard. Cuya representación lógica y resultado es el siguiente.

Los autores han implementado dos combinaciones de puertas de Hadamard y de CNOT, en concreto sendas H a la entrada y salida del bit de control en una CNOT (B) y sólo a la entrada (C) con muy buenos resultados.

CNOT, H y la puerta T (un desfase en uno de los qubits de un par, no implementada por los autores del artículo) forman un conjunto de puertas lógicas universales (cualquier circuito lógico cuántico se puede construir con ellas). La obtención de un set universal con esta nueva tecnología está sólo a un paso.

Los espectaculares resultados obtenidos, utilizando una implementación física extremadamente simple (comparada con realizaciones experimentales previas en fotónica cuántica, que requieren complejos sistemas de interferómetros) demuestra que es posible construir circuitos lógicos cuánticos de gran fidelidad con esta tecnología. Además, aunque sólo a priori, estos circuitos serán fácilmente escalables (aunque habrá que estudiar cómo les afecta el fenómeno de la decoherencia).  

Conferencia en la Universidad de Málaga = Orión, el “primer” computador cuántico comercial - Una introducción a la computación cuántica adiabática

Anuncio INFOUMA 

Conferencia: “Orión, el “primer” computador cuántico comercial. Una introducción a la computación cuántica adiabática”

Resumen: Un tipo de computación cuántica en tiempo continuo (analógica) es la adiabática. Expondremos su evolución histórica, potencia de cálculo, aplicaciones, implementaciones validadas científicamente y otras no validadas como el ordenador Orion de la compañía canadiense D-Wave Systems.

Ponente: Dr. Francisco R. Villatoro (Profesor Titular de la UMA)
Fecha y hora: 12 de marzo de 2008. 11:45 horas
Lugar: Salón de Actos, Complejo Politécnico, E.T.S. Ingeniería Informática
Organiza: Departamento de Lenguajes y Ciencias de la Computación

NUEVO (27 marzo 2008): El Consejo de Estudiantes de Informática de la UMA ha publicado las TRANSPARENCIAS utilizadas en la conferencia (fichero PPT).

Computación cuántica adiabática (o el “primer” ordenador cuántico comercial)

La compañía canadiense D-Wave Systems, anunció el 13 de febrero de 2007 el desarrollo del primer computador cuántico “comercial” llamado Orion de sólo 16 qubits y el 12 de noviembre del mismo año el primer ordenador cuántico de 28 qubits. Su idea es tener un ordenador con 512 qubits disponible en el verano de 2008 y uno de 1024 para finales del mismo. Hasta ahora el ordenador “cuántico” de D-Wave se ha utilizado como oráculo “cuántico” de un programa clásico para resolver algunos problemas sencillos (resolver un sudoku o búsqueda de patrones en imágenes). Para estos problemas la “nueva máquina” es más lenta que un ordenador convencional, pero es de esperar que conforme el número de qubits aumente se obtenga algún tipo de speedup “cuántico”.

FOTO DE UN “CHIP” de ORION

El ordenador Orion de D-Wave se basa en el concepto de computación cuántica adiabática. Propuesto por Farhi, Goldstone, Gutmann y Sipser en el 2000 (”Quantum Computation by Adiabatic Evolution“), este tipo de computación se basa en construir un Hamiltoniano que “físicamente” represente el problema a resolver de tal forma de que su evolución lenta en el tiempo corresponda a una búsqueda de la solución óptima al problema. La idea fue propuesta inicialmente para resolver problemas de satisfacibilidad NP en tiempo polinomial, partiendo de un Hamiltoniano fácilmente construible, el sistema evoluciona hacia el estado final deseado que es solución del problema. También se ha propuesto para resolver el problema del viajante (”Quantum Adiabatic Computation and the Travelling Salesman Problem“, Kieu, 2006), como oráculo “eficiente” de un ordenador clásico.

FOTO del LAYOUT de los 16 QUBITS del ORION

La computación adiabática también permite resolver otro tipo de problemas como los problemas de búsqueda. Mediante una elección adecuada del Hamiltoniano dependiente del tiempo se puede buscar un dato concreto en una base de datos no estructurada en una unidad de tiempo fija, independiente del número de elementos de dicha base de datos (al contrario que el algoritmo de Grover que requiere un número O(sqrt(N)) de operaciones, o un algoritmo clásico que requiere al menos O(N) operaciones) (”Rapid Data Search using Adiabatic Quantum Computation“, Ahrensmeier, Das, Kobes, Kunstatter, Zaraket, 2002). De hecho, ciertas críticas al Orion de D-Wave como ordenador cuántico adiabático es que utiliza el algoritmo de Grover, en lugar del algoritmo más eficiente posible. Lo que ha generado dudas (más aún cuando todavía no han publicado ningún artículo científico sobre Orion en ninguna revista de prestigio) sobre si Orion es realmente un ordenador cuántico adiabático o solamente un computador “clásico” que usa qubits superconductores (es decir, si hay o no entrelazamiento, entanglement, entre los qubits).

Una de las grandes esperanzas de la computación cuántica, la simulación del proceso cuántico de plegamiento de proteínas, también ha sido “atacado teóricamente” mediante computadores adiabáticos (”On the construction of model Hamiltonians for adiabatic quantum computing and its application to finding low energy conformations of lattice protein models“, Perdomo, Truncik, Tubert-Brohman, Rose, Aspuru-Guzik, 2008).

Desde el punto de vista de la potencia computacional, la computación cuántica adiabática es equivalente (polinomialmente) a la computación cuántica estándar (máquina de Turing cuántica de Deutsch) (”Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation“, Aharonov, van Dam, Kempe, Landau, Lloyd, y Regev, 2004).

Por supuesto los computadores cuánticos adiabáticos también sufre el “gran mal” de la decoherencia (acoplamiento cuántico con el entorno) que introduce errores aleatorios en los estados internos de superposición (entanglement) del Hamiltoniano penalizando (o impidiendo) el desarrollo de computadores con un gran número de qubits (”Decoherence in a scalable adiabatic quantum computer“, Ashhab, Johansson, Nori, 2006, y “Decoherence in adiabatic quantum computation“, Amin, Averin, 2007), aunque trabajos anteriores proclamaban “incorrectamente” que eran más robustos ante los errores introducidos por la decoherencia (”Robustness of adiabatic quantum computation“, Childs, Farhi, Preskill, 2001).

En resumen, el futuro de los ordenadores cuánticos adiabáticos, como oráculos de computadores clásicos, es muy prometedor, aunque quizás los “anuncios” de D-Wave están muy mediatizados comercialmente y obtener ordenadores con miles de qubits está todavía muy lejos. Pero, quien sabe, Craig Venter y Celera Genomics aceleraron con su esfuerzo privado el Proyecto Genoma Humano, quizás Geordi Rose (CEO “técnico”) y Herb Martin (CEO “político”) logren que D-Wave acelere el desarrollo del primer ordenador cuántico útil en la práctica.