Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler ...
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 a...
| Main Authors: | , |
|---|---|
| Format: | Report |
| Language: | unknown |
| Published: |
arXiv
2024
|
| Subjects: | |
| Online Access: | https://dx.doi.org/10.48550/arxiv.2406.14252 https://arxiv.org/abs/2406.14252 |
| Summary: | 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 ... : 16 pages and 4 figures ... |
|---|