Un conocido problema computacional busca encontrar la ruta más eficiente para que un viajante de comercio visite clientes en varias ciudades. Aparentemente simple, en realidad es sorprendentemente complejo y muy estudiado, con implicaciones en campos tan amplios como la fabricación y el control del tráfico aéreo.

Investigadores de la Universidad de Florida Central y la Universidad de Boston han desarrollado un enfoque novedoso para resolver problemas computacionales tan difíciles con mayor rapidez. Como se informó el 12 de mayo en Comunicaciones de la naturaleza , han descubierto una forma de aplicar la mecánica estadística, una rama de la física, para crear algoritmos más eficientes que puedan ejecutarse en computadoras tradicionales o un nuevo tipo de máquina computacional cuántica, dijo el profesor Eduardo Mucciolo, presidente del Departamento de Física de la Facultad de Ciencias de la UCF.

La mecánica estadística se desarrolló para estudiar sólidos, gases y líquidos a escalas macroscópicas, pero ahora se usa para describir una variedad de estados complejos de la materia, del magnetismo a la superconductividad. También se han aplicado métodos derivados de la mecánica estadística para comprender los patrones de tráfico, el comportamiento de las redes de neuronas, avalanchas de arena y fluctuaciones del mercado de valores.

Ya existen algoritmos exitosos basados ​​en la mecánica estadística que se utilizan para resolver problemas computacionales. Tales algoritmos mapean problemas en un modelo de variables binarias en los nodos de un gráfico, y la solución se codifica en la configuración del modelo con la energía más baja. Al construir el modelo en hardware o una simulación por computadora, los investigadores pueden enfriar el sistema hasta que alcance su energía más baja, revelando la solución.

"El problema con este enfoque es que a menudo es necesario pasar por transiciones de fase similares a las que se encuentran al pasar de una fase líquida a una vítrea, donde existen muchas configuraciones competitivas con baja energía, "Dijo Mucciolo." Tales transiciones de fase ralentizan el proceso de enfriamiento a un lento, inutilizando el método ".

Mucciolo y sus compañeros físicos Claudio Chamon y Andrei Ruckenstein de BU superaron este obstáculo mapeando el problema computacional original en un elegante modelo estadístico sin transiciones de fase, al que llamaron modelo de vértice. El modelo se define en una celosía bidimensional y cada vértice corresponde a una puerta lógica reversible conectada a cuatro vecinos. Los datos de entrada y salida se encuentran en los límites del enrejado. El uso de puertas lógicas reversibles y la regularidad de la celosía fueron ingredientes cruciales para evitar el problema de la transición de fase. Dijo Mucciolo.

"Nuestro método básicamente ejecuta las cosas al revés para que podamos resolver estos problemas tan difíciles, "Dijo Mucciolo." Asignamos a cada una de estas puertas lógicas una energía. Lo configuramos de tal manera que cada vez que se satisfagan estas puertas lógicas, la energía es muy baja, por lo tanto, cuando todo esta satisfecho, la energía total del sistema debería ser muy baja ".

Chamon, profesor de física en BU y líder del equipo, dijo que la investigación representa una nueva forma de pensar sobre el problema.

"Este modelo no presenta una transición de fase termodinámica masiva, así se eliminó uno de los obstáculos para llegar a soluciones presentes en modelos anteriores, " él dijo.

El modelo de vértice puede ayudar a resolver problemas complejos en el aprendizaje automático, optimización del circuito, y otros importantes desafíos computacionales. Los investigadores también están explorando si el modelo se puede aplicar a la factorización de semiprimos, números que son el producto de dos números primos. La dificultad de realizar esta operación con semiprimos muy grandes es la base de la criptografía moderna y ha ofrecido una razón fundamental para la creación de computadoras cuánticas a gran escala.

Es más, el modelo se puede generalizar para agregar otro camino hacia la solución de problemas computacionales clásicos complejos aprovechando el paralelismo de la mecánica cuántica, el hecho de que, según la mecánica cuántica, un sistema puede estar en muchos estados clásicos al mismo tiempo.

"Nuestro artículo también presenta un marco natural para la programación de dispositivos computacionales de propósito especial, como las máquinas de D-Wave Systems, que utilizan la mecánica cuántica para acelerar el tiempo de solución de problemas computacionales clásicos, "dijo Ruckenstein.

Zhi-Cheng Yang, un estudiante de posgrado en física en la BU, también es coautor del artículo. Las universidades han solicitado una patente sobre aspectos del modelo de vértice.