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