⚛️ quantum physics

Solving The Travelling Salesman Problem Using A Single Qubit

Este artículo presenta un algoritmo cuántico eficiente en recursos que resuelve el Problema del Viajante para hasta nueve ciudades utilizando un solo cúbit mediante el aprovechamiento del paralelismo cuántico y métodos de control óptimo basados en un enfoque de Braquistócrona cuántica, demostrando una precisión superior y un potencial de aceleración polinómica sobre los métodos cuánticos y clásicos existentes.

Autores originales: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Publicado 2026-01-28

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

El gran problema: El viajero cansado

Imagina que eres un vendedor ambulante con un mapa de ciudades. Tu trabajo es visitar cada ciudad exactamente una vez y regresar a casa, pero quieres hacerlo recorriendo la distancia más corta posible.

Este es el famoso Problema del Viajante (TSP, por sus siglas en inglés). Es un rompecabezas clásico que se vuelve increíblemente difícil muy rápido. Si tienes 4 ciudades, es fácil. Si tienes 10, es manejable. Pero si tienes 20, el número de rutas posibles es tan enorme que incluso las supercomputadoras más rápidas del mundo tardarían más que la edad del universo en revisarlas todas una por una.

La vieja forma cuántica: El enfoque de "demasiadas llaves"

Normalmente, cuando los científicos intentan resolver esto en una computadora cuántica, tratan el problema como una cerradura gigante con muchos cilindros. Necesitan un "cilindro" (un qubit) separado para cada ciudad y cada conexión posible.

El problema: Para resolver un problema de solo 9 o 10 ciudades, los métodos cuánticos existentes necesitan cientos o incluso miles de qubits.
La realidad: Las computadoras cuánticas actuales son ruidosas y frágiles. Les cuesta mantener ese número de qubits trabajando juntos y, a menudo, fallan al encontrar la respuesta perfecta, incluso para mapas pequeños.

La nueva idea: El qubit de "una sola maravilla"

Este artículo propone una nueva forma radical de resolver el TSP usando solo un único qubit (la unidad básica de información cuántica). Piensa en este único qubit no como un pequeño interruptor, sino como un trompo mágico que puede apuntar en cualquier dirección en un espacio 3D.

Así es como lo hacen funcionar, paso a paso:

1. El mapa es un globo (La esfera de Bloch)

En lugar de dibujar las ciudades en un papel plano, los autores las mapean sobre la superficie de una esfera (como un globo terráqueo).

Las ciudades: Las ciudades "reales" se colocan a lo largo del ecuador de este globo.
Las distancias: La distancia entre dos ciudades no se mide en millas, sino por cuánto tienes que hacer girar el trompo para ir de un punto de la ciudad a otro.
El objetivo: El vendedor necesita hacer girar el trompo de ciudad en ciudad, visitando cada punto del ecuador una vez y regresando a casa, minimizando el "esfuerzo de giro" total.

2. La superautopista de la superposición

En la forma antigua, revisas la Ruta A, luego la Ruta B, luego la Ruta C, una por una.
En este nuevo método, los autores utilizan la superposición cuántica. Imagina que el trompo es un viajero mágico que puede estar en múltiples lugares a la vez.

En lugar de caminar un solo camino, el "trompo" explora todas las rutas posibles simultáneamente.
Es como enviar a mil exploradores por mil caminos diferentes al mismo tiempo, pero todos son el mismo explorador, simplemente existiendo en una "superposición" de todos los caminos.

3. El atajo de la "Brachistocrona"

El artículo utiliza un concepto de la física llamado el problema de la Brachistocrona. Históricamente, este pregunta: "¿Cuál es la ruta más rápida para que una bola ruede entre dos puntos?".

Los autores convirtieron el TSP en una versión de este problema. Tratan la búsqueda de la ruta como una carrera contra el tiempo.
Utilizan una técnica llamada Control Óptimo (piensa en esto como un piloto automático muy inteligente) para empujar y rotar suavemente el qubit único.
El piloto automático ajusta el "giro" para que los caminos que son demasiado largos se cancelen entre sí (como los auriculares con cancelación de ruido), mientras que el camino más corto se amplifica y destaca.

4. La comprobación final

Después de que el qubit ha "viajado" por todas las rutas a la vez, los científicos miden la posición final del trompo.

No miran cada ruta individual. Miran el final del viaje.
Al analizar el estado final, pueden trabajar hacia atrás para reconstruir la ruta ganadora.
Es como observar a un mago realizar un truco donde baraja un mazo de cartas, y al mirar la última carta, puede decirte el orden exacto en que estaba todo el mazo.

Los resultados: ¿Qué encontraron?

El equipo realizó simulaciones por computadora para probar este método de "Un solo Qubit".

La prueba: Resolvieron acertijos de TSP con 4 a 9 ciudades.
El éxito: En más del 90% de los problemas, su método encontró la ruta perfecta y más corta.
El sistema de seguridad: En los casos raros en los que no obtuvieron la respuesta perfecta, aun así obtuvieron una aproximación muy buena (aproximadamente un 90% de tan buena como la mejor posible).
La eficiencia: Hicieron todo esto usando solo un qubit, mientras que otros métodos habrían necesitado docenas o cientos.

La conclusión fundamental

Este artículo no afirma que vaya a resolver el TSP para un millón de ciudades mañana. En cambio, demuestra un concepto poderoso: No necesitas una computadora cuántica masiva para resolver problemas de rutas complejas.

Al tratar el problema como un rompecabezas geométrico en una única esfera giratoria y utilizar el poder de "estar en muchos lugares a la vez", demostraron que un solo qubit puede navegar laberintos complejos de manera eficiente. Es una forma de optimización cuántica con menos recursos que eventualmente podría construirse en cualquier plataforma cuántica que pueda hacer girar un qubit con precisión.

Resumen Técnico: Resolución del Problema del Viajante mediante un Único Qubit

Planteamiento del Problema
El Problema del Viajante (TSP, por sus siglas en inglés) es un problema de optimización combinatoria fundamental de clase NP-duro que requiere la identificación de la ruta más corta posible que visite un conjunto de ciudades exactamente una vez y regrese al origen. Aunque existen algoritmos clásicos, las soluciones exactas escalan exponencialmente con el número de ciudades, y los métodos heurísticos no garantizan la optimalidad. Los enfoques cuánticos existentes, como aquellos que utilizan la Optimización Binaria No Restringida Cuadrática (QUBO) mapeada a Hamiltonianos de Ising o circuitos de estimación de fase, son intensivos en recursos. Típicamente requieren un gran número de qubits (por ejemplo, miles de qubits físicos para un problema de 10 ciudades) y a menudo sufren de bajas probabilidades de éxito en el hardware ruidoso actual.

Metodología
Los autores proponen un algoritmo que mapea un TSP arbitrario en un único qubit, aprovechando el principio de paralelismo cuántico en lugar del entrelazamiento. La metodología central involucra tres etapas principales:

Mapeo a un Problema de Brachistócrona Discreta:
El TSP se reformula primero como un problema de Brachistócrona discreta finita. En esta analogía clásica, las ciudades se representan como puntos en un plano 2D y las rutas son funciones lineales por partes. El objetivo es minimizar un funcional de tiempo $Q$ , que corresponde a la distancia total de viaje. El problema está restringido de tal manera que la trayectoria debe regresar a la ciudad inicial, codificada mediante un segmento lineal adicional hacia un punto final $F$ .
Codificación en la Esfera de Bloch:
El problema de la Brachistócrona discreta se mapea sobre la geometría de la esfera de Bloch de un único qubit.

Representación de Estados: Las ciudades ( $c_i$ ) se representan mediante estados cuánticos $|P_{ii}\rangle$ ubicados en el ecuador de la esfera de Bloch.
Codificación de Distancia: Las distancias relativas entre ciudades se codifican como distancias geométricas (geodésicas) en la esfera. Los estados intermedios $|P_{ij}\rangle$ se sitúan en curvas geodésicas que conectan los estados ecuatoriales con un polo $P_0$ . La distancia angular entre estados corresponde a la distancia euclidiana entre las ciudades.
Trayectoria: El movimiento entre ciudades se logra mediante operadores de rotación ( $U^u$ y $U^d$ ). Un "paso" de la ciudad $i$ a la ciudad $j$ implica una rotación "hacia arriba" desde el ecuador hacia un estado intermedio $|P_{ij}\rangle$ (más cercano al polo) seguida de una rotación "hacia abajo" al estado ecuatorial $|P_{jj}\rangle$ .

Optimización Cuántica mediante Superposición:
A diferencia de un enfoque de fuerza bruta que recorre las rutas secuencialmente, el algoritmo propuesto utiliza la superposición cuántica para recorrer múltiples rutas simultáneamente.

Creación de Superposición: El sistema se inicializa en un estado correspondiente a la ciudad de partida. Una serie de operadores de rotación ajustables crea un estado de superposición en cada capa del diagrama de rutas, explorando efectivamente todos los caminos válidos e inválidos a la vez.
Optimización: El algoritmo emplea métodos de control óptimo, específicamente la Aproximación Estocástica de Perturbación Simultánea (SPSA), para ajustar los operadores de rotación.
Función Objetivo: Mientras que un enfoque cuántico de fuerza bruta podría minimizar un funcional de tiempo $T$ , el enfoque basado en superposición minimiza la función de costo clásica $D$ (distancia total). Esto es necesario porque la superposición incluye rutas "clásicamente prohibidas" que no forman ciclos hamiltonianos válidos. La optimización busca maximizar la población del ciclo hamiltoniano válido en el estado final.
Medición y Post-procesamiento: El algoritmo concluye con una medición proyectiva del estado penúltimo. A través de la tomografía de estado cuántico, se analiza la distribución de población para identificar la ruta dominante, que corresponde a la ruta óptima del TSP.

Resultos Clave
Los autores presentan simulaciones numéricas resolviendo instancias de TSP con 4 a 9 ciudades utilizando un único qubit.

Precisión: Para los tamaños de problema probados, el algoritmo obtuvo soluciones exactas (razón de aproximación $\sim 1$ ) para más del 90% de las instancias del problema.
Aproximación: En los casos donde no se encontraron soluciones exactas, el algoritmo logró altas razones de aproximación ( $\sim 0.90$ ).
Eficiencia de Recursos: El método requiere solo un único qubit, lo que contrasta fuertemente con los algoritmos cuánticos existentes que requieren cientos o miles de qubits para problemas similares.
Agnosticismo de Plataforma: El algoritmo está diseñado para ser implementable en cualquier plataforma cuántica capaz de realizar rotaciones de qubit arbitrarias de alta fidelidad y tomografía de estado, incluyendo qubits superconductores, iones atrapados, centros nitrógeno-vacante y átomos de Rydberg.

Significancia y Reivindicaciones
El artículo afirma que este enfoque ofrece una alternativa más eficiente en recursos y más precisa que los algoritmos cuánticos existentes para instancias de TSP de pequeño a mediano tamaño. Al utilizar el principio de superposición en un único qubit, el método evita la necesidad de un gran entrelazamiento y de conteos extensos de qubits, abordando un cuello de botella primario en el hardware cuántico actual.

Los autores discuten una potencial aceleración de tiempo polinómica sobre los algoritmos clásicos, sugiriendo que el paralelismo cuántico inherente en la superposición de rutas podría proporcionar una ventaja práctica tanto en tiempo como en precisión. El trabajo posiciona al TSP no solo como un problema de enrutamiento, sino como un caso específico de un problema de Brachistócrona restringido resoluble mediante control cuántico, abriendo una vía para la optimización cuántica escalable en dispositivos de era NISQ (Near-term Intermediate-Scale Quantum).