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:2503.00219

Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem

Christos Lytrosyngounis, Ioannis Lytrosyngounis

Published Feb 28, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2503.00219

Related papers

Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability

F. Picariello, G. Turati, R. Antonelli +10 more

The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.

quant-pharXiv:2512.10813•Dec 12, 2025•0 citations

Solving larger Travelling Salesman Problem networks with a penalty-free Variational Quantum Algorithm

Daniel Goldsmith, Xing Liang, Dimitrios Makris +1 more

The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as $\mathcal{O}(nlog_2 n)$ qubits compared to conventional formulations with $\mathcal{O}(n^2)$ scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver

quant-pharXiv:2512.06523•Dec 9, 2025•0 citations

The travelling salesperson problem and the challenges of near-term quantum advantage

Kate Smith‐Miles, Holger H. Hoos, Hao Wang +2 more

Abstract Over the last two decades, the travelling salesperson problem (TSP) has been cited as a benchmark problem to demonstrate the advantage of quantum computers over conventional computers. Its advantage is that it is a well-studied NP-hard optimisation problem that can be easily communicated to highlight the challenges of searching through an exponentially growing number of possible solutions to find the optimal solution. It is therefore a tempting problem to choose to explore quantum advantage. At what point, however, is a call made that quantum advantage is not likely, and efforts should be focused on other problems? This article challenges the continued use of the TSP as a benchmark for quantum optimisation methods—such as quantum annealing and gate-based quantum computing—that require the TSP to be formulated as a quadratic unconstrained binary optimisation (QUBO) problem. We offer explanations for why such quantum approaches are not well suited, nor competitive against state-of-the-art classical methods, for tackling the challenges of the TSP landscape, and we draw parallels with similar observations made almost four decades ago when QUBO-based neural networks proved to be uncompetitive for solving the TSP. After critically reviewing two decades of research effort to solve TSPs using QUBO-based quantum methods, we note a gradual shift in focus: from initial attempts to solve small sized TSPs with general-purpose QUBO-based quantum approaches, to growing evidence that competitiveness is only enhanced where TSP domain knowledge is integrated, via either modified formulations or hybridisation with TSP classical heuristics. We discuss the numerous challenges that must be overcome before QUBO-based quantum optimisers could ever be competitive with classical state-of-the-art TSP solvers. Acknowledging that there may be more promise for non-QUBO-based hybrid approaches, where quantum search accelerates components of conventional algorithms, we offer recommendations for how future studies should be conducted to compare fairly and rigorously any proposed quantum methods against state-of-the-art TSP solvers, or any classical optimisation method, when seeking to establish quantum advantage.

Quantum Science and Technology•May 8, 2025•6 citations

Evolutionary Algorithm for the Traveling Salesman Problem With Innovative Encoding on Hybrid Quantum-Classical Machines

Ravi Saini, Ashish Mani, Mani Shankar Prasad +2 more

The Traveling Salesman Problem (TSP) is a widely studied NP-complete optimization challenge with significant theoretical and practical implications. This study proposes a hybrid quantum-classical framework using a Quantum-Inspired Evolutionary Algorithm (QEA) with Sort Gray Binary Encoding to solve the TSP. The proposed method guarantees the generation of valid TSP tours by eliminating invalid solutions. It employs quantum superposition with intrinsic randomness to enhance computational efficiency and scalability. The framework was implemented on cloud-based NISQ platforms, including IBM Quantum and AWS Braket, demonstrating its practicality and effectiveness. Experimental evaluations revealed that the proposed framework successfully solved TSP instances with up to 15 cities, achieving superior performance compared to classical methods and showcasing its ability to scale under NISQ constraints. The results also highlight the potential of hybrid quantum-classical approaches to overcome hardware limitations in current quantum systems. This study establishes a robust hybrid methodology for solving combinatorial optimization problems. It also sets a benchmark for leveraging the capabilities of NISQ-era quantum devices in real-world applications, thereby providing a foundation for future research in hybrid quantum-classical optimization techniques.

IEEE Access•Jan 1, 2025•4 citations

Quantum Self-Organizing Map for Solving the Euclidean Traveling Salesman Problem

Rui XU, Jean-Charles Créput

Hybrid quantum-classical algorithms are the subject of intensive research in quantum computing and specifically in the domains of Machine Learning and Approximate Optimization. Simple distance-based learning classifiers such as kNN or k-means classifiers have already been the subject of many proposals, but most of their quantum implementation only consider a very small number of classes/clusters and only use metrics suitable for normalized unit length quantum data. Very few approaches combine the need for Euclidean distance of unnormalized data with an efficient quantum computation implementation. Based on two kNN and k-means proposals from the literature, this paper proposes their adaptation to the design of a Quantum Self-Organizing Map in order to solve the NP-hard Traveling Salesman Optimization Problem (TSP) specifically. Hence, we evaluate the hybrid quantum-classical approach to Euclidean TSP instances of sizes from 52 to 127 cities and present the properties, advantages, and limitations of the quantum implementation in solving the TSP optimization problem.

International Conference on Control, Decision and Information Technologies (CoDIT)•Jul 15, 2025•1 citation

A Hybrid Classical-Quantum Annealing Algorithm for the TSP

Siwei Hu, Victor Lopata, Salvatore Sinno +2 more

Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer.

quant-pharXiv:2605.09616•Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•May 12, 2026•0 citations
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.
The Traveling Salesman Problem (TSP) is a fundamental challenge in combinatorial optimization, widely applied in logistics and transportation. As the size of TSP instances grows, traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes. This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method, to solve TSP under realistic constraints. We adopt a QUBO-based formulation of TSP that integrates real-world logistical constraints reflecting operational conditions, such as vehicle capacity, road accessibility, and time windows, while ensuring compatibility with the limitations of current quantum hardware. Our experiments are conducted in a simulated environment using high-performance computing (HPC) resources to assess QAOA's performance across different problem sizes and quantum circuit depths. In order to improve scalability, we propose clustering QAOA (Cl-QAOA), a hybrid approach combining classical machine learning with QAOA. This method decomposes large TSP instances into smaller sub-problems, making quantum optimization feasible even on devices with a limited number of qubits. The results offer a comprehensive evaluation of QAOA's strengths and limitations in solving constrained TSP scenarios. This study advances quantum optimization and lays groundwork for future large-scale applications.
The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as O(nlog2n)\mathcal{O}(nlog_2 n)O(nlog2​n) qubits compared to conventional formulations with O(n2)\mathcal{O}(n^2)O(n2) scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver
Abstract Over the last two decades, the travelling salesperson problem (TSP) has been cited as a benchmark problem to demonstrate the advantage of quantum computers over conventional computers. Its advantage is that it is a well-studied NP-hard optimisation problem that can be easily communicated to highlight the challenges of searching through an exponentially growing number of possible solutions to find the optimal solution. It is therefore a tempting problem to choose to explore quantum advantage. At what point, however, is a call made that quantum advantage is not likely, and efforts should be focused on other problems? This article challenges the continued use of the TSP as a benchmark for quantum optimisation methods—such as quantum annealing and gate-based quantum computing—that require the TSP to be formulated as a quadratic unconstrained binary optimisation (QUBO) problem. We offer explanations for why such quantum approaches are not well suited, nor competitive against state-of-the-art classical methods, for tackling the challenges of the TSP landscape, and we draw parallels with similar observations made almost four decades ago when QUBO-based neural networks proved to be uncompetitive for solving the TSP. After critically reviewing two decades of research effort to solve TSPs using QUBO-based quantum methods, we note a gradual shift in focus: from initial attempts to solve small sized TSPs with general-purpose QUBO-based quantum approaches, to growing evidence that competitiveness is only enhanced where TSP domain knowledge is integrated, via either modified formulations or hybridisation with TSP classical heuristics. We discuss the numerous challenges that must be overcome before QUBO-based quantum optimisers could ever be competitive with classical state-of-the-art TSP solvers. Acknowledging that there may be more promise for non-QUBO-based hybrid approaches, where quantum search accelerates components of conventional algorithms, we offer recommendations for how future studies should be conducted to compare fairly and rigorously any proposed quantum methods against state-of-the-art TSP solvers, or any classical optimisation method, when seeking to establish quantum advantage.
The Traveling Salesman Problem (TSP) is a widely studied NP-complete optimization challenge with significant theoretical and practical implications. This study proposes a hybrid quantum-classical framework using a Quantum-Inspired Evolutionary Algorithm (QEA) with Sort Gray Binary Encoding to solve the TSP. The proposed method guarantees the generation of valid TSP tours by eliminating invalid solutions. It employs quantum superposition with intrinsic randomness to enhance computational efficiency and scalability. The framework was implemented on cloud-based NISQ platforms, including IBM Quantum and AWS Braket, demonstrating its practicality and effectiveness. Experimental evaluations revealed that the proposed framework successfully solved TSP instances with up to 15 cities, achieving superior performance compared to classical methods and showcasing its ability to scale under NISQ constraints. The results also highlight the potential of hybrid quantum-classical approaches to overcome hardware limitations in current quantum systems. This study establishes a robust hybrid methodology for solving combinatorial optimization problems. It also sets a benchmark for leveraging the capabilities of NISQ-era quantum devices in real-world applications, thereby providing a foundation for future research in hybrid quantum-classical optimization techniques.
Hybrid quantum-classical algorithms are the subject of intensive research in quantum computing and specifically in the domains of Machine Learning and Approximate Optimization. Simple distance-based learning classifiers such as kNN or k-means classifiers have already been the subject of many proposals, but most of their quantum implementation only consider a very small number of classes/clusters and only use metrics suitable for normalized unit length quantum data. Very few approaches combine the need for Euclidean distance of unnormalized data with an efficient quantum computation implementation. Based on two kNN and k-means proposals from the literature, this paper proposes their adaptation to the design of a Quantum Self-Organizing Map in order to solve the NP-hard Traveling Salesman Optimization Problem (TSP) specifically. Hence, we evaluate the hybrid quantum-classical approach to Euclidean TSP instances of sizes from 52 to 127 cities and present the properties, advantages, and limitations of the quantum implementation in solving the TSP optimization problem.
Hybrid quantum-classical algorithms can help mitigating the physical limitations of current quantum devices, particularly the low qubit count and the reduced topological connectivity. In this paper, we propose a hybrid technique to solve a well-known NP-hard optimization problem: the Traveling Salesperson Problem (TSP). Our approach is based on a graph contraction technique that removes most of the dimensionality of the original problem instance, producing a sub-TSP of a size suitable to be efficiently solved by a quantum device. The performance of our approach is first demonstrated on classical quantum simulation using Path Integral Monte Carlo, and then run on a D-Wave quantum annealer.