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

arXiv:1612.06203 · Physical Review A

Quantum speedup of the traveling-salesman problem for bounded-degree graphs

Dominic J. Moylett, Noah Linden, Ashley Montanaro

Published Mar 22, 2017• 43 citations
arXivHTMLPDF

Abstract

The traveling-salesman problem is an iconic route-finding task, with applications from chip design to planning and logistics. Here the authors show that if the graph of cities to be visited is of low degree, a traveling salesman armed with a quantum satnav can find the best route quadratically faster than using any known classical method.

DOI
10.1103/physreva.95.032323

Related papers

An Efficient Quantum Algorithm for the Traveling Salesman Problem

Anant Sharma, Nupur Deshpande, Sanchita Purohit Ghosh +2 more

Abstract The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be N P -hard with a brute-force complexity of O ( N N ) or O ( N 2 N ) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O ( N N /2 ) or O ( N N ). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O ( N 3 log( N ) κ / ϵ + 1/ ϵ 3 ), where the errors ϵ are O (1/poly( N )), and κ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.

Quantum Information and Computation•Feb 22, 2025•1 citation

Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs

Dom J Moylett, Noah Linden, Ashley Montanaro

The Travelling Salesman Problem is one of the most famous problems in graph theory. However, little is currently known about the extent to which quantum computers could speed up algorithms for the problem. In this paper, we prove a quadratic quantum speedup when the degree of each vertex is at most 3 by applying a quantum backtracking algorithm to a classical algorithm by Xiao and Nagamochi. We then use similar techniques to accelerate a classical algorithm for when the degree of each vertex is at most 4, before speeding up higher-degree graphs via reductions to these instances.

•Apr 4, 2017•4 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

Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience

Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera +1 more

The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.

arXiv:1805.10928•May 28, 2018•62 citations

Quantum Algorithm for the Traveling Salesperson Problem

Andrew Haverly, M. A. Novotny, Shahram Rahimi

The traveling salesperson problem (TSP) is “if a traveling salesman wishes to visit exactly once each of a list of$m$cities (where the cost of traveling from city$i$to city$j$is$c_{ij}$) and then return to the home city, what is the least costly route the traveling salesman can take [1]?” The TSP is an NP-Complete problem. This paper introduces a solution to the TSP using Grover's quantum algorithm. This paper also introduces a quantum algorithm to the minimum (and maximum) spanning tree problem. The full circuit implementation is presented using the open-source Qiskit environment [2]. This paper provides the number of qubits required, the quantum depth, and the quantum volume of the algorithm for the TSP. This paper also shows how to solve the minimum (and maximum) spanning tree using Grover's algorithm.

IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)•Dec 4, 2023•1 citation

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

Krit Grover, Marcelo Ponce

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.

cs.CCCross-listedarXiv:2607.24581•Practice and Experience in Advanced Research Computing•Jul 28, 2026•0 citations
The traveling-salesman problem is an iconic route-finding task, with applications from chip design to planning and logistics. Here the authors show that if the graph of cities to be visited is of low degree, a traveling salesman armed with a quantum satnav can find the best route quadratically faster than using any known classical method.
Abstract The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be N P -hard with a brute-force complexity of O ( N N ) or O ( N 2 N ) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O ( N N /2 ) or O ( N N ). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O ( N 3 log( N ) κ / ϵ + 1/ ϵ 3 ), where the errors ϵ are O (1/poly( N )), and κ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.
The Travelling Salesman Problem is one of the most famous problems in graph theory. However, little is currently known about the extent to which quantum computers could speed up algorithms for the problem. In this paper, we prove a quadratic quantum speedup when the degree of each vertex is at most 3 by applying a quantum backtracking algorithm to a classical algorithm by Xiao and Nagamochi. We then use similar techniques to accelerate a classical algorithm for when the degree of each vertex is at most 4, before speeding up higher-degree graphs via reductions to these instances.
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 famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.
The traveling salesperson problem (TSP) is “if a traveling salesman wishes to visit exactly once each of a list ofmmmcities (where the cost of traveling from cityiiito cityjjjiscijc_{ij}cij​) and then return to the home city, what is the least costly route the traveling salesman can take [1]?” The TSP is an NP-Complete problem. This paper introduces a solution to the TSP using Grover's quantum algorithm. This paper also introduces a quantum algorithm to the minimum (and maximum) spanning tree problem. The full circuit implementation is presented using the open-source Qiskit environment [2]. This paper provides the number of qubits required, the quantum depth, and the quantum volume of the algorithm for the TSP. This paper also shows how to solve the minimum (and maximum) spanning tree using Grover's algorithm.
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.