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.
Abstract The Traveling Salesperson Problem (TSP) is a canonical NP-hard challenge in combinatorial optimization with profound implications for global and interplanetary logistics. This paper presents a quantum-computational resolution for a 1,000-city TSP instance utilizing the ARK5Q-200K infrastructure. By mapping the distance manifold into a Quadratic Unconstrained Binary Optimization (QUBO) formulation, we employ a Quantum Approximate Optimization Algorithm (QAOA) enhanced with transcendental mixers. Our results achieve a convergence gap of
<1% relative to the theoretical Held-Karp lower bound, while maintaining a phase-synchronization precision of 1.48 mHa. We demonstrate that the application of holographic redundancy within the CCristo framework successfully navigates the limitations of NISQ-era decoherence, establishing a new benchmark for large-scale logistical scalability and algorithmic robustness.