Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Journal on Applied Physics and Engineering

Framework for Small Traveling Salesman Problems

Richard H. Warren

Published Nov 12, 2024• 1 citation
Publisher

Abstract

We study small traveling salesman problems (TSPs) because current quantum computers can find optional solutions for TSPs with up to 14 cities. Also, we study small TSPs because TSPs have been recommended to be benchmarks to measure quantum optimization on all types of quantum hardware. This means comparisons of quantum data about small TSPs. We extent previous numerical results that were reported in “Small Traveling Salesman Problems” for 6, 8 and 10 cities. The new results in this paper are for 10 – 14 cities in symmetric TSPs. The data for this new range of cities is consistent with the previous data and can be the basis for estimates of results from quantum computers that are upgraded to handle more than 14 cities. The work and analysis suggest two conjectures that we discuss. The paper also contains an annotated survey of recent publications about TSPs.

DOI
10.37394/232030.2024.3.7

Related papers

Small Traveling Salesman Problems

Richard H. Warren

This paper illustrates fundamental principles about small traveling salesman problems (TSPs) which are a current application for quantum annealing computers.The 2048 qubit, quantum annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8 cities, which advances a recent 4-city result on a quantum simulator.Additionally, the D-Wave quantum computer is expected to find all optimal tours for each TSP.To prepare for this, we show the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities.The examples in the TSPLIB have 14 or more cities.These are too large for the current quantum annealing processors.We have included an annotated bibliography about solving the TSP on a quantum computer.

Journal of Advances in Applied Mathematics•Apr 12, 2017•13 citations

Benchmarking Quantum Optimization by Traveling Salesman Problems

Richard H. Warren

This paper recommends symmetric traveling salesman problems (TSPs) be used to benchmark quantum capability to find optimal solutions for combinatorial optimization problems. We add four features to the existing list of reasons supporting this recommendation. We discuss benchmark measures and how to overcome the lack of small TSP examples for standards. Significate open questions are identified. We comment about published articles related to the benchmark theme.

International Journal on Applied Physics and Engineering•Dec 31, 2024•1 citation

Travelling Salesman Problem in the Classical to Quantum Era: A Comparative Review of Algorithms and Computational Complexity

Istiyak Amin Santo, Siow Chun Lim, Md Serajun Nabi +3 more

The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.

•Nov 12, 2025•1 citation

Quantum iterative approach to the Traveling Salesman Problem

Arturo Rodríguez-Almazán, Guillermo Rivas, Ricardo S. Alonso +2 more

The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of $O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})$ which depends on the error tolerance parameter $ε$. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.

quant-pharXiv:2606.11843•Physica Scripta•Jun 11, 2026•0 citations

A benchmark for quantum optimization: the traveling salesman

Richard H. Warren

We present compelling reasons for symmetric traveling salesman problems (TSPs) to be the benchmark for quantum computing of combinatorial optimization problems for all types of quantum hardware. There are seven reasons for endorsing these TSPs to be the benchmark and no shortcomings.

Quantum Information and Computation•Apr 27, 2021•8 citations

Comparative study on the variations of quantum approximate optimization algorithms to the Traveling Salesman Problem

Wenyang Qian, Robert Basili, Mary Mehrnoosh Eshaghian‐Wilner +3 more

The Traveling Salesman Problem (TSP) is one of the most often-used NP-Hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also being used heavily as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this work, we formulate the symmetric TSP as an optimization problem, which we solve using the quantum approximate optimization algorithm (QAOA) approach. By adopting an improved qubit encoding strategy and a layerwise learning optimization protocol, we obtain numerical results on the gate-based digital quantum simulator for the 3-, 4-, and 5-city TSPs. Specifically, we focus on three QAOA mixer designs to evaluate their performances in terms of numerical accuracy and optimization cost. Based on our results, we propose that a well-balanced QAOA mixer design is more prominent on gate-based simulators or realistic quantum devices in the near future. In addition, we study the sensitivity of TSP graph properties such as graph skewness and penalty weight in the TSP-QAOA simulation. Overall, our results prove digital quantum simulation is a powerful candidate for obtaining the optimal solution to the TSP.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2023•3 citations
We study small traveling salesman problems (TSPs) because current quantum computers can find optional solutions for TSPs with up to 14 cities. Also, we study small TSPs because TSPs have been recommended to be benchmarks to measure quantum optimization on all types of quantum hardware. This means comparisons of quantum data about small TSPs. We extent previous numerical results that were reported in “Small Traveling Salesman Problems” for 6, 8 and 10 cities. The new results in this paper are for 10 – 14 cities in symmetric TSPs. The data for this new range of cities is consistent with the previous data and can be the basis for estimates of results from quantum computers that are upgraded to handle more than 14 cities. The work and analysis suggest two conjectures that we discuss. The paper also contains an annotated survey of recent publications about TSPs.
This paper illustrates fundamental principles about small traveling salesman problems (TSPs) which are a current application for quantum annealing computers.The 2048 qubit, quantum annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8 cities, which advances a recent 4-city result on a quantum simulator.Additionally, the D-Wave quantum computer is expected to find all optimal tours for each TSP.To prepare for this, we show the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities.The examples in the TSPLIB have 14 or more cities.These are too large for the current quantum annealing processors.We have included an annotated bibliography about solving the TSP on a quantum computer.
The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.
The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of O(m2log⁡2(m)log⁡2(1/ε)ε)O(\frac{m^2\log_2(m)\log_2(1/ε)}{\sqrtε})O(ε​m2log2​(m)log2​(1/ε)​) which depends on the error tolerance parameter εεε. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
The Traveling Salesman Problem (TSP) is one of the most often-used NP-Hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also being used heavily as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this work, we formulate the symmetric TSP as an optimization problem, which we solve using the quantum approximate optimization algorithm (QAOA) approach. By adopting an improved qubit encoding strategy and a layerwise learning optimization protocol, we obtain numerical results on the gate-based digital quantum simulator for the 3-, 4-, and 5-city TSPs. Specifically, we focus on three QAOA mixer designs to evaluate their performances in terms of numerical accuracy and optimization cost. Based on our results, we propose that a well-balanced QAOA mixer design is more prominent on gate-based simulators or realistic quantum devices in the near future. In addition, we study the sensitivity of TSP graph properties such as graph skewness and penalty weight in the TSP-QAOA simulation. Overall, our results prove digital quantum simulation is a powerful candidate for obtaining the optimal solution to the TSP.