A Quantitative Framework for Comparing Classical and Quantum Algorithms for the Traveling Salesman Problem

This paper investigates the practical performance and scalability of four distinct approaches to solving the Traveling Salesman Problem (TSP): brute-force enumeration, a 2-approximation algorithm using Minimum Spanning Trees (MST), simulated annealing (SA), and the Quantum Approximate Optimization Algorithm (QAOA). The authors developed an open-source framework to provide a unified, reproducible environment for comparing these methods across varying graph sizes, focusing on execution time, solution quality, and memory usage.

The authors implemented each solver with specific design choices to ensure fair comparison. The MST approach uses Prim’s algorithm for tree construction followed by a depth-first search traversal. The simulated annealing implementation incorporates multi-strategy initialization and topology-aware neighbor generation to improve convergence. For QAOA, the authors utilized an edge-based encoding scheme that guarantees feasibility by construction, avoiding the penalty terms often required in node-based formulations. The study highlights the engineering trade-offs between exact matrix exponentiation and Trotterized evolution within the PennyLane simulation framework.

The empirical results reveal a stark divide in scalability. Brute-force methods and QAOA are limited by factorial and exponential complexity, respectively. Specifically, QAOA suffers from a significant classical precomputation bottleneck—the need to enumerate all Hamiltonian cycles to construct the initial state and mixing Hamiltonian—which makes it intractable for even moderately sized graphs. In contrast, the MST approximation and simulated annealing demonstrate robust, polynomial-time scalability, remaining efficient even as the number of cities increases. The authors conclude that for current practical applications, classical heuristics remain far superior to near-term quantum approaches for the TSP.