Las mejores computadoras digitales de hoy en día todavía luchan por resolver, en un marco de tiempo práctico, una cierta clase de problema:problemas de optimización combinatoria, o aquellos que implican examinar un amplio conjunto de posibilidades para encontrar la mejor solución. Las computadoras cuánticas tienen potencial para abordar estos problemas, pero la ampliación del número de bits cuánticos en estos sistemas sigue siendo un obstáculo.

Ahora, Los investigadores del Laboratorio Lincoln del MIT han demostrado una alternativa, forma analógica para acelerar el cálculo de estos problemas. "Nuestra computadora funciona mediante la 'computación con la física' y utiliza la naturaleza misma para ayudar a resolver estos difíciles problemas de optimización, "dice Jeffrey Chou, coautor principal de un artículo sobre este trabajo publicado en Nature's Informes científicos . "Está hecho de componentes electrónicos estándar, permitiéndonos escalar nuestra computadora de forma rápida y económica al aprovechar la industria de microchip existente ".

Quizás el problema de optimización combinatoria más conocido es el del vendedor ambulante. El problema pide encontrar la ruta más corta que un vendedor puede tomar a través de varias ciudades, comenzando y terminando en el mismo. Puede parecer simple con solo unas pocas ciudades, pero el problema se vuelve exponencialmente difícil de resolver a medida que aumenta el número de ciudades, empantanando incluso las mejores supercomputadoras. Sin embargo, los problemas de optimización deben resolverse en el mundo real a diario; las soluciones se utilizan para programar turnos, minimizar el riesgo financiero, descubrir drogas, planificar envíos, reducir la interferencia en las redes inalámbricas, y mucho más.

"Se sabe desde hace mucho tiempo que las computadoras digitales son fundamentalmente malas para resolver este tipo de problemas, "dice Suraj Bramhavar, también coautor principal. "Muchos de los algoritmos que se han diseñado para encontrar soluciones tienen que sacrificar la calidad de la solución por el tiempo. Encontrar la solución óptima absoluta termina tomando un tiempo irrazonablemente largo cuando el tamaño del problema crece". Encontrar mejores soluciones y hacerlo en mucho menos tiempo podría ahorrar a las industrias miles de millones de dólares. Por lo tanto, Los investigadores han estado buscando nuevas formas de construir sistemas diseñados específicamente para la optimización.

Encontrar el ritmo

A la naturaleza le gusta optimizar la energía, o lograr metas de la manera más eficiente y distribuida. Este principio puede atestiguarse en la sincronía de la naturaleza, como las células del corazón latiendo juntas o los bancos de peces moviéndose como uno solo. Similar, si coloca dos relojes de péndulo en la misma superficie, no importa cuándo se ponga en movimiento la péndula individual, eventualmente serán arrullados en un ritmo sincronizado, alcanzando su ápice al mismo tiempo pero moviéndose en direcciones opuestas (o fuera de fase). Este fenómeno fue observado por primera vez en 1665 por el científico holandés Christiaan Huygens. Estos relojes son un ejemplo de osciladores acoplados, configurados de tal manera que la energía se pueda transferir entre ellos.

"Básicamente, hemos construido un versión programable de esta [configuración del reloj] utilizando osciladores no lineales acoplados, "Chou dice, mostrando un video de YouTube de metrónomos mostrando un fenómeno similar. "La idea es que si configura un sistema que codifica el panorama energético de su problema, entonces el sistema naturalmente intentará minimizar la energía sincronizando, y al hacerlo, se decidirá por la mejor solución. Entonces podemos leer esta solución ".

El prototipo del laboratorio es un tipo de máquina Ising, una computadora basada en un modelo de física que describe una red de imanes, cada uno de los cuales tiene una orientación de "giro" magnético que solo puede apuntar hacia arriba o hacia abajo. La orientación final de cada giro depende de su interacción con todos los demás. Las interacciones de espín a espín individuales se definen con un peso de acoplamiento específico, que denota la fuerza de su conexión. El objetivo de una máquina Ising es encontrar, dada una red de fuerza de acoplamiento específica, la configuración correcta de cada giro, arriba o abajo, que minimiza la energía general del sistema.

Pero, ¿cómo resuelve una máquina Ising un problema de optimización? Resulta que los problemas de optimización se pueden mapear directamente en el modelo de Ising, de modo que un conjunto de giros con ciertos pesos de acoplamiento pueda representar cada ciudad y las distancias entre ellas en el problema del vendedor ambulante. Por lo tanto, Encontrar la configuración de giros de menor energía en el modelo Ising se traduce directamente en la solución para la ruta más rápida del vendedor. Sin embargo, Resolver este problema comprobando individualmente cada una de las configuraciones posibles se vuelve prohibitivamente difícil cuando los problemas crecen incluso a tamaños modestos.

En años recientes, ha habido esfuerzos para construir máquinas cuánticas que se mapean en el modelo de Ising, el más notable es uno de la empresa canadiense D-Wave Systems. Estas máquinas pueden ofrecer una forma eficiente de buscar en el gran espacio de soluciones y encontrar la respuesta correcta, aunque operan a temperaturas criogénicas.

El sistema del laboratorio realiza una búsqueda similar, pero lo hace utilizando osciladores electrónicos simples. Cada oscilador representa un giro en el modelo de Ising, y de forma similar adquiere una fase binarizada, donde osciladores que están sincronizados, o en fase, representan la configuración "spin up" y los que están fuera de fase representan la configuración "spin down". Para configurar el sistema para resolver un problema de optimización, el problema se asigna primero al modelo de Ising, traducirlo en pesos de acoplamiento programables que conectan cada oscilador.

Con los pesos de acoplamiento programados, los osciladores pueden funcionar, como el péndulo de cada reloj que se suelta. Entonces, el sistema se relaja naturalmente a su estado de energía mínima general. Leer electrónicamente la fase final de cada oscilador, que representa "girar hacia arriba" o "girar hacia abajo, "presenta la respuesta a la pregunta planteada. Cuando el sistema corrió contra más de 2, 000 problemas de optimización aleatoria, llegó a la solución correcta el 98 por ciento de las veces.

Previamente, Investigadores de la Universidad de Stanford demostraron una máquina Ising que usa láseres y electrónica para resolver problemas de optimización. Ese trabajo reveló el potencial de una aceleración significativa sobre la computación digital, aunque, según Chou, el sistema puede ser difícil y costoso de escalar a tamaños más grandes. El objetivo de encontrar una alternativa más simple encendió la investigación del laboratorio.

Ampliar

El circuito de oscilador individual que el equipo usó en su demostración es similar a los circuitos que se encuentran dentro de los teléfonos celulares o enrutadores Wi-Fi. Una adición que han hecho es una arquitectura de barra transversal que permite que todos los osciladores del circuito se acoplen directamente entre sí. "Hemos encontrado una arquitectura que es escalable para fabricar y puede permitir la conectividad total a miles de osciladores, "Dice Chou. Un sistema completamente conectado permite que se asigne fácilmente a una amplia variedad de problemas de optimización.

"Este trabajo del Laboratorio Lincoln hace un uso innovador de una arquitectura de barra transversal en la construcción de una máquina Ising analógica-electrónica, "dice Peter McMahon, un profesor asistente de física aplicada y de ingeniería en la Universidad de Cornell que no participó en esta investigación. "Será interesante ver cómo funcionan los desarrollos futuros de esta arquitectura y plataforma".

El prototipo de máquina Ising del laboratorio utiliza cuatro osciladores. El equipo ahora está elaborando un plan para escalar el prototipo a un mayor número de osciladores, o "nodos, "y fabricarlo en una placa de circuito impreso". Si podemos llegar a, decir, 500 nodos, existe la posibilidad de que podamos empezar a competir con las computadoras existentes, y a la 1, 000 nodos, es posible que podamos vencerlos, "Dice Bramhavar.

El equipo ve un camino claro hacia la ampliación porque la tecnología se basa en componentes electrónicos estándar. También es extremadamente barato. Todas las piezas para su prototipo se pueden encontrar en un laboratorio típico de ingeniería eléctrica de pregrado y se compraron en línea por alrededor de $ 20.

"Lo que me emociona es la sencillez, ", Añade Bramhavar." Se espera que las computadoras cuánticas demuestren un rendimiento asombroso, pero los desafíos científicos y de ingeniería necesarios para ampliarlos son bastante difíciles. Demostrando incluso una pequeña fracción de las ganancias de rendimiento previstas con las computadoras cuánticas, pero al hacerlo utilizando hardware de la industria electrónica existente, sería un gran paso adelante. La explotación del comportamiento natural de estos circuitos para resolver problemas reales presenta una alternativa muy convincente para lo que podría ser la próxima era de la informática ".

Esta historia se vuelve a publicar por cortesía de MIT News (web.mit.edu/newsoffice/), un sitio popular que cubre noticias sobre la investigación del MIT, innovación y docencia.