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

Advances in systems analysis, software engineering, and high performance computing book series

A Secure Quantum Technology for Smart Cities Using Travelling Salesman Problem (TSP): Application Perspectives

A. Rehash Rushmi Pavitra, I. Daniel Lawrence, A. Muthukrishnan

Published Mar 3, 2023• 1 citation
Publisher

Abstract

Modern computing techniques like quantum computing are based on the remarkable phenomena of quantum mechanics. With an increasing number of instances of quantum supremacy displaying that a programmable quantum device can overcome the challenge that no computer algorithm can solve in any reasonable amount of time being shown by Google, IBM, Honeywell, and other distinct positions where quantum computing research is being conducted, quantum computing has grown in significance in recent days. Ultimately, travelling salesman problem (TSP) method is used and gives additional constraints on the beginning and ending points of the routing path. Hence, the outcome collections demonstrate that it is possible to obtain a strong quality result that has significant real-world applications even though the samples show an increase in problem complexity.

DOI
10.4018/978-1-6684-6697-1.ch009

Related papers

Quantum Computing for Optimizing Routes in Smart Cities

André Filipe de Soveral Torres Lopes dos Santos

In recent years, Quantum Computing has been gaining increasing importance as more and more examples of Quantum Supremacy (demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time) has been demonstrated by Google, Honeywell and other places where quantum computing research is underway.The potential of Quantum Computing is explored to address computational issues within the smart cities domain.Focusing in its application on the routing of garbage trucks.The garbage truck routing issue was studied and a simplified model of route planning was considered.A modified "Travelling Salesman Problem" (TSP) algorithm was applied, with added restrictions concerning the start and the end of the route.A few graphs from a TSP database were used.With each graph, the problem was formulated as a QUBO, and using a solver (Qbsolv), it was solved both by a classical computer (Laptop) and a Quantum Computer (Dwave Advantage System).Due to the limitation on time with the Dwave Quantum Computer, there was a limit to how many experiments that were possible to run on it.The samples show that as the complexity of the problem increases, so does its deviation from the "optimal result", but nonetheless the results obtained show that it is possible to obtain a "good enough" result that has practical real world applications.

•Jul 21, 2021•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•113 citations

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

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

Variational Quantum Approach for the Multiple Traveling Salesman Problem Optimisation

Yannis Spyridis, Athanasios Gkelias, Vasileios Argyriou

The Multiple Traveling Salesman Problem (m-TSP) is a well-known combinatorial optimisation problem with diverse applications in various fields, including transportation, logistics, and network design. The m-TSP involves finding the optimal routes for multiple salesmen to visit a set of cities, minimising the total travel distance while ensuring that each city is visited exactly once. Traditional computational approaches struggle to efficiently solve large-scale instances of the m-TSP due to its inherent complexity. In recent years, quantum computing has emerged as a promising field for tackling combinatorial optimisation problems. In this study, we investigate the application of the Quantum Approximate Optimisation Algorithm (QAOA) to solve the m-TSP, leveraging the inherent parallelism and quantum computational power to potentially obtain high-quality solutions.

International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT)•Jun 1, 2023•7 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
Modern computing techniques like quantum computing are based on the remarkable phenomena of quantum mechanics. With an increasing number of instances of quantum supremacy displaying that a programmable quantum device can overcome the challenge that no computer algorithm can solve in any reasonable amount of time being shown by Google, IBM, Honeywell, and other distinct positions where quantum computing research is being conducted, quantum computing has grown in significance in recent days. Ultimately, travelling salesman problem (TSP) method is used and gives additional constraints on the beginning and ending points of the routing path. Hence, the outcome collections demonstrate that it is possible to obtain a strong quality result that has significant real-world applications even though the samples show an increase in problem complexity.
In recent years, Quantum Computing has been gaining increasing importance as more and more examples of Quantum Supremacy (demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time) has been demonstrated by Google, Honeywell and other places where quantum computing research is underway.The potential of Quantum Computing is explored to address computational issues within the smart cities domain.Focusing in its application on the routing of garbage trucks.The garbage truck routing issue was studied and a simplified model of route planning was considered.A modified "Travelling Salesman Problem" (TSP) algorithm was applied, with added restrictions concerning the start and the end of the route.A few graphs from a TSP database were used.With each graph, the problem was formulated as a QUBO, and using a solver (Qbsolv), it was solved both by a classical computer (Laptop) and a Quantum Computer (Dwave Advantage System).Due to the limitation on time with the Dwave Quantum Computer, there was a limit to how many experiments that were possible to run on it.The samples show that as the complexity of the problem increases, so does its deviation from the "optimal result", but nonetheless the results obtained show that it is possible to obtain a "good enough" result that has practical real world applications.
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.
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 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 Multiple Traveling Salesman Problem (m-TSP) is a well-known combinatorial optimisation problem with diverse applications in various fields, including transportation, logistics, and network design. The m-TSP involves finding the optimal routes for multiple salesmen to visit a set of cities, minimising the total travel distance while ensuring that each city is visited exactly once. Traditional computational approaches struggle to efficiently solve large-scale instances of the m-TSP due to its inherent complexity. In recent years, quantum computing has emerged as a promising field for tackling combinatorial optimisation problems. In this study, we investigate the application of the Quantum Approximate Optimisation Algorithm (QAOA) to solve the m-TSP, leveraging the inherent parallelism and quantum computational power to potentially obtain high-quality solutions.
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).