{"ID":2862779,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.26229","arxiv_id":"2509.26229","title":"Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.26229","url_pdf":"https://arxiv.org/pdf/2509.26229v1","authors":"[\"Christos Lytrosyngounis\",\"Ioannis Lytrosyngounis\"]","published":"2025-09-30T13:26:12Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.LG\"]","methods":"[]","has_code":false}