Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem
This work addresses the NP-hard TSP for logistics and network design, showing incremental progress by integrating quantum and classical methods to enhance performance on noisy quantum hardware.
The paper tackled the Traveling Salesperson Problem (TSP) by proposing a hybrid quantum-classical framework, achieving an approximation ratio of 1.0287 at 80 cities, a 47.5% improvement over quantum-only methods, and reducing variability in tour distances.
The Traveling Salesperson Problem (TSP), a quintessential NP-hard combinatorial optimisation challenge, is vital for logistics and network design but limited by exponential complexity in large instances. We propose a hybrid quantum-classical framework integrating variational quantum eigensolver (VQE) optimisation with classical machine learning, using K-means clustering for problem decomposition and a RandomForestRegressor for path refinement. Evaluated on 80 European cities (from 4 to 80 cities, 38,500 samples in total) via Qiskit's AerSimulator and ibm_kyiv 127-qubit backend, the hybrid approach outperforms quantum-only methods, achieving an approximation ratio of 1.0287 at 80 cities, a 47.5% improvement over quantum-only's 1.9614, nearing the classical baseline. Machine learning reduces variability in tour distances (interquartile range, IQR - the spread of the middle 50% of results relative to the median - from 0.06 to 0.04), enhancing stability despite noisy intermediate-scale quantum (NISQ) noise. This framework underscores hybrid strategies' potential for scalable TSP optimisation, with future hardware advancements promising practical quantum advantages.