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:2605.09616 · Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

A Hybrid Classical-Quantum Annealing Algorithm for the TSP

Siwei Hu, Victor Lopata, Salvatore Sinno, Shruthi Thuravakkath, Paolo Zuliani

quant-phcs.ETSubmitted May 10, 2026• Announced May 12, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

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

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

Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero

The Traveling Salesman Problem is a classical NP-hard combinatorial optimization problem that has been extensively studied in operations research. A major challenge in Traveling Salesman Problem formulations is the large number of subtour elimination constraints required to ensure a valid tour. To address this issue, we adopt an iterative approach grounded in well-established operations research techniques, in which subtour elimination constraints are generated dynamically. In addition, we integrate a preprocessing phase to reduce the number of candidate arcs. In this work, we investigate both classical and quantum optimization approaches for solving the problem using the proposed framework. In particular, for quantum optimization we analyze quantum annealing techniques within the D-Wave framework, considering both direct quantum execution on the QPU and hybrid quantum classical solvers. Computational experiments show that the proposed strategies significantly reduce the model size and lead to positive improvements in computational performance across classical, direct quantum, and hybrid optimization approaches.

quant-pharXiv:2604.20321•Apr 23, 2026•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

Quantum hobbit routing: Annealer implementation of generalized Travelling Salesperson Problem

Iñigo Perez Delgado, Beatriz García Markaida, Aitor Moreno-Fernández-de-Leceta +1 more

In this paper, we present an implementation of a Job Selection Problem (JSP) — a generalization of the well-known Travelling Salesperson Problem (TSP)— of$N=9$jobs on its Quadratic Unconstrained Binary Optimization (QUBO) form, using$\mathrm{O}(N)$qubits on DWave's Advantage_system4.1 quantum annealing device. The best known quantum algorithm for TSP to date uses$\mathcal{O}(N^{2})$qubits. A solution is found using the quantum method. However, since hardware is not yet able to compensate the increase in search-space size, no present overall advantage is achieved when comparing the quantum results with either exhaustive or equiprobably sampled classical solutions of the problem.

arXiv:2309.16522•IEEE Symposium Series on Computational Intelligence (SSCI)•Dec 4, 2022•3 citations

Solving the Traveling Salesman Problem on the D-Wave Quantum Computer

Siddharth Jain

The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.

Frontiers in Physics•Nov 12, 2021•50 citations
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.
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.
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 is a classical NP-hard combinatorial optimization problem that has been extensively studied in operations research. A major challenge in Traveling Salesman Problem formulations is the large number of subtour elimination constraints required to ensure a valid tour. To address this issue, we adopt an iterative approach grounded in well-established operations research techniques, in which subtour elimination constraints are generated dynamically. In addition, we integrate a preprocessing phase to reduce the number of candidate arcs. In this work, we investigate both classical and quantum optimization approaches for solving the problem using the proposed framework. In particular, for quantum optimization we analyze quantum annealing techniques within the D-Wave framework, considering both direct quantum execution on the QPU and hybrid quantum classical solvers. Computational experiments show that the proposed strategies significantly reduce the model size and lead to positive improvements in computational performance across classical, direct quantum, and hybrid optimization approaches.
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
In this paper, we present an implementation of a Job Selection Problem (JSP) — a generalization of the well-known Travelling Salesperson Problem (TSP)— ofN=9N=9N=9jobs on its Quadratic Unconstrained Binary Optimization (QUBO) form, usingO(N)\mathrm{O}(N)O(N)qubits on DWave's Advantage_system4.1 quantum annealing device. The best known quantum algorithm for TSP to date usesO(N2)\mathcal{O}(N^{2})O(N2)qubits. A solution is found using the quantum method. However, since hardware is not yet able to compensate the increase in search-space size, no present overall advantage is achieved when comparing the quantum results with either exhaustive or equiprobably sampled classical solutions of the problem.
The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.