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

Benchmarking Quantum Optimization by Traveling Salesman Problems

Richard H. Warren

Published Dec 31, 2024• 1 citation
Publisher

Abstract

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.

DOI
10.37394/232030.2024.3.14

Related papers

Framework for Small Traveling Salesman Problems

Richard H. Warren

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.

International Journal on Applied Physics and Engineering•Nov 12, 2024•1 citation

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

Designing Adiabatic Quantum Optimization: A Case Study for the Traveling Salesman Problem

Bettina Heim, Ethan Brown, Dave Wecker +1 more

With progress in quantum technology more sophisticated quantum annealing devices are becoming available. While they offer new possibilities for solving optimization problems, their true potential is still an open question. As the optimal design of adiabatic algorithms plays an important role in their assessment, we illustrate the aspects and challenges to consider when implementing optimization problems on quantum annealing hardware based on the example of the traveling salesman problem (TSP). We demonstrate that tunneling between local minima can be exponentially suppressed if the quantum dynamics are not carefully tailored to the problem. Furthermore we show that inequality constraints, in particular, present a major hurdle for the implementation on analog quantum annealers. We finally argue that programmable digital quantum annealers can overcome many of these obstacles and can - once large enough quantum computers exist - provide an interesting route to using quantum annealing on a large class of problems.

arXiv:1702.06248•Feb 21, 2017•11 citations

Employing continuous quantum systems to solve optimization problems

Alexander Sauer, Sebastian Luhn, Jannes Weghake

At land, sea and in the air mobility and traffic management offer a vast amount of problems with a large potential of optimization with quantum computers, e.g. service scheduling, route planning, or path optimization. Many of these problems can be described at a fundamental level by the traveling salesman problem (TSP), in which the shortest route while visiting each point exactly once is to be found [1]. The TSP has already received a lot of attention in the quantum computing community, for example, implementations for adiabatic quantum annealers exist and have been tested [2,3]. We investigate the TSP with a focus on going beyond qubits by employing continuous quantum systems. Using bosonic Qiskit we simulate potential algorithms for solving the TSP and compare their performance. [1] Flood, M. M., The traveling-salesman problem. Operations research, 4(1), 61-75, (1956). [2] Martoňák, Roman, Giuseppe E. Santoro, and Erio Tosatti., Quantum annealing of the traveling-salesman problem. Physical Review E 70.5: 057701, (2004). [3] Jain, S., Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics, 646, (2021).

•Mar 13, 2024•0 citations

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 approaches to the traveling salesman problem: A critical review of formulations, complexity, and implementation limits

Florian Klug

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.

Physica A Statistical Mechanics and its Applications•May 12, 2026•1 citation
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.
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.
With progress in quantum technology more sophisticated quantum annealing devices are becoming available. While they offer new possibilities for solving optimization problems, their true potential is still an open question. As the optimal design of adiabatic algorithms plays an important role in their assessment, we illustrate the aspects and challenges to consider when implementing optimization problems on quantum annealing hardware based on the example of the traveling salesman problem (TSP). We demonstrate that tunneling between local minima can be exponentially suppressed if the quantum dynamics are not carefully tailored to the problem. Furthermore we show that inequality constraints, in particular, present a major hurdle for the implementation on analog quantum annealers. We finally argue that programmable digital quantum annealers can overcome many of these obstacles and can - once large enough quantum computers exist - provide an interesting route to using quantum annealing on a large class of problems.
At land, sea and in the air mobility and traffic management offer a vast amount of problems with a large potential of optimization with quantum computers, e.g. service scheduling, route planning, or path optimization. Many of these problems can be described at a fundamental level by the traveling salesman problem (TSP), in which the shortest route while visiting each point exactly once is to be found [1]. The TSP has already received a lot of attention in the quantum computing community, for example, implementations for adiabatic quantum annealers exist and have been tested [2,3]. We investigate the TSP with a focus on going beyond qubits by employing continuous quantum systems. Using bosonic Qiskit we simulate potential algorithms for solving the TSP and compare their performance. [1] Flood, M. M., The traveling-salesman problem. Operations research, 4(1), 61-75, (1956). [2] Martoňák, Roman, Giuseppe E. Santoro, and Erio Tosatti., Quantum annealing of the traveling-salesman problem. Physical Review E 70.5: 057701, (2004). [3] Jain, S., Solving the traveling salesman problem on the d-wave quantum computer. Frontiers in Physics, 646, (2021).
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) 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.