Resolver el ‘Problema del Viajante’ mediante la Computación Cuántica

Un problema algorítmico clásico en el campo de la informática conocido como el Problema del Viajante (TSP) es un ejemplo destacado de un problema de optimización combinatoria.

¿Qué es exactamente el TSP? Este clásico de las matemáticas implica encontrar la ruta más corta posible para visitar N ciudades exactamente una vez antes de regresar a la ciudad de origen. Sin embargo, a medida que aumenta el número de ciudades, también lo hacen las rutas posibles y el tiempo de cálculo para encontrar la solución óptima. Mientras que este problema puede resolverse mediante métodos de aproximación, los ordenadores cuánticos podrían ofrecer soluciones mucho mejores y mucho más rápidamente. 

Esto es precisamente lo que demostró el equipo del físico teórico Prof. Dr. Jens Eisert: que dichos problemas pueden resolverse de manera mejor y más rápida con ordenadores cuánticos.

La computación cuántica utiliza hardware y algoritmos que aprovechan la mecánica cuántica para resolver problemas complejos más allá del alcance de los convencionales, incluidos los superordenadores. A pesar de su potencia, los superordenadores —masivas computadoras clásicas con miles de núcleos CPU y GPU— están limitados por su dependencia de la tecnología de transistores del siglo XX al resolver problemas de alta complejidad. 

Aquí es donde entra la física cuántica. En contraste con los ordenadores clásicos, que codifican la información en bits binarios (0 y 1), los ordenadores cuánticos utilizan bits cuánticos o qubits para ejecutar algoritmos cuánticos multidimensionales. 

Además, a diferencia de los ordenadores convencionales, que utilizan ventiladores para refrigerar, los ordenadores cuánticos requieren que sus procesadores cuánticos se mantengan a temperaturas extremadamente bajas para conservar sus estados cuánticos. Esto se logra mediante superfluidos criogénicos. 

Los superconductores son materiales que presentan un efecto cuántico crítico, permitiendo que los electrones se desplacen a través de ellos sin resistencia. A medida que los electrones atraviesan, se emparejan para transportar carga a través de barreras. Cuando dos superconductores se colocan a cada lado de un aislante, se forma una unión Josephson, que se utiliza para conducir qubits superconductores.  

Un qubit es útil en la importante tarea de colocar su información cuántica en un estado de superposición, una combinación de las posibles configuraciones del qubit. Los grupos de qubits en superposición pueden crear espacios computacionales complejos y multidimensionales donde se pueden representar problemas complejos.

Aquí, mediante el entrelazamiento de dos qubits, los cambios en uno pueden afectar directamente al otro, mientras que cuando estos qubits entrelazados se colocan en un estado de superposición, obtenemos una gran cantidad de probabilidades. El cálculo en un ordenador cuántico funciona preparando una superposición de todos los estados computacionales posibles y, a través de la interferencia, se encuentran las soluciones.

Por supuesto, construir un ordenador cuántico con muchos qubits es un procedimiento muy complejo, aunque se están explorando varios métodos sobre lo que tales ordenadores pueden lograr. 

Según Eisert, quien dirige un grupo de investigación conjunto en el Helmholtz-Zentrum Berlin (HZB), un centro de investigación de materiales energéticos, y en la universidad pública Freie Universität Berlin:

“Hay muchos mitos al respecto, y a veces una cierta cantidad de palabrería y exageración. Sin embargo, hemos abordado el tema de manera rigurosa, utilizando métodos matemáticos, y hemos entregado resultados sólidos sobre el asunto. Sobre todo, hemos aclarado en qué sentido pueden existir ventajas.”

El Problema Crítico del Viajante

Un problema de optimización, el TSP tiene una gran importancia económica en la industria de la logística y la cadena de suministro. Forma parte de la categoría más amplia de problemas de optimización combinatoria, que también incluye la programación de trabajos, la asignación de recursos, la optimización de carteras e incluso el plegamiento de proteínas, todos críticos para varios sectores.

Dada la importancia social y económica de estos problemas, han sido objeto de una intensa investigación. Como tal, encontrar la respuesta a problemas como la cadena de suministro más eficiente y la ruta de entrega más barata tiene un impacto positivo en nuestra vida diaria.

Sin embargo, optimizar las rutas de entrega para múltiples destinos considerando diversas restricciones como la congestión del tráfico, el aumento de los costos operativos, cambios repentinos de ruta, citas de última hora y solicitudes de clientes hace que el TSP sea aún más desafiante de resolver. A pesar de estos retos, resolver el TSP es crucial para la entrega eficiente de bienes, lo que garantiza un modelo de negocio viable. 

Hay muchos beneficios al resolver este problema, incluyendo la reducción de la distancia y las horas de viaje y el ahorro de combustible. Minimizar la distancia recorrida puede ayudar a reducir significativamente la huella de carbono, lo que se traduce en una mejor calidad del aire, una desaceleración del cambio climático y crecimiento económico. Además, resolver el TSP puede ayudar con la entrega puntual de bienes y reuniones a tiempo con clientes, lo que mejora la experiencia del cliente y los negocios de servicio de campo.

Como hemos visto, resolver el problema no solo ayuda a las empresas, sino que estos beneficios se extienden a los clientes, enriqueciendo la experiencia de todos los involucrados.

Se pueden utilizar varios métodos para resolver el problema del TSP. Uno de ellos es el enfoque de ‘Fuerza Bruta’, que calcula todas las permutaciones posibles para encontrar la ruta más corta. En el método de ramificación y acotación, el problema se divide en varias series de subproblemas, y la solución de cada etapa influye en la solución encontrada en etapas posteriores.

En la programación dinámica, el foco está en evitar cálculos redundantes. Mientras tanto, el Vecino Más Cercano es un algoritmo de aproximación en el que se comienza con la ubicación de inicio y luego se detiene en la más cercana. Una vez cubiertas todas las ciudades, se regresa al punto de partida. Aunque práctico y relativamente rápido, este método puede no siempre proporcionar una ruta eficiente.

A medida que la tecnología avanza, la planificación y optimización de rutas pueden realizarse de manera mucho más eficaz. La Inteligencia Artificial (IA), en particular, también puede ayudar a resolver el problema analizando rápidamente una gran cantidad de datos para ayudar a muchas empresas modernas a tomar decisiones operativas y estratégicas.

Los ordenadores cuánticos también están siendo investigados para resolver el problema; después de todo, ofrecen considerables aceleraciones computacionales respecto a los ordenadores clásicos. Hace tiempo se ha sugerido que estos ordenadores podrían ayudar a mejorar las aproximaciones a estos problemas. 

Uso de Técnicas de Computación Cuántica para Resolver el TSP

Mientras la computación cuántica está generando un enorme interés y proporcionando resultados prometedores para ciertos problemas, el alcance de esta ventaja cuántica sigue siendo en gran parte inexplorado. 

Como tal, el estudio proporcionó una prueba constructiva completa de que los ordenadores cuánticos pueden superar realmente a los ordenadores convencionales para encontrar aproximaciones a problemas de optimización combinatoria.

El estudio más reciente, liderado por Eisert y su colega Jean‑Pierre Seifert, utilizó únicamente métodos analíticos para evaluar hasta qué punto un ordenador cuántico con qubits puede resolver el problema del TSP. 

“Simplemente asumimos, independientemente de la realización física, que hay suficientes qubits y examinamos las posibilidades de realizar operaciones de cálculo con ellos”, lo que revela una semejanza con un problema común en criptografía, es decir, el cifrado de datos, explicó Vincent Ulitzsch, estudiante de doctorado en la Universidad Técnica de Berlín. 

Luego, el equipo utilizó el algoritmo de Shor, un algoritmo cuántico, para encontrar los factores primos de un entero y resolver una subclase de estos problemas de optimización. Con eso, el tiempo de cálculo ya no explotará a medida que aumenta el número de ciudades. Solo aumentará de forma polinómica, es decir, con Nx, donde x es una constante. De esta manera, la solución obtenida también es cualitativamente mucho mejor que la derivada de la solución aproximada usando el algoritmo convencional.

Al utilizar conceptos criptográficos y teoría del aprendizaje computacional, el estudio ofrece una “prueba totalmente constructiva de que los ordenadores cuánticos presentan una ventaja superpolinómica sobre los ordenadores clásicos al aproximar problemas de optimización combinatoria”. 

El estudio también señaló que el equipo de investigación ha avanzado significativamente en la importante cuestión de qué potencial pueden ofrecer los ordenadores cuánticos para aproximar la solución de problemas de optimización combinatoria, los cuales tienen impactos sociales y económicos sustanciales.

El estudio fue financiado por la Unidad de Investigación Einstein, el Centro de Investigación Matemática de Berlín (MATH+ Cluster of Excellence), el BMBF (Hybrid), el BMWK (EniQmA), el Munich Quantum Valley y la DFG. El Ministerio Federal de Educación e Investigación de Alemania también proporcionó apoyo financiero.

Explorando el Potencial de la Computación Cuántica 

Aunque es un gran logro, no fue la primera vez que la computación cuántica se utilizó para resolver el problema del viajante. Ha habido muchas instancias de entusiastas e investigadores que han buscado resolver el problema mediante la computación cuántica. 

En diciembre de 2022, un artículo propuso un algoritmo cuántico para el TSP basado en la Búsqueda Adaptativa de Grover (GAS). Dentro del marco de GAS, existen al menos dos dificultades fundamentales: las soluciones pueden no ser factibles, y el número de qubits de los ordenadores cuánticos actuales es muy limitado y no puede cumplir los requisitos mínimos, restringiendo la aplicación de algoritmos cuánticos para problemas de optimización combinatoria. 

Así, el artículo perfeccionó el oráculo de Detección de Ciclos Hamiltonianos (HCD), que puede eliminar automáticamente soluciones poco prácticas durante la ejecución del algoritmo. También diseñaron una estrategia de “registro ancla” para ahorrar el uso de qubits, considerando plenamente el requisito de reversibilidad de la computación cuántica y superando la dificultad de que los qubits utilizados no puedan simplemente sobrescribirse o liberarse. Esto permitió que el estudio requiriera solo 31 qubits, y la solución tuvo una tasa de éxito del 86,71 %.

En 2019, el aficionado a la física Joseph Cammidge escribió sobre el uso de un procesador cuántico de recocido, que le permitió resolver el problema del viajante para siete ciudades y tiene el potencial teórico de resolverlo para nueve ciudades una vez que se eliminen las limitaciones tecnológicas. 

Un nuevo método de cálculo, el recocido cuántico, ha demostrado el potencial de resolver problemas de optimización más rápido que las técnicas clásicas. Su teoría implica que los qubits alcanzarán un estado de energía baja óptimo cuando se enfríen a temperaturas extremadamente bajas. 

Sin embargo, en 2021, un estudio financiado por Supply Chain Digital & Data Science, Johnson & Johnson encontró que el recocedor cuántico solo puede manejar un tamaño de problema de 8 o menos nodos, y su rendimiento es inferior tanto en tiempo como en precisión comparado con el solucionador clásico.

El uso de la computación cuántica para resolver el problema del TSP lleva ya un tiempo. Hace más de dos décadas, en 2001, un estudio comenzó buscando un algoritmo cuántico para resolver el problema.

En el artículo, Buckley Hopper de la Universidad de Alabama analizó los algoritmos cuánticos de Grover y Shor. Señaló que el algoritmo de Grover solo ofrece una mejora de raíz cuadrada, lo que implica que no puede convertir un problema intratable clásicamente en uno tratable en un ordenador cuántico. En cuanto al algoritmo de Shor, Hopper observó que, aunque puede convertir un problema de factorización prima presumiblemente intratable en uno tratable en la máquina cuántica, solo es adecuado para un tipo de problema muy específico. 

En general, Hopper “no encontró un resultado satisfactorio para un algoritmo que compute soluciones aproximadas al problema del viajante”.

Unos años después, el Instituto de Ingenieros Eléctricos y Electrónicos (IEEE) presentó un nuevo algoritmo para resolver el problema, inspirado tanto en algoritmos genéticos como en la computación cuántica. El IEEE descubrió que los resultados de la aplicación del algoritmo propuesto en algunas instancias del Problema del Viajante son considerablemente mejores que los proporcionados por los algoritmos genéticos estándar.

Haga clic aquí para aprender sobre el estado actual de la computación cuántica.

Empresas que Trabajan con la Computación Cuántica 

Ahora, echemos un vistazo a un par de nombres que están trabajando en la investigación y desarrollo de la computación cuántica:

#1. IBM

International Business Machines Corporation está involucrada en una amplia gama de sectores, incluidos IA, servicios en la nube, TI, financiación de clientes y financiación comercial. El gigante tecnológico también participa en la computación cuántica a través de su IBM Quantum Platform, que brinda acceso público y premium a sus servicios de computación cuántica basados en la nube. Estos incluyen un conjunto de procesadores cuánticos prototipo de IBM, tutoriales sobre computación cuántica y un libro de texto interactivo.

Recientemente, científicos de IBM declararon que están un paso más cerca de superar un obstáculo que desbloquea el potencial revolucionario de los ordenadores cuánticos. Para ello, introdujeron un nuevo código de corrección de errores cuánticos, que, según dicen, es aproximadamente diez veces más eficiente que los métodos anteriores. 

A finales del año pasado, la compañía también lanzó el ordenador cuántico llamado Condor, con 1.121 qubits superconductores dispuestos en un patrón de panal. IBM también presentó IBM Quantum System Two, su primer ordenador cuántico modular y arquitectura de supercomputación centrada en lo cuántico, que es escalable y, por lo tanto, puede actualizarse con chips que se lanzarán en los próximos cinco años.

Con una capitalización de mercado de 175 mil millones de dólares, las acciones de IBM cotizan a 190,86 $, con un aumento del 16,66 % en lo que va del año (YTD). IBM ha registrado ingresos (TTM) de 61,86 mil millones de dólares, con un BPA (TTM) de 8,03, una relación P/E (TTM) de 23,76 y un ROE (TTM) de 33,36 %. La compañía paga un rendimiento de dividendo del 3,48 %.

#2. D-Wave Systems

Esta empresa de computación cuántica desarrolla y entrega sistemas, software y servicios relacionados. Sus productos incluyen The Leap y The Advantage, y ofrece aplicaciones cuánticas para programación, logística, descubrimiento de fármacos, procesos de fabricación y más. 

A principios de este mes, D‑Wave afirmó que las máquinas cuánticas ahora pueden resolver problemas con aplicaciones del mundo real más rápido que cualquier ordenador convencional. A principios de este año, la compañía anunció un ordenador cuántico con 1.200 qubits, 10.000 acopladores y un tiempo de solución 20 veces más rápido en problemas de optimización difíciles.

Las acciones de la compañía cotizan actualmente a 1,86 $, con un aumento del 138,6 % en lo que va del año (YTD), y una capitalización de mercado de 267 millones de dólares. Reportó ventas de 8,247 millones de dólares (TTM), un BPA (TTM) de -0,66 y una relación P/E (TTM) de -3,19, y anunció un crecimiento de más del 20 % en ventas tanto para su cuarto trimestre como para los resultados de fin de año 2023, mientras que las reservas aumentaron un 34 % y un 89 %, respectivamente. 

Curiosamente, el CEO de la compañía, el Dr. Alan Baratz, declaró el impulso de la empresa, citando la asociación estratégica plurianual con Zapata AI, la introducción del prototipo Advantage2 de más de 1.200 qubits, joint ventures con NEC Australia y Deloitte Canada, y el nombramiento de la exsecretaria de Seguridad Nacional Kirstjen Nielsen al consejo de administración.

Conclusión

El mercado de la computación cuántica se espera que alcance los 6,5 mil millones de dólares en 2028, y su potencial para resolver el Problema del Viajante (TSP) tiene repercusiones en varias industrias, como la manufactura, la logística, la gestión de la cadena de suministro, el comercio electrónico, el transporte y la investigación. Después de todo, puede generar beneficios sustanciales, notablemente al impulsar la productividad, reducir los gastos y fomentar la innovación en diversos sectores.

Haga clic aquí para la lista de las cinco mejores empresas de computación cuántica.