Quantum approaches to the traveling salesman problem: A critical review of formulations, complexity, and implementation limits
Florian Klug · Physica A Statistical Mechanics and its Applications · 2026
The Traveling Salesman Problem (TSP) serves as a standard benchmark for assessing potential quantum advantage in combinatorial optimization. This paper provides a critical comparative analysis of quantum annealing, gate-based approaches based on quantum phase estimation, and hybrid quantum–classical dynamic programming methods within a unified complexity and implementation framework. While theoretical results indicate reductions of the classical O ( 2 n ) scaling to approximately O ( 1.728 n ) for general instances and to O ( 1.110 n ) for structured cases, these improvements remain largely asymptotic. In practice, all current quantum approaches are strongly constrained by hardware limitations. Quantum annealing suffers from embedding overhead and noise, hybrid methods rely extensively on classical decomposition without guaranteed optimality, and gate-based implementations are limited by circuit depth and error accumulation. As a result, no clear quantum advantage over classical algorithms has been demonstrated at practically relevant problem scales. By systematically separating intrinsic algorithmic scaling from hardware-induced resource constraints, this work clarifies the origin of the gap between theoretical quantum speedups and experimental performance, providing a critical assessment of the current status and realistic prospects of quantum TSP methods.