Para resolver las tareas de optimización más difíciles, solo agregue láseres

Un extraño dispositivo conocido como Ising Optical Machine es capaz de controlar el tráfico aéreo y ayudar a la NFL a programar juegos.

El año pasado, una falla en el sistema de distribución entre los empleados de American Airlines podría llevar a la interrupción del horario de miles de vuelos durante la temporada de vacaciones. El error permitió a los pilotos rechazar vuelos sin ser reemplazados por otro piloto, y cerca de 15,000 vuelos fueron amenazados. Y aunque la aerolínea logró rastrear el problema a tiempo y distribuir empleados , este desastre se convirtió en un recordatorio de cuánto dependemos de las computadoras para organizar el horario de trabajo de una gran cantidad de servicios y funciones, de los cuales nuestra comunidad ahora depende completamente.

Por ejemplo, todas las principales aerolíneas tienen sofisticados algoritmos de optimización de gráficos que comparan a los pilotos y los vuelos. Y aunque el incidente con American Airlines no ocurrió directamente por la falla del algoritmo, el resultado podría ser similar. Tal rechazo llevaría a cientos de miles de personas en una situación difícil o muy inconveniente mientras la aerolínea buscaba una salida a la situación.

El triunfo de la ciencia algorítmica y la ley de Moore es que ahora podemos abordar muchas tareas complejas de optimización, incluidas áreas como el transporte, la logística y la programación. La mayor parte del mundo moderno no podrá funcionar normalmente sin estos algoritmos: anualmente 50,000 buques de carga transportan mercancías, se generan 25,000 TWh de electricidad y los enrutadores transportan 1 Zettabyte de tráfico a través de ellos mismos. Todo esto funcionaría mucho menos eficientemente. Sin embargo, las organizaciones a menudo trabajan con soluciones subóptimas debido a plazos ajustados y la falta de recursos informáticos disponibles. Además, todavía hay muchas oportunidades para mejorar los métodos que utilizamos para ayudar a resolver la mayoría de los problemas de optimización.

Dada la importancia de la optimización y el hecho de que la era de las mejoras estables y mayores en la velocidad del procesador parece estar llegando a su fin, los investigadores comenzaron a estudiar la cuestión de si las máquinas especialmente diseñadas para la optimización pueden mejorar significativamente nuestra capacidad para resolver problemas complejos.

Un enfoque prometedor es el desarrollo de máquinas ópticas diseñadas para la optimización. Un grupo de científicos de la Universidad de Stanford (que incluye al autor del artículo), dirigido por Yoshihik Yamamoto, comenzó estos estudios hace siete años. Ahora este tema está siendo estudiado por varios grupos de científicos, así como por investigadores de los laboratorios HP y NTT . Después de años de trabajo, existe una creciente confianza en que al menos uno de estos grupos algún día podrá crear una máquina que pueda ayudarnos a abordar algunos de los problemas de optimización más difíciles que la industria moderna necesita resolver.


La tarea del vendedor: la complejidad de las tareas, como encontrar el camino más corto entre varios puntos, aumenta con el número de puntos. Modelarlos bajo la apariencia de problemas de optimización de Ising puede ayudar a resolverlos más rápido.

Recuerde el clásico problema del vendedor, en el que el vendedor se mueve de ciudad en ciudad, vendiendo bienes. No quiere perder tiempo y dinero en gasolina. Esta tarea de optimización, cuyo propósito es encontrar el camino más corto para el vendedor, dado que necesita llegar a cada punto una vez, y al final del viaje quiere regresar a donde comenzó.

Para cinco ciudades, el problema se resuelve simplemente. Se puede calcular simplemente considerando las 12 rutas . Sin embargo, si el trabajador-vendedor tiene la intención de visitar 50 ciudades, entonces el método de búsqueda que considera todas las rutas posibles será insoportable: habrá más de estas rutas que el nuevo decillón , o 10 ⁶⁰ - uno y 60 ceros.

Las posibles soluciones a este problema se nos pueden dar mediante algoritmos que utilizan diferentes rutas de derivación y aproximaciones razonables. Pero incluso los mejores pueden hacer pensar a la computadora más poderosa. En un ejemplo reciente, la Universidad de Waterloo de Canadá trató de encontrar el camino más corto entre casi 50,000 ciudades en los Estados Unidos que estaban en el registro nacional de lugares históricos y probar la exactitud de su decisión. Para hacer esto, utilizó 310 potentes procesadores que funcionaron sin parar durante 9 meses.

Pero la optimización implica muchas más tareas que solo la tarea del vendedor. Otro desafío es la programación. Por ejemplo, la National Football League en los Estados Unidos debe programar anualmente varios cientos de juegos, mientras trata de cumplir con miles de reglas, que, por ejemplo, prohíben a los equipos jugar más de tres juegos en su propio campo en una fila. Para resolver este problema, en 2017, la NFL utilizó un grupo de 400 computadoras .


Optimización de Ising : en este problema de Ising, la energía del sistema es menor cuando los espines de sus electrones se dirigen en direcciones opuestas a los espines de los vecinos. Los sistemas que pueden encontrar el estado con energía mínima en el modelo Ising pueden ayudar a acelerar la solución de problemas complejos de optimización.

Las empresas manufactureras necesitan planificar el mantenimiento de la máquina. Las universidades necesitan un horario. Los servicios de correo deben planificar rutas de entrega. A las grandes ciudades, como Pekín o Tokio, les encantaría aprender a gestionar eficazmente los flujos de millones de automóviles que intentan conducir por sus calles durante las horas pico. Estas tareas pueden incluir cientos o miles de eventos que deben planificarse y, en muchos casos, las soluciones prácticas aún no están disponibles, ya que requieren demasiado tiempo de computadora o demasiadas computadoras.

Durante muchos años, los investigadores han estado tratando de crear máquinas especiales para resolver problemas de optimización. A mediados de la década de 1980, David Tank, que trabajaba en los laboratorios AT&T Bell, y John Hopfield, ambos que trabajaban en AT&T Bell y Caltech, sugirieron usar circuitos electrónicos analógicos que representaran redes neuronales para resolver problemas de optimización como el problema del vendedor ambulante. Su trabajo dio lugar a décadas de investigación en esta área. Luego, en 1994, Leonard Edleman, de la Universidad del Sur de California, descubrió que, en teoría, el ADN puede usarse para resolver problemas de este tipo. Su idea dio lugar a una serie de investigaciones similares. Sin embargo, estos intentos de desarrollar enfoques radicalmente nuevos y efectivos para resolver problemas de optimización han llevado a alternativas prácticas a las computadoras y tecnologías convencionales, que siguen siendo las herramientas principales para resolver estos problemas.

Los intentos de crear máquinas ópticas especiales capaces de resolver problemas de optimización se han concentrado en uno de estos problemas, conocido como optimización de Ising. Fue nombrada en honor al físico Ernst Ising, el famoso trabajo sobre el modelo de momentos magnéticos y su explicación de las transiciones entre diferentes estados magnéticos. Resulta que muchos problemas comunes de optimización, incluida la programación y la búsqueda de rutas, pueden convertirse fácilmente en problemas de optimización de Ising.

Para comprender cómo se relaciona el modelo de Ising con la optimización, debe comenzar usándolo en física para comprender el magnetismo. Considere una barra magnética convencional. Usando el modelo de Ising, uno puede imaginar una barra magnética, como una red tridimensional de átomos, en la que cada uno de los átomos es una barra magnética. Los electrones en los átomos tienen una propiedad llamada espín. Los giros de los electrones de valencia, ubicados en las capas externas del átomo, se dirigen hacia arriba o hacia abajo. La dirección de los giros determina la magnetización del material. Si todas las espaldas están dirigidas hacia arriba, el material está magnetizado. Si está abajo, el material también está magnetizado, solo con la polaridad opuesta. Si las partes posteriores están mezcladas, el material no está magnetizado.

Estos giros también interactúan entre sí. En una barra magnética, la " energía total " de dos electrones vecinos es menor si sus espines están alineados, es decir, se dirigen en la misma dirección. Por el contrario, su energía total es mayor si los giros son multidireccionales.


Máquina Ising óptica: un oscilador paramétrico óptico (OPO) con retroalimentación de medición puede resolver los problemas de optimización expresados ​​en la forma del modelo Ising: un conjunto de espines de electrones y su influencia mutua. Las fases de los pulsos ópticos en OPO representan giros, y el efecto se introduce en una matriz de compuerta programable por el usuario ( PPM ). Es necesario completar alrededor de cien pasos a través del sistema antes de que los impulsos en el OPO se vuelvan lo suficientemente potentes como para producir una solución al problema.

En el modelo de Ising, resumimos la energía de las interacciones entre los espines de cada par de electrones en un conjunto de átomos. Dado que la cantidad de energía depende de si los giros están alineados o no, la energía total del conjunto depende de la dirección de todos los giros del sistema. Por lo tanto, la tarea general de la optimización de Ising es determinar en qué estado deben estar los giros para minimizar la energía del sistema.

En el modelo más simple, se cree que solo los giros adyacentes interactúan. Sin embargo, en el problema general de optimización de Ising, cualquier giro puede interactuar con cualquier otro, independientemente de la distancia, y el signo y la fuerza de estas interacciones pueden ser únicos para cada par de espaldas. En una formulación tan generalizada, este problema es muy difícil de resolver, al igual que resolver el problema de un vendedor que visita a cientos de miles de compradores potenciales. Si podemos encontrar una manera de resolver rápidamente los problemas de optimización de Ising, y una forma de hablar sobre el problema del vendedor ambulante y problemas similares de la misma manera que los problemas de Ising, también podremos resolver estos problemas rápidamente. La energía mínima del sistema en el problema de Ising representará la ruta más rápida entre ciudades, la solución más efectiva para empacar un buque de carga o cualquier otro problema de optimización que necesitemos.

Entonces, ¿cómo se convierte el camino de un vendedor viajero en espaldas? La tarea principal es establecer el cumplimiento: debemos presentar nuestro problema de optimización de forma que una máquina diseñada para resolver los problemas de optimización de Ising pueda resolverlo. Primero, debe comparar el problema de optimización inicial, por ejemplo, encontrar una manera para el vendedor de aspiradoras, con un conjunto de giros y determinar cómo se afectan entre ellos. Gracias a los estudios realizados en las últimas décadas tanto en informática como en investigación de operaciones , generalmente se conoce una comparación de varios problemas de optimización con formas de Ising.

Sin embargo, es difícil trabajar con átomos individuales y los espines de sus electrones, por lo que nos concentramos en crear una máquina que implemente el modelo Ising utilizando pulsos de luz en lugar de espines de electrones. El problema de Ising se compara con momentos e interacciones entre ellos. El resultado se evalúa en términos de la energía total del problema, y ​​un estado con energía mínima se considera la solución óptima. Luego, esta decisión se traduce a un lenguaje que tiene sentido para la tarea original, por ejemplo, en la forma más breve de un vendedor.

La clave de la capacidad de nuestro prototipo para hacer coincidir los giros con los pulsos de luz es el OPO, un dispositivo similar al láser. Pero OPO, a diferencia de un láser convencional, produce luz que está exactamente en fase, o exactamente en antifase, a alguna luz básica. Esto es exactamente lo que se necesita para representar los estados binarios del giro, arriba y abajo. Podemos imaginar un giro dirigido hacia arriba como un estado en el que la luz del OPO está en fase con la base, y viceversa, un giro dirigido hacia abajo corresponde a la luz en antifase.

Hay varias formas de crear una máquina Ising con OPO. Los grupos de NTT, Caltech, Cornell y Columbia, entre otros, tienen enfoques diferentes. El prototipo de la máquina Ising, que se mostró por primera vez en Stanford en un experimento dirigido por Alireza Marandi (que ahora trabaja en Caltech), utilizó una tecnología con la que seguimos trabajando: multiplexación por división de tiempo multiplex y conexión óptica.

Veamos este término difícil. Comenzamos con una fuente láser pulsada. La fuente envía pulsos simultáneos de luz que duran varios picosegundos en dos direcciones. El primer impulso se vuelve básico; se divide y recorre dos caminos diferentes.

El segundo se utiliza como fuente de energía para OPO: estimula un cristal en OPO, que emite pulsos de fotones. Cada pulso se transmite a una bobina de cable de bucle óptico de varios cientos de metros de largo, dependiendo de la cantidad de pulsos que necesitemos. Hay cientos o incluso miles de pulsos OPO en este anillo, y perseguirán en un círculo uno tras otro, atravesando el cristal una y otra vez.


Arriba: El autor del artículo y su ex compañera de laboratorio, Alireza Marandi, están mirando el prototipo de la computadora óptica de Ising.
Abajo: la mayoría de los eventos tienen lugar dentro del carrete de cable óptico

Las fases de estos pulsos desempeñarán el papel de los giros del modelo Ising. Pero inmediatamente después de su creación, antes de pasar por el ciclo varias veces, son tan débiles que sus fases no están bien definidas. La forma en que hacemos que interactúen finalmente les dará las fases finales y nos dará la solución a nuestro problema Ising.

¿Recuerdas la luz base de la descripción del experimento? En un punto del bucle hay un divisor que selecciona una pequeña porción de cada pulso, que se compara con el pulso base en el detector de homodina. El voltaje de salida del detector contiene información sobre la fase y la amplitud del detector. Esta señal se digitaliza y se alimenta al PPVM. En él, se presenta el problema de Ising.

Recuerde que resolver el problema de Ising significa encontrar el estado de energía mínimo para un conjunto de giros en el que los giros interactúan de diferentes maneras, y estas interacciones agregan energía adicional a la energía total del sistema. En HME, cada impulso denota un giro. Por lo tanto, para cada pulso, y en nuestra configuración usamos 100, el PPMM realiza cálculos, que incluyen las mediciones registradas de todos los otros pulsos que, de acuerdo con el problema de Ising, deberían afectar el giro en consideración. Luego, el procesador aplica los cálculos a la configuración del modulador de intensidad y el modulador de fase ubicados en una de las rutas del pulso base. El pulso base modificado se alimenta al anillo del cable de fibra óptica, en el cual el OPO pulsa snoop.

Es fundamental elegir el momento correcto: necesitamos el pulso base combinado para combinarlo con el pulso OPO correcto. Si se hace correctamente, los dos pulsos se mezclarán. Dependiendo de si están en fase o no, el impulso introducido en el sistema inclina el impulso OPO para representar un giro dirigido hacia arriba o hacia abajo.

Para cada impulso OPO en el bucle, repetimos todo este proceso, y para alcanzar los estados de fase final, los pulsos pueden viajar decenas de miles de veces a lo largo de todo el bucle. Después de eso, una computadora separada lee un conjunto de fases, las interpreta como electrones del problema Ising con giros apuntando hacia arriba o hacia abajo, y luego convierte esto en una solución significativa al problema de optimización inicial que necesita resolver.

En nuestros experimentos, primero hicimos un sistema con cuatro giros, y luego con 16 giros. Los parámetros de la tarea estaban basados ​​en hardware en instalaciones en forma de segmentos ramificados de un cable óptico de cierta longitud. En estos experimentos, descubrimos con éxito estados de energía mínima, y ​​esto nos motivó a desarrollar este enfoque. En 2016, creamos una máquina de retroalimentación basada en PPVM capaz de resolver problemas de Ising con 100 giros. La comparación de la velocidad de nuestras instalaciones con los sistemas especializados, incluido el aparato de " recocido cuántico " de la NASA, nos dio la confianza de que las máquinas Ising OPO pueden ser optimizadores eficientes.

Los resultados fueron prometedores, pero todavía tenemos mucho que aprender antes de comprender si tal enfoque óptico puede incluso adelantarse a un procesador convencional para resolver problemas prácticos de optimización. Es posible que la capacidad de la máquina para resolver problemas se pueda mejorar utilizando estados cuánticos de luz, que son muy difíciles de simular. Solo nos estamos acercando a la solución de muchas de estas preguntas, y planeamos en los próximos años estudiar la interacción extremadamente interesante de la teoría y el experimento, desarrollando este nuevo tipo de computadora.