تقرير
Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler
| العنوان: | Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler |
|---|---|
| المؤلفون: | Goldsmith, Daniel, Day-Evans, Joe |
| سنة النشر: | 2024 |
| المجموعة: | Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics |
| الوصف: | 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. Comment: 16 pages and 4 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2406.14252 |
| رقم الأكسشن: | edsarx.2406.14252 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |