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:2309.16522 · IEEE Symposium Series on Computational Intelligence (SSCI)

Quantum hobbit routing: Annealer implementation of generalized Travelling Salesperson Problem

Iñigo Perez Delgado, Beatriz García Markaida, Aitor Moreno-Fernández-de-Leceta, Jon Ander Ochoa Uriarte

Published Dec 4, 2022• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/ssci51031.2022.10022127

Related papers

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

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

Quantum Annealing Implementation of Job-Shop Scheduling

Davide Venturelli, D. J. J. Marchand, Galo Rojo

A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.

arXiv:1506.08479•Jun 29, 2015•135 citations

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

Enhanced QUBO Formulations for The Flow Shop Scheduling Problem

Yousra Farhani, Malak Saiem, Taha Arbaoui +1 more

In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2024•4 citations

Solving the traveling salesman problem via different quantum computing architectures

Venkat Aneesh Padmasola, zhuangbin li, Rupak Chatterjee +1 more

In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.

arXiv:2502.17725•International Journal of Quantum Information•Oct 11, 2025•7 citations
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.
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 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.
A quantum annealing solver for the renowned job-shop scheduling problem (JSP) is presented in detail. After formulating the problem as a time-indexed quadratic unconstrained binary optimization problem, several pre-processing and graph embedding strategies are employed to compile optimally parametrized families of the JSP for scheduling instances of up to six jobs and six machines on the D-Wave Systems Vesuvius processor. Problem simplifications and partitioning algorithms, including variable pruning and running strategies that consider tailored binary searches, are discussed and the results from the processor are compared against state-of-the-art global-optimum solvers.
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.
In recent years, the Flow shop Scheduling Problem (FSP) has gained significant attention, prompting researchers to develop various methods, from conventional to hybrid optimization algorithms. Driven by the rapid growth of quantum computing capabilities, quantum approaches applied to optimization problems have attracted an increasing research effort. This work attempts to solve the permutation flow shop scheduling problem using quantum annealing by formulating the problem as a Quadratic Unconstrained Binary Optimization model (QUBO). Two QUBO formulations tailored to address the FSP are used. The first formulation is based on the position-based modelling while the second is based on five approximations of FSP as a Traveling Salesman Problem (TSP). The QUBO formulations are tested, using D-Wave's quantum annealers, on the well-known Taillard FSP benchmark and compared against each other. Results show that the proposed position-based QUBO reaches better solutions than the TSP-based QUBOs. This work is an attempt to highlight the increasing effectiveness of quantum annealers in addressing complex optimization problems and their limitations compared to conventional classical methods.
In this paper, we study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of six nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.