Una máquina de Ising híbrida es un ordenador que combina computación clásica y cuántica, siendo la parte cuántica una red de espines que sigue el modelo de Ising y la parte clásica un controlador realimentado. Se publican en Science dos máquinas de Ising híbridas, una con 100 bits y la otra con 2048 bits. Los resultados son prometedores, aunque aún no muestran la supremacía cuántica. En cualquier caso, estos ordenadores híbridos tienen muchas aplicaciones potenciales en la resolución de problemas de optimización combinatoria en grafos, nicho de muchos problemas NP-duros en los que la computación híbrida (clásico-cuántica) parece prometedora.

Los artículos son Peter L. McMahon, Alireza Marandi, …, Yoshihisa Yamamoto, «A fully-programmable 100-spin coherent Ising machine with all-to-all connections,» Science (20 Oct 2016), doi: 10.1126/science.aah5178, y Takahiro Inagaki, Yoshitaka Haribara, …, Hiroki Takesue, «A coherent Ising machine for 2000-node optimization problems,» Science (20 Oct 2016), doi: 10.1126/science.aah4243. Más información divulgativa en Adrian Cho, «Odd computer zips through knotty tasks,» Science 354: 269-270 (21 Oct 2016), doi: 10.1126/science.354.6310.269.

El modelo de Ising fue introducido en 1920 por el físico alemán Wilhelm Lenz y su estudiante Ernst Ising para explicar el origen del magnetismo. Cada átomo se comporta como un pequeño imán (gracias a su espín, que es resultado del espín de los electrones de valencia). A alta temperatura, las direcciones de los espines son aleatorias y el campo magnético total es despreciable, luego el material no se comporta como un imán permanente. Por debajo de cierta temperatura crítica, todos los espines apuntan en la misma dirección y aparece un campo magnético macroscópico, luego el material se ha magnetizado. El modelo de Ising pretende describir esta transición de fase en materiales magnéticos.

Cuando se usa un modelo de Ising en computación, se usa una versión generalizada del modelo original. En lugar de una interacción entre espines reducida a los vecinos más cercanos, se considera que todos los espines interaccionan a pares entre ellos. Más aún, se pueden considerar interacciones positivas, que la pareja de espines tiendan a apuntar en la misma dirección, o negativas, que tiendan a apuntar en direcciones opuestas. Los modelos de Ising generalizados permiten resolver muchos problemas de optimización en grafos (tras un mapeado adecuado en un estado de mínima energía). A partir de un estado inicial aleatorio a alta temperatura, se reduce la temperatura obligando al sistema a alcanzar un estado de mínima energía (estado fundamental o “ground state”) que corresponde a una solución al problema de optimización mapeado.

La máquina de Ising de Peter L. McMahon (Univ. Stanford, EE.UU.) y sus colegas se basa en una red de osciladores ópticos paramétricos acoplados (OPOs). Esta red permite simular un modelo de Ising generalizado con interconectividad completa (para 100 espines hay 10.000 conexiones a pares entre ellos). La red es un sistema cuántico, pero está insertado en un sistema de control realimentado, que realiza medidas sucesivas del estado cuántico de la red (measurement-feedback-based OPO Ising machine) con lo que destruye de forma periódica su coherencia cuántica (y por ello no se puede hablar de computación cuántica en sentido estricto). Los interesados en los detalles pueden consultar el artículo publicado en Science.

Se ha resuelto el problema MAX-CUT, dividir los vértices de un grafo en dos conjuntos disjuntos tales que el número de aristas en cada subconjunto sea máximo. Se trata de un problema NP-duro (NP-hard), por lo tanto no se conoce ningún algoritmo clásico eficiente para su resolución. El problema MAX-CUT se puede mapear en un modelo de Ising de tal forma que el número máximo de aristas corresponde a un mínimo energético de la red de espines. El estado cuántico del OPO es medido cada 1,6 μs y el número total de medidas determina el tiempo total de cálculo; en la figura se presentan los resultados para el grafo de la escalera de Moebius (Möbius Ladder graph) con 16 vértices, para el que se requiere unas 100 medidas, luego el tiempo de cálculo ronda los 160 μs (aunque a partir de 120 μs ya se obtiene la respuesta óptima).

Por supuesto, el sistema no obtiene siempre la solución correcta (óptima). Para 16 vértices se obtiene el óptimo el 100% de las ejecuciones, pero para 100 vértices solo el 20% de las veces. En este tipo de algoritmos no deterministas siempre se recomienda ejecutar el algoritmo muchas veces (por ejemplo, 100 veces) y elegir como respuesta óptima la mejor entre ellas (con lo que el tiempo total se multiplica por 100).

McMahon y sus colegas afirman que su máquina de Ising híbrida es escalable. Sin embargo, conforme crece el número de espines (vértices en el grafo) crece el número de veces que el estado final alcanzado es un cuasi-óptimo, tiene baja energía, pero no tiene energía mínima. Por ello, todavía no se ha logrado la supremacía con este tipo de computación (que la máquina híbrida sea más rápida que un ordenador de sobremesa sobre el mismo problema). Siendo optimistas podemos soñar con que se logre en la próxima década.

La máquina de Ising de Takahiro Inagaki (NTT Basic Research Laboratories, Japón) y sus colegas utiliza un enfoque similar, pero con una red de hasta 2048 osciladores ópticos parámetros degenerados (DOPOs) que simulan un modelo de Ising con 2.048 espines y 2.096.128 acoplamientos espín-espín; en la implementación física se usan 5082 DOPOs, pero solo 2048 simulan espines, siendo 2834 usados para obtener las señales de error que usa el algoritmo de control y los restantes 200 se usan para separar ambos grupos de espines. El bucle realimentado de medida tiene un periodo de 5 ms (llamado circulación) y la ejecución del algoritmo requiere unas 1000 circulaciones. Además, la preparación del estado inicial de la red de DOPOs requiere unos ~60 segundos.

Se ha resuelto el problema MAX-CUT para tres grafos llamados G22, G39 y K2000. El resultado de la máquina de Ising coherente (CIM) se ha comparado con el de un algoritmo de recocido simulado (SA) y un algoritmo de Goemans-Williamson de programación semidefinida para Max Cut (GW-SDP), estos dos últimos implementados en un procesador Intel Xeon X5650 (2,67 GHz) de un solo núcleo. Se ha repetido la ejecución 100 veces y se ha elegido la mejor solución. Como muestra esta tabla los resultados de la CIM para G22 y G39 son peores que el SA, pero mejores que GW-SDP, y en ambos casos inferiores a la mejor solución conocida. Sin embargo, para K2000 el mejor resultado es el mejor de todas (par este problema concreto es la mejor solución conocida). Por ello se trata de un resultado bastante prometedor, siendo la CIM un prototipo.

Por cierto, hay que tener cuidado con los tiempos de ejecución. Para GW-SDP el tiempo es fijo, per para SA y CIM no se ha contabilizado el tiempo de lectura/escritura para la transferencia de información del model de Ising al controlador clásico. Con seguridad la ejecución de GW-SDP en una máquina clásica más poderosa y durante más tiempo permitiría que obtuviera una solución comparable a SA y CIM.

En resumen, se publican en Science dos máquinas de Ising híbridas, que combinan una arquitectura cuántica con osciladores ópticos paramétricos y un bucle realimentado clásico. No han logrado la supremacía cuántica, pero su posible escalabilidad, en mi opinión aún no demostrada, parece prometedora. Quizás en menos de una década estas arquitecturas híbridas empiecen a darnos agradables sorpresas.