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 of Engineering Research and

Travelling Salesperson Problem with Quantum Computing

Bhanu Lalith Aakash Medury, Vyoma Harshitha Podapati

Published Mar 12, 2020• 1 citation
Publisher

Abstract

Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.

DOI
10.17577/ijertv9is030107

Related papers

Efficient Encoding of the Traveling Salesperson Problem on a Quantum Computer

John Stenger, Sean Crowe, Joseph Diaz +3 more

Abstract We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function. Our encoding requires a number of qubits which grows logarithmically with the number of cities. We propose to calculate the cost function classically based on the probability distribution extracted from measuring the quantum computer. This is in contrast from the typical method of evaluating the cost function by taking the expectation value of a quantum operator. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.

Quantum Reports•Jul 17, 2025•3 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

Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem

Christos Lytrosyngounis, Ioannis Lytrosyngounis

The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge with widespread applications in logistics, operations research, and network design. While classical algorithms effectively solve small to medium-sized instances, they struggle with scalability due to exponential complexity. In this work, we present a hybrid quantum-classical approach that leverages IBM's Qiskit Runtime to integrate quantum optimisation techniques with classical machine learning methods, specifically K-Means clustering and Random Forest classifiers. These machine learning components aid in problem decomposition and noise mitigation, improving the quality of quantum solutions. Experimental results for TSP instances ranging from 4 to 8 cities reveal that the quantum-only approach produces solutions up to 21.7% worse than the classical baseline, while the hybrid method reduces this cost increase to 11.3% for 8 cities. This demonstrates that hybrid approaches improve solution quality compared to purely quantum methods but remain suboptimal compared to classical solvers. Despite current hardware limitations, these results highlight the potential of quantum-enhanced methods for combinatorial optimisation, paving the way for future advancements in scalable quantum computing frameworks.

arXiv:2503.00219•Feb 28, 2025•1 citation

Quantum evolutionary algorithm for TSP combinatorial optimisation problem

Ma, Yijiang, Tan Chye Cheah

This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.

arXiv:2409.13788•Sep 20, 2024•0 citations

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
Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.
Abstract We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function. Our encoding requires a number of qubits which grows logarithmically with the number of cities. We propose to calculate the cost function classically based on the probability distribution extracted from measuring the quantum computer. This is in contrast from the typical method of evaluating the cost function by taking the expectation value of a quantum operator. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.
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.
The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge with widespread applications in logistics, operations research, and network design. While classical algorithms effectively solve small to medium-sized instances, they struggle with scalability due to exponential complexity. In this work, we present a hybrid quantum-classical approach that leverages IBM's Qiskit Runtime to integrate quantum optimisation techniques with classical machine learning methods, specifically K-Means clustering and Random Forest classifiers. These machine learning components aid in problem decomposition and noise mitigation, improving the quality of quantum solutions. Experimental results for TSP instances ranging from 4 to 8 cities reveal that the quantum-only approach produces solutions up to 21.7% worse than the classical baseline, while the hybrid method reduces this cost increase to 11.3% for 8 cities. This demonstrates that hybrid approaches improve solution quality compared to purely quantum methods but remain suboptimal compared to classical solvers. Despite current hardware limitations, these results highlight the potential of quantum-enhanced methods for combinatorial optimisation, paving the way for future advancements in scalable quantum computing frameworks.
This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.
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.