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:2106.09056 · Quantum Information Processing

Unconstrained binary models of the travelling salesman problem variants for quantum optimization

Özlem Salehi, Adam Glos, Jarosław Adam Miszczak

Published Jan 22, 2022• 65 citations
arXivHTMLPDF

Abstract

Abstract Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the travelling salesman problem with time windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher-order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world tasks which can be cast in the form of travelling salesman problem with time windows.

DOI
10.1007/s11128-021-03405-5

Related papers

A QUBO Model for the Traveling Salesman Problem with Time Windows

Christos Papalitsas, Theodore Andronikos, Konstantinos Giannakis +2 more

This work focuses on expressing the TSP with Time Windows (TSPTW for short) as a quadratic unconstrained binary optimization (QUBO) problem. The time windows impose time constraints that a feasible solution must satisfy. These take the form of inequality constraints, which are known to be particularly difficult to articulate within the QUBO framework. This is, we believe, the first time this major obstacle is overcome and the TSPTW is cast in the QUBO formulation. We have every reason to anticipate that this development will lead to the actual execution of small scale TSPTW instances on the D-Wave platform.

Algorithms•Oct 25, 2019•90 citations

Solving the Traveling Salesman Problem Using Quantum Devices: QUBO and HOBO Formulations

G. V. Shuvalov, E. N. Krivtsova, M. A. Remnev +1 more

Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.

Russian Microelectronics•Dec 1, 2025•0 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

Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler

Goldsmith, Daniel, Joe Day-Evans

The Travelling Salesman Problem (TSP) is an important combinatorial optimisation problem, and is usually solved on a quantum computer using a Quadratic Unconstrained Binary Optimisation (QUBO) formulation or a Higher Order Binary Optimisation(HOBO) formulation. In these formulations, penalty terms are added to the objective function for outputs that don't map to valid routes. We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes. Simulations of a quantum boson sampler were carried out which demonstrate that larger networks can be solved with this penalty-free formulation than with formulations with penalties. Simulations were successfully translated to hardware by running a non-QUBO formulation with penalties on an early experimental prototype ORCA PT-1 boson sampler. Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices. This work shows that a good embedding for combinatorial optimisation problems can solve larger problems with the same quantum computing resource. The flexibility of boson sampling quantum devices is a powerful asset in solving combinatorial optimisation problem, because it enables formulations where the output string is always mapped to a valid solution, avoiding the need for penalties.

arXiv:2406.14252•Jun 20, 2024•1 citation

Quantum approximation optimization algorithm for traveling salesman problem on 5-qubit IQM spark quantum computer

Igor Dudkiewicz, Wojciech Bożejko

In this paper, we consider a method for solving difficult combinatorial optimization problems on real quantum computers. We focus on the traveling salesman problem as a representative problem for a group of problems where the solution is represented by a permutation. Typically, existing algorithmic solutions use binary matrices to store this permutation – the QUBO (quadratic unconstrained binary optimization) model. We propose a new way of encoding permutations on quantum computers, using a significantly smaller number of qubits than binary matrix encodings. Our method allows for significant performance improvements for any problem whose input or solution is a permutation. We demonstrate an example implementation of the traveling salesman problem on the IQM quantum computers: IQM Spark 5-qubit ‘ODRA-5’ computer and IQM Radiance ‘Garnet’ 20-qubit computer.

Bulletin of the Polish Academy of Sciences Technical Sciences•Dec 11, 2025•2 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
Abstract Quantum computing is offering a novel perspective for solving combinatorial optimization problems. To fully explore the possibilities offered by quantum computers, the problems need to be formulated as unconstrained binary models, taking into account limitation and advantages of quantum devices. In this work, we provide a detailed analysis of the travelling salesman problem with time windows (TSPTW) in the context of solving it on a quantum computer. We introduce quadratic unconstrained binary optimization and higher-order binary optimization formulations of this problem. We demonstrate the advantages of edge-based and node-based formulations of the TSPTW problem. Additionally, we investigate the experimental realization of the presented methods on a quantum annealing device. The provided results pave the path for utilizing quantum computer for a variety of real-world tasks which can be cast in the form of travelling salesman problem with time windows.
This work focuses on expressing the TSP with Time Windows (TSPTW for short) as a quadratic unconstrained binary optimization (QUBO) problem. The time windows impose time constraints that a feasible solution must satisfy. These take the form of inequality constraints, which are known to be particularly difficult to articulate within the QUBO framework. This is, we believe, the first time this major obstacle is overcome and the TSPTW is cast in the QUBO formulation. We have every reason to anticipate that this development will lead to the actual execution of small scale TSPTW instances on the D-Wave platform.
Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.
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.
The Travelling Salesman Problem (TSP) is an important combinatorial optimisation problem, and is usually solved on a quantum computer using a Quadratic Unconstrained Binary Optimisation (QUBO) formulation or a Higher Order Binary Optimisation(HOBO) formulation. In these formulations, penalty terms are added to the objective function for outputs that don't map to valid routes. We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes. Simulations of a quantum boson sampler were carried out which demonstrate that larger networks can be solved with this penalty-free formulation than with formulations with penalties. Simulations were successfully translated to hardware by running a non-QUBO formulation with penalties on an early experimental prototype ORCA PT-1 boson sampler. Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices. This work shows that a good embedding for combinatorial optimisation problems can solve larger problems with the same quantum computing resource. The flexibility of boson sampling quantum devices is a powerful asset in solving combinatorial optimisation problem, because it enables formulations where the output string is always mapped to a valid solution, avoiding the need for penalties.
In this paper, we consider a method for solving difficult combinatorial optimization problems on real quantum computers. We focus on the traveling salesman problem as a representative problem for a group of problems where the solution is represented by a permutation. Typically, existing algorithmic solutions use binary matrices to store this permutation – the QUBO (quadratic unconstrained binary optimization) model. We propose a new way of encoding permutations on quantum computers, using a significantly smaller number of qubits than binary matrix encodings. Our method allows for significant performance improvements for any problem whose input or solution is a permutation. We demonstrate an example implementation of the traveling salesman problem on the IQM quantum computers: IQM Spark 5-qubit ‘ODRA-5’ computer and IQM Radiance ‘Garnet’ 20-qubit computer.
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.