Solucionador analógico supera a computadoras digitales en optimización NP-difícil

• Investigadores construyen un nuevo sistema que puede resolver un problema de optimización discreta por excelencia, llamado MaxSAT.
• Este solucionador analógico funciona mejor que las computadoras digitales y puede extenderse a otros problemas de optimización.

Las computadoras digitales actuales realizan bien la mayoría de las tareas. Son perfectas para ciertos cálculos, procesamiento de textos, navegación web y artes gráficas. Pero como dependen del código binario — 0s y 1s — no son ideales para resolver todos los problemas.

La computación digital casi ha alcanzado su potencial máximo, y por eso algunos matemáticos han empezado a interesarse en revivir la computación analógica. Puede ayudar a avanzar la computación más allá del marco digital.

Recientemente, investigadores de la Universidad de Notre Dame y la Universidad Babes-Bolyai, Rumanía, desarrollaron un nuevo solucionador analógico que puede evaluar las mejores soluciones de problemas NP-duros.

Problema NP-duro significa que no hay algoritmo que pueda resolver el problema en tiempo polinomial. El tiempo requerido para llegar a la solución aumenta exponencialmente con el tamaño del problema. Usualmente, estos problemas se asocian con imágenes médicas, bioinformática, plegamiento de proteínas y planificación.

Los investigadores probaron su solucionador analógico en una amplia gama de problemas NP-duros y encontraron que este nuevo método tiene el potencial de llevar a mejores soluciones en menos tiempo.

¿Por qué computación analógica?

Las computadoras analógicas fueron extremadamente populares a mediados del siglo XX. Cada gran administración y empresa preocupada por problemas de dinámica tenía un centro gigante de computación analógica. Se usaban para lanzar cohetes al espacio, guiar armas en acorazados y simular dinámica de aeronaves.

A diferencia de las computadoras digitales, las computadoras analógicas usan datos no discretos como voltaje, peso, velocidad, temperatura y presión. Y como usan valores continuos, son inmunes al ruido de cuantización.

Las computadoras analógicas pueden diseñarse para resolver una variedad de problemas. Pueden realizar operaciones matemáticas directamente. Por ejemplo, para restar 8 de 3, las computadoras analógicas restan voltajes que corresponden a esos valores y luego proporcionan inmediatamente la salida correcta.

Pueden usarse para operaciones en tiempo real y computación simultánea. En caso de problemas analógicos, pueden proporcionar información sobre los problemas y errores. Y como no requieren cuantización, son perfectas para modulación/demodulación de señales y control de motores de alta velocidad.

Referencia: Nature Communications | doi:10.1038/s41467-018-07327-2 | Universidad de Notre Dame

Sin embargo, las computadoras digitales tomaron el mercado en los años 1980. Eran suficientemente flexibles, rápidas y más precisas en realizar tareas generales. A medida que llegaron algoritmos eficientes, su rendimiento mejoró aún más.

Una computadora analógica vintage AMF665D | Crédito de imagen: Francis Massen / YouTube

Pero las computadoras digitales, incluidas las modernas, no pueden resolver problemas NP-duros con variables grandes. La dificultad con la mayoría de los problemas de optimización es que no puedes determinar si la solución(es) es óptima. Asegurar que no hay ninguna solución mejor es tan difícil como el problema mismo.

Solucionador analógico de alto rendimiento

El nuevo sistema dinámico de tiempo continuo puede resolver un problema de optimización discreta por excelencia, llamado MaxSAT. El método se basa en un conjunto determinista de ecuaciones diferenciales ordinarias y una técnica heurística para predecir la probabilidad de que la solución óptima haya sido evaluada por el tiempo analógico t.

En circuitos analógicos, el cuello de botella de von Neumann se elimina: el circuito en sí actúa como procesador y memoria. Implementar el enfoque en computadoras digitales, por otro lado, requiere el uso de un algoritmo integrador de ecuaciones diferenciales ordinarias que discretiza las ecuaciones de tiempo continuo y las resuelve paso a paso mientras maneja errores.

En forma digital, el solucionador no funciona eficientemente porque la dinámica evoluciona varios miles de ecuaciones diferenciales ordinarias acopladas, lo que es un proceso de integración que consume mucho tiempo.

Lea: Datos más interesantes sobre computadoras cuánticas

Y como el enfoque usa caracteres generales, puede extenderse a otros problemas de optimización también. Los investigadores planean diseñar y construir dispositivos basados en este nuevo enfoque.