Análisis comparativo de QAOA mediante la formulación Tensor QUDO para una variante del TSP aplicable a motores de búsqueda de viajes

Resumen

El Problema del Viajante de Comercio (TSP por sus siglas en inglés) constituye un problema de optimización combinatoria fundamental con amplias aplicaciones en logística, diseño de transporte y planificación de la producción. Sin embargo, los mejores algoritmos clásicos exactos conocidos presentan complejidad temporal exponencial, lo que vuelve intratables en la práctica a las instancias de gran tamaño y motiva la exploración de paradigmas alternativos como la computación cuántica. En este trabajo, implementamos la formulación QUBO y su generalización, Tensor Quadratic Unconstrained D-ary Optimisation (T-QUDO), que extiende la codificación en circuitos cuánticos de qubits a qudits, para una variante del TSP. Esta variante busca determinar una ruta de costo mínimo incorporando funciones de costo dependientes del tiempo y restricciones de precedencia, y permanece en gran medida inexplorada con T-QUDO a pesar de su relevancia en la planificación dinámica de viajes. Las formulaciones se codifican dentro del algoritmo QAOA y se analizan mediante simulaciones sin ruido utilizando las librerías Cirq y CUDA-Q, con el objetivo de evaluar las posibles ventajas de las representaciones basadas en qudits frente a las basadas en qubits, particularmente en términos de expresividad, eficiencia de recursos y calidad de solución.