Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

Imagina a un repartidor que debe visitar una lista de ciudades exactamente una vez y regresar a casa, con el objetivo de recorrer la distancia más corta posible. Este es el problema del viajante, un rompecabezas clásico que se encuentra en el corazón de la logística, la programación y el diseño de circuitos. Si bien encontrar la ruta perfecta para unas pocas ciudades es fácil, la dificultad estalla a medida que la lista crece; por cada nueva ciudad añadida, el número de rutas posibles se multiplica tan rápidamente que incluso las supercomputadoras más rápidas pueden quedarse estancadas intentando encontrar la mejor. Durante décadas, los científicos han recurrido a las computadoras cuánticas, máquinas que utilizan las extrañas reglas de las partículas subatómicas para procesar información, para resolver estos acertijos. Sin embargo, un obstáculo importante ha persistido: cómo traducir el problema a un lenguaje que la computadora cuántica entienda sin ahogar el cálculo en errores y complejidad innecesaria.

Un investigador de QuantScape Inc. ha demostrado ahora una nueva forma de guiar a una computadora cuántica a través de este laberinto, encontrando con éxito la ruta más corta para mapas de hasta diez ciudades. El trabajo, que se basa en simulaciones de hardware cuántico en lugar de máquinas físicas, introduce un método que utiliza muchos menos bits cuánticos —las unidades básicas de información en una computadora cuántica— que los enfoques anteriores. Más importante aún, muestra que un único conjunto de instrucciones puede adaptarse a las condiciones cambiantes de la carretera, como el tráfico que varía a lo largo del día, sin necesidad de ser reentrenado para cada nuevo escenario. Los resultados sugieren que, con la codificación y las técnicas de entrenamiento adecuadas, las computadoras cuánticas podrían abordar pronto problemas de optimización que actualmente están fuera de su alcance, siempre que el hardware continúe mejorando.

El núcleo del desafío reside en cómo se escribe el problema para la máquina. Los métodos tradicionales asignan un bit cuántico separado a cada combinación posible de una ciudad y una posición en la ruta. Para un mapa de diez ciudades, este enfoque requiere ochenta y un bits, y obliga a la computadora a comprobar y descartar constantemente rutas inválidas, desperdiciando tiempo y energía en penalizaciones. El nuevo estudio utiliza una estrategia diferente, inspirada en un sistema matemático llamado código de Lehmer, que esencialmente clasifica cada ruta posible según su orden en una lista. Este método requiere solo diecinueve bits para diez ciudades, una reducción significativa. Al utilizar este código compacto, cada estado de la computadora cuántica representa una ruta válida, eliminando la necesidad de comprobaciones de penalización. Para que la búsqueda sea eficiente, los investigadores dispusieron estos estados de modo que cambiar un solo bit en el código correspondiera a un cambio pequeño y lógico en la ruta, permitiendo que la computadora explore el espacio de soluciones de manera fluida.

Para guiar a la computadora cuántica, los investigadores emplearon un sistema híbrido llamado red de Kolmogorov–Arnold variacional cuántica. Piense en esto como un controlador inteligente que observa el mapa y la hora del día, y luego ajusta los diales del circuito cuántico a las posiciones correctas. En lugar de codificar rígidamente los ajustes para cada mapa específico, este controlador aprende una regla general: cómo ajustar el circuito basándose en las distancias entre las ciudades y la hora actual. Esto permite al sistema manejar grafos dependientes del tiempo, donde los tiempos de viaje cambian, como una red eléctrica o una red de carreteras con tráfico de hora punta. El controlador fue entrenado con un objetivo específico: minimizar el riesgo de elegir una ruta larga. En lugar de buscar solo la longitud media absoluta, el entrenamiento se centró en los peores escenarios dentro de los pocos porcentajes superiores de los resultados probables, asegurando que el resultado final sea robusto y fiable.

El proceso de entrenamiento en sí fue riguroso, diseñado para evitar la trampa común de quedarse atrapado en un mínimo local, donde la computadora se conforma con una respuesta "suficientemente buena" en lugar de la mejor. Los investigadores utilizaron una estrategia de varios pasos que comenzaba con búsquedas amplias y se estrechaba gradualmente, combinada con una técnica que sacudía deliberadamente los ajustes para escapar de callejones sin salida. También utilizaron un método llamado salto de cuenca (basin hopping), que actúa como un suave temblor para ayudar al sistema a saltar fuera de valles poco profundos en el paisaje de búsqueda. Al ser probado en mapas de cuatro a diez ciudades, incluyendo tanto formas simétricas como redes aleatorias e irregulares, este enfoque encontró la ruta perfecta en todos los casos para los mapas más pequeños. Para los mapas de diez ciudades, que son significamente más difíciles, el método encontró la ruta óptima en 112 de 120 ensayos, siendo los fallos restantes de apenas un uno por ciento de la distancia perfecta.

Crucialmente, el estudio descartó varias ideas alternativas que podrían haber parecido prometedoras. Los investigadores probaron un enfoque más simple que utiliza solo diez bits, uno para cada ciudad, para rastrear la posición del conductor paso a paso. Este método falló completamente para mapas con seis o más ciudades porque no podía representar las relaciones complejas entre paradas sucesivas. También compararon sus resultados contra un algoritmo clásico estándar conocido como 2-opt, que mejora una ruta intercambiando dos segmentos. Aunque el 2-opt es efectivo, el circuito cuántico proporcionó un punto de partida mucho mejor, y la combinación de ambos superó a cualquiera de los métodos por sí solos. El estudio confirmó que el éxito provino de la forma específica en que se codificó el problema y del sofisticado entrenamiento del controlador, no solo del poder del propio circuito cuántico.

Los hallazgos también destacan la eficiencia del método con respecto a la medición. En una computadora cuántica real, leer la respuesta requiere repetir el proceso muchas veces para obtener una señal clara. Las simulaciones mostraron que incluso con tan solo cien lecturas, el sistema podía identificar de forma fiable la mejor ruta. Esto sugiere que, cuando las computadoras cuánticas físicas con suficientes bits estén disponibles, este método podría ofrecer resultados rápidamente sin necesidad de millones de repeticiones. Los investigadores señalaron que, aunque el presente trabajo se realizó en una computadora clásica simulando el comportamiento cuántico, las técnicas están diseñadas para funcionar en hardware real. Los siguientes pasos consisten en probar el sistema bajo las condiciones ruidosas de las máquinas reales y escalarlo a mapas más grandes donde el número de rutas posibles es demasiado vasto para ser verificado a mano.

Este trabajo representa un paso significativo hacia la practicidad de la optimización cuántica. Al resolver el problema de la codificación y crear un controlador que se generaliza a través de diferentes mapas y tiempos, los investigadores han mostrado un camino para que las máquinas resuelvan problemas de rutas complejos de manera eficiente. La capacidad de manejar cambios dependientes del tiempo con un único conjunto de parámetros es particularmente prometedora para aplicaciones del mundo real donde las condiciones nunca son estáticas. Aunque el viaje hacia un optimizador cuántico totalmente funcional está en curso, este estudio proporciona un plano claro de cómo entrenar a estas máquinas para encontrar el camino más corto a través de un mundo complejo.