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

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

Goldsmith, Daniel, Joe Day-Evans

Published Jun 20, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2406.14252

Related papers

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

Many-Qudit Representation for the Travelling Salesman Problem Optimisation

Vladimir Vargas-Calderón, Nicolas Parra-A., Herbert Vinck-Posada +1 more

We present a map from the travelling salesman problem (TSP), a prototypical NP-complete combinatorial optimisation task, to the ground state associated with a system of many-qudits. Conventionally, the TSP is cast into a quadratic unconstrained binary optimisation (QUBO) problem, that can be solved on an Ising machine. The size of the corresponding physical system's Hilbert space is $2^{N^2}$, where $N$ is the number of cities considered in the TSP. Our proposal provides a many-qudit system with a Hilbert space of dimension $2^{N\log_2N}$, which is considerably smaller than the dimension of the Hilbert space of the system resulting from the usual QUBO map. This reduction can yield a significant speedup in quantum and classical computers. We simulate and validate our proposal using variational Monte Carlo with a neural quantum state, solving the TSP in a linear layout for up to almost 100 cities.

arXiv:2102.13298•Journal of the Physical Society of Japan•Oct 6, 2021•10 citations

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

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

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.

arXiv:2106.09056•Quantum Information Processing•Jan 22, 2022•65 citations

Análisis comparativo de QAOA mediante la formulación Tensor QUDO para una variante del TSP aplicable a motores de búsqueda de viajes

Alejandro Mata Ali, Adriano Lusso, Elías F. Combarro +2 more

The Travelling Salesman Problem (TSP) constitutes a fundamental Combinatorial Optimisation Problem (COP) with wide-ranging applications in logistics, transportation design and production scheduling. However, the best-known exact classical algorithms exhibit exponential time complexity, rendering large instances intractable in practice and motivating the exploration of alternative paradigms such as quantum computing. In this work, we implement the Quadratic Unconstrained Binary Optimisation (QUBO) formulation and its generalisation, Tensor Quadratic Unconstrained D-ary Optimisation (T-QUDO), which extends quantum circuit encoding from qubits to qudits, for a TSP variant. This variant seeks to determine a minimum-cost route while incorporating a timedependent cost function and precedence constraints, and remains largely unexplored with T-QUDO despite its relevance to dynamic travel planning. The formulations are encoded within the Quantum Approximate Optimisation Algorithm (QAOA) framework and analysed under noiseless simulations with the Cirq and CUDA-Q libraries, aiming to assess the potential advantages of qudit-based representations over qubit-based ones, particularly in terms of expressivity, resource efficiency, and solution quality.

JAIIO, Jornadas Argentinas de Informática•Oct 29, 2026•0 citations

QROSS: QUBO Relaxation Parameter optimisation via Learning Solver Surrogates

Tian Huang, Siong Thye Goh, Sabrish Gopalakrishnan +3 more

A popular method for solving a constrained combinatorial optimisation problem is to first convert it into a quadratic unconstrained binary optimisation (QUBO) problem, and solve it using a standard QUBO solver. However, this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints, and their chosen values significantly impact performance. Hence, hyper-parameters tuning is important. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them inefficient for performance critical applications when repeated solutions of similar combinatorial optimisation problems are required. In this paper, we propose the QROSS method, in which we build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce promising hyper-parameters with fewer calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate QROSS finds better solutions with fewer calls to QUBO solver, compared with conventional hyper-parameter tuning techniques. Moreover, with simple adaptation methods, QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.

arXiv:2103.10695•IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW)•Jul 1, 2021•5 citations
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.
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 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
We present a map from the travelling salesman problem (TSP), a prototypical NP-complete combinatorial optimisation task, to the ground state associated with a system of many-qudits. Conventionally, the TSP is cast into a quadratic unconstrained binary optimisation (QUBO) problem, that can be solved on an Ising machine. The size of the corresponding physical system's Hilbert space is 2N22^{N^2}2N2, where NNN is the number of cities considered in the TSP. Our proposal provides a many-qudit system with a Hilbert space of dimension 2Nlog⁡2N2^{N\log_2N}2Nlog2​N, which is considerably smaller than the dimension of the Hilbert space of the system resulting from the usual QUBO map. This reduction can yield a significant speedup in quantum and classical computers. We simulate and validate our proposal using variational Monte Carlo with a neural quantum state, solving the TSP in a linear layout for up to almost 100 cities.
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.
The Travelling Salesman Problem (TSP) constitutes a fundamental Combinatorial Optimisation Problem (COP) with wide-ranging applications in logistics, transportation design and production scheduling. However, the best-known exact classical algorithms exhibit exponential time complexity, rendering large instances intractable in practice and motivating the exploration of alternative paradigms such as quantum computing. In this work, we implement the Quadratic Unconstrained Binary Optimisation (QUBO) formulation and its generalisation, Tensor Quadratic Unconstrained D-ary Optimisation (T-QUDO), which extends quantum circuit encoding from qubits to qudits, for a TSP variant. This variant seeks to determine a minimum-cost route while incorporating a timedependent cost function and precedence constraints, and remains largely unexplored with T-QUDO despite its relevance to dynamic travel planning. The formulations are encoded within the Quantum Approximate Optimisation Algorithm (QAOA) framework and analysed under noiseless simulations with the Cirq and CUDA-Q libraries, aiming to assess the potential advantages of qudit-based representations over qubit-based ones, particularly in terms of expressivity, resource efficiency, and solution quality.
A popular method for solving a constrained combinatorial optimisation problem is to first convert it into a quadratic unconstrained binary optimisation (QUBO) problem, and solve it using a standard QUBO solver. However, this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints, and their chosen values significantly impact performance. Hence, hyper-parameters tuning is important. Existing generic hyper-parameter tuning methods require multiple expensive calls to a QUBO solver, making them inefficient for performance critical applications when repeated solutions of similar combinatorial optimisation problems are required. In this paper, we propose the QROSS method, in which we build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce promising hyper-parameters with fewer calls to the QUBO solver. We take the Traveling Salesman Problem (TSP) as a case study, where we demonstrate QROSS finds better solutions with fewer calls to QUBO solver, compared with conventional hyper-parameter tuning techniques. Moreover, with simple adaptation methods, QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.