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=9jobs on its Quadratic Unconstrained Binary Optimization (QUBO) form, using
O(N)qubits on DWave's Advantage_system4.1 quantum annealing device. The best known quantum algorithm for TSP to date uses
O(N2)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.
With the ongoing progress of quantum computing, there is increasing interest in bringing quantum technologies into real-world applications, making practically motivated NP-hard problems particularly important to study. In this work, we solve the traveling salesperson problem (TSP) on real quantum hardware to demonstrate and analyze the performance of different quantum chips, and we benchmark these results against simulations. This comparison provides evidence supporting the feasibility of deploying quantum computation toward practical applications.