Curator's Take
This article tackles a fundamental bottleneck in quantum optimization by dramatically reducing the qubit requirements for the classic Traveling Salesman Problem from O(n²) to O(n log n) through clever binary encoding. The researchers demonstrate that smart problem decomposition and encoding strategies can make combinatorial optimization accessible on today's limited quantum hardware, achieving near-perfect success rates on small instances and even running experiments on actual quantum computers. While the city counts are still modest, this work represents exactly the kind of resource-efficient thinking needed to bridge the gap between theoretical quantum advantage and practical near-term implementations. The combination of compact encoding with divide-and-conquer execution offers a promising template for tackling other optimization problems on current noisy intermediate-scale quantum devices.
— Mark Eatherly
Summary
The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.