Un problema informático bien conocido busca encontrar la ruta más eficiente para que un vendedor viajero visite a clientes en varias ciudades. Aparentemente simple, en realidad es sorprendentemente complejo y muy estudiado, con implicaciones en campos tan amplios como la fabricación ycontrol de 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 más rápidamente. Como se informó el 12 de mayo Comunicaciones de la naturaleza , descubrieron 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 en un nuevo tipo de máquina computacional cuántica, dijo el profesor Eduardo Mucciolo, presidente del Departamento de Físicaen 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, desde el magnetismo hasta la superconductividad. Los métodos derivados de la mecánica estadística también se han aplicado 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 el más bajoenergía. 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 encontradas al pasar de una fase líquida a una de vidrio, donde existen muchas configuraciones competidoras con baja energía", dijo Mucciolo. "Dichas transiciones de fase son lentas".reducir el proceso de enfriamiento a un rastreo, lo que hace que el método sea inútil "
Mucciolo y sus colegas físicos Claudio Chamon y Andrei Ruckenstein de BU superaron este obstáculo al mapear el problema computacional original en un modelo estadístico elegante sin transiciones de fase, que llamaron el modelo de vértice. El modelo se define en una red reticular bidimensional y cada unoEl 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 de la red. El uso de puertas lógicas reversibles y la regularidad de la red fueron ingredientes cruciales para evitar el problema de transición de fase, dijo Mucciolo.
"Nuestro método básicamente ejecuta las cosas a la inversa para que podamos resolver estos problemas muy 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 estas puertas lógicas se satisfagan, la energía es muy baja, por lo tanto, cuando todo está satisfecho, la energía general 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 muestra una transición de fase termodinámica en masa, por lo que se eliminó una de las obstrucciones para alcanzar las soluciones presentes en modelos anteriores", dijo.
El modelo de vértice puede ayudar a resolver problemas complejos en el aprendizaje automático, la optimización de circuitos y otros desafíos computacionales importantes. Los investigadores también están explorando si el modelo se puede aplicar a la factorización de semipretes, números que son el producto de dos primosnúmeros. La dificultad de realizar esta operación con semi-primos muy grandes subyace a la criptografía moderna y ha ofrecido una razón fundamental para la creación de computadoras cuánticas a gran escala.
Además, el modelo puede generalizarse para agregar otro camino hacia la solución de problemas computacionales clásicos complejos aprovechando el paralelismo mecánico cuántico: el hecho de que, según la mecánica cuántica, un sistema puede estar en muchos estados clásicos al mismo tiempohora.
"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 graduado de física en BU, también es coautor del artículo. Las universidades han solicitado una patente sobre aspectos del modelo de vértice.
Fuente de la historia :
Materiales proporcionados por Universidad de Florida Central . Nota: El contenido puede ser editado por estilo y longitud.
Referencia del diario :
Cita esta página :