A Quantum Encoding of Traveling Salesperson Tours via Route Generation, Cost Phases, and a Valid-Permutation

1. El Problema

El Problema del Viajante de Comercio (TSP) es un problema fundamental de optimización combinatoria. Dado un grafo ponderado de $n$ ciudades, el objetivo es encontrar un ciclo hamiltoniano (una ruta que visite cada ciudad exactamente una vez y regrese al inicio) con el costo mínimo posible.

• Desafío principal: El número de rutas válidas crece factorialmente con el número de ciudades ($n!$), lo que hace que la búsqueda exhaustiva clásica sea inviable para instancias grandes.
• Limitación de enfoques cuánticos existentes: Las codificaciones basadas en aristas (comunes en annealing cuántico y modelos QUBO) a menudo requieren muchos qubits o tienen dificultades para representar explícitamente la estructura de permutación. Además, la mayoría de los algoritmos cuánticos enfrentan el desafío de que la fracción de estados válidos en el espacio de búsqueda es exponencialmente pequeña.

2. Metodología

Los autores proponen una codificación basada en rutas dentro de un modelo de circuito cuántico, en lugar de codificar aristas. La metodología se divide en tres componentes principales:

A. Representación de la Ruta (Registro de Tiempo)

• Se fija una ciudad de inicio y fin (ciudad $n-1$).
• La ruta se representa como una secuencia ordenada de las $n-1$ ciudades restantes a lo largo de $T = n-1$ pasos de tiempo.
• Registro de Ruta: Se utiliza un registro cuántico de tamaño $T \times b$, donde $b = \lceil \log_2(n-1) \rceil$ es el número de qubits necesarios para codificar una etiqueta de ciudad.
• Superposición Inicial: Se aplica una puerta Hadamard a todos los qubits del registro de ruta para crear una superposición uniforme de todas las posibles secuencias de etiquetas (incluyendo rutas inválidas).

B. Oráculo de Validez (Valid-Permutation Oracle)

• Función: Distingue entre permutaciones válidas de las ciudades no iniciales y asignaciones inválidas (donde una ciudad se repite o falta).
• Mecanismo:
  1. Introduce qubits auxiliares para calcular la paridad de la aparición de cada etiqueta de ciudad a lo largo de la secuencia de tiempo.
  2. Una etiqueta es válida si aparece exactamente una vez (paridad impar).
  3. Utiliza puertas CnX (Toffoli multi-control) para verificar que todas las etiquetas tengan paridad impar y marcar un qubit de bandera (good) con el estado $|1\rangle$ si la ruta es una permutación válida.
• Complejidad: Requiere $O(n^2 \log n)$ puertas CX y T.

C. Oráculo de Costo (Cost Oracle)

• Función: Codifica el costo total de la ruta en la fase del estado cuántico.
• Mecanismo: Aplica rotaciones de fase controladas basadas en la longitud de la ruta $L(x) = C_{0,x_1} + \sum C_{x_t, x_{t+1}} + C_{x_T, 0}$.
• Implementación: Descompone el costo en tres partes: arista de salida, transiciones intermedias y arista de retorno.
• Complejidad: La implementación "naive" requiere $O(n^3)$ operaciones de fase controlada, resultando en $O(n^3 \log n)$ puertas CX y $O(n^3(\log n + \log(1/\epsilon)))$ puertas T.

3. Contribuciones Clave

1. Codificación Compacta: Presentan una representación explícita de la estructura de permutación utilizando $O(n \log n)$ qubits, evitando la redundancia de las codificaciones basadas en aristas.
2. Construcción de Circuitos Reversibles: Detallan la implementación de un oráculo de validez y un oráculo de costo que funcionan en superposición coherente, permitiendo que la información de factibilidad y costo esté incrustada directamente en el estado cuántico.
3. Análisis de Recursos: Proporcionan un desglose preciso de la profundidad del circuito y el conteo de puertas (CX y T), mostrando que la profundidad escala cuadráticamente ($O(n^2)$) debido a la ejecución paralela de pasos de tiempo disjuntos, aunque el conteo total de puertas es cúbico.
4. Marco para Amplificación: El estado preparado es compatible con técnicas de amplificación de amplitud (Grover) o filtrado espectral (QSVT), sirviendo como una línea base clara para futuras optimizaciones.

4. Resultados y Limitaciones

• Complejidad de Recursos:
  • Qubits: $O(n \log n)$.
  • Puertas CX: $O(n^3 \log n)$.
  • Profundidad del Circuito: $O(n^2 \log n)$.
• Limitación Fundamental (El cuello de botella):
  • Aunque el algoritmo cuántico puede procesar todas las rutas en superposición, la fracción de rutas válidas en el espacio total de búsqueda es extremadamente pequeña: $\frac{(n-1)!}{(n-1)^{n-1}} \sim \sqrt{2\pi(n-1)} e^{-(n-1)}$.
  • Consecuencia: Incluso al utilizar amplificación de amplitud (que ofrece una aceleración cuadrática), la complejidad total del algoritmo sigue siendo exponencial en $n$ debido a la necesidad de amplificar una fracción exponencialmente pequeña de estados válidos.
  • El oráculo de costo naive también introduce una alta complejidad de puertas ($O(n^3)$), lo que dificulta la implementación en hardware actual.

5. Significado e Implicaciones

• Valor Pedagógico y de Referencia: El artículo no afirma lograr una ventaja cuántica práctica inmediata (polinómica), sino que proporciona una línea base de codificación clara y concreta. Es útil para simular instancias pequeñas y entender cómo integrar la factibilidad y el costo en circuitos cuánticos.
• Dirección Futura:
  • Se sugiere que el enfoque actual es principalmente representacional.
  • El trabajo futuro debe centrarse en construir oráculos más eficientes (usando aritmética reversible o técnicas de block-encoding) para reducir la complejidad de puertas.
  • Explorar métodos espectrales (como QSVT) para sesgar el estado hacia rutas de bajo costo sin necesidad de una proyección explícita de factibilidad, o buscar codificaciones alternativas que aumenten la fracción de estados válidos.
• Disponibilidad: El código fuente y los datos están disponibles públicamente en GitHub para fomentar la reproducibilidad.

En resumen, el paper ofrece una construcción teórica sólida para codificar el TSP en un ordenador cuántico, destacando la viabilidad de la representación basada en tiempo, pero advirtiendo honestamente sobre las barreras de escalabilidad actuales debido a la densidad exponencialmente baja de soluciones válidas.