A Quantitative Framework for Comparing Classical and Quantum Algorithms for the Traveling Salesman Problem
2026-07-27 • Computational Complexity
Computational ComplexityEmerging Technologies
AI summaryⓘ
The authors studied four different ways to solve the Traveling Salesman Problem, a tough puzzle where you try to visit many places using the shortest route possible. They tried a simple method that checks every possible route, a faster method using tree structures, a technique inspired by cooling metals, and a quantum computing approach. They tested these methods on different sized problems to see how well and quickly each one works. The authors also created a free tool that others can use to try out and improve these methods.
Traveling Salesman ProblemNP-hardBrute-force enumerationMinimum spanning tree2-approximation algorithmSimulated annealingQuantum Approximate Optimization AlgorithmScalabilityOpen-source framework
Authors
Krit Grover, Marcelo Ponce
Abstract
The Traveling Salesman Problem is a classical NP-hard problem with significant implications in logistics, circuit design, and operations research. This paper presents a comparative study of four approaches to solving the Traveling Salesman Problem: brute-force enumeration, a 2-approximation algorithm using minimum spanning trees, simulated annealing, and the Quantum Approximate Optimization Algorithm. We implement each technique and evaluate them on graphs of varying sizes to analyze performance, solution quality, and scalability. In doing so, we have also developed an open-source framework that allows researchers and practitioners to explore, test and extend these methods.