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:1004.4124 · Journal of the Korean Physical Society

A quantum heuristic algorithm for the traveling salesman problem

Jeongho Bang, Junghee Ryu, Changhyoup Lee, Seokwon Yoo, James Lim, Jinhyoung Lee

Published Dec 1, 2012• 18 citations
arXivHTMLPDF

Abstract

We propose a quantum heuristic algorithm to solve the traveling salesman problem by generalizing the Grover search. Sufficient conditions are derived to greatly enhance the probability of finding the tours with the cheapest costs reaching almost to unity. These conditions are characterized by the statistical properties of tour costs and are shown to be automatically satisfied in the large-number limit of cities. In particular for a continuous distribution of the tours along the cost, we show that the quantum heuristic algorithm exhibits a quadratic speedup compared to its classical heuristic algorithm.

DOI
10.3938/jkps.61.1944

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

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

Embedding All Feasible Solutions of Traveling Salesman Problem by Divide-and-Conquer Quantum Search

Rei Sato, Kazuhiro Saito, Tetsuro Nikuni +1 more

Quantum search algorithms, such as the Grover algorithm, are investigated as one of the ways to solve a traveling salesman problem (TSP). In TSP, the quantum search starts from an equal superposition of all feasible solutions. The embedding cost of all feasible solutions is up to exponential, i.e.,$\mathcal{O}(n!)$with$n$cities, and makes it difficult to solve large-scale TSP. Hence, preparing the initial state of TSP at a lower embedding cost is an important issue. Here, we propose a quantum search algorithm based on the divide-and-conquer approach, which divides each constraint term of the TSP into subproblems and applies the quantum search to each subproblem. We investigate the embedding quality of all feasible solutions by comparing our proposed method with the Grover algorithm regarding optimal iterations and success probability. The results show that our quantum divide-and-conquer approach can significantly reduce the embedding cost while the success probability decreases.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•3 citations

Grover Adaptive Search with Problem-Specific State Preparation

Maximilian Hess, Lilly Palackal, Abhishek Awasthi +5 more

Grover's search algorithm is one of the basic building block in the world of quantum algorithms. Successfully applying it to combinatorial optimization problems is a subtle challenge. As a quadratic speedup is not enough to naively search an exponentially large space, the search has to be complemented with a state preparation routine which increases the amplitudes of promising states by exploiting the problem structure. In this paper, we build upon previous work by Baertschi and Eidenbenz to construct heuristic state preparation routines for the Traveling Salesperson Problem (TSP), mimicking the well-known classical Lin-Kernighan heuristic. With our heuristic, we aim to achieve a reasonable approximation ratio with only a polynomial number of Grover iterations. Further, we compare several algorithmic settings relating to termination criteria and the choice of Grover iterations when the number of marked solutions is unknown.

quant-pharXiv:2602.08418•Feb 10, 2026•0 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

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
We propose a quantum heuristic algorithm to solve the traveling salesman problem by generalizing the Grover search. Sufficient conditions are derived to greatly enhance the probability of finding the tours with the cheapest costs reaching almost to unity. These conditions are characterized by the statistical properties of tour costs and are shown to be automatically satisfied in the large-number limit of cities. In particular for a continuous distribution of the tours along the cost, we show that the quantum heuristic algorithm exhibits a quadratic speedup compared to its classical heuristic algorithm.
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 (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.
Quantum search algorithms, such as the Grover algorithm, are investigated as one of the ways to solve a traveling salesman problem (TSP). In TSP, the quantum search starts from an equal superposition of all feasible solutions. The embedding cost of all feasible solutions is up to exponential, i.e.,O(n!)\mathcal{O}(n!)O(n!)withnnncities, and makes it difficult to solve large-scale TSP. Hence, preparing the initial state of TSP at a lower embedding cost is an important issue. Here, we propose a quantum search algorithm based on the divide-and-conquer approach, which divides each constraint term of the TSP into subproblems and applies the quantum search to each subproblem. We investigate the embedding quality of all feasible solutions by comparing our proposed method with the Grover algorithm regarding optimal iterations and success probability. The results show that our quantum divide-and-conquer approach can significantly reduce the embedding cost while the success probability decreases.
Grover's search algorithm is one of the basic building block in the world of quantum algorithms. Successfully applying it to combinatorial optimization problems is a subtle challenge. As a quadratic speedup is not enough to naively search an exponentially large space, the search has to be complemented with a state preparation routine which increases the amplitudes of promising states by exploiting the problem structure. In this paper, we build upon previous work by Baertschi and Eidenbenz to construct heuristic state preparation routines for the Traveling Salesperson Problem (TSP), mimicking the well-known classical Lin-Kernighan heuristic. With our heuristic, we aim to achieve a reasonable approximation ratio with only a polynomial number of Grover iterations. Further, we compare several algorithmic settings relating to termination criteria and the choice of Grover iterations when the number of marked solutions is unknown.
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 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.