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

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.

Presented at PEARC'26: "Practice and Experience in Advanced Research Computing", July 26-30, 2026. Minneapolis, MN, USA

Computational Complexity (cs.CC); Emerging Technologies (cs.ET); Quantum Physics (quant-ph)

arXiv:2607.24581 [cs.CC]

(or arXiv:2607.24581v1 [cs.CC] for this version)

https://doi.org/10.48550/arXiv.2607.24581 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

https://doi.org/10.1145/3785462.3815790 Focus to learn more DOI(s) linking to related resources

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.