# Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem

arXiv: https://arxiv.org/abs/2509.26229 · HTML: https://mlsanity.com/paper/2509.26229/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 25 references that are in the map.
- First posted on arXiv 30 Sep 2025.

## Builds on (most cited first, 6 of 6)

- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Challenges and Opportunities in Quantum Optimization](https://mlsanity.com/paper/2312.02279/) (2023)
- [Accelerating Quantum Approximate Optimization Algorithm using Machine Learning](https://mlsanity.com/paper/2002.01089/) (2020)

## Built on by (most cited first, 1 of 1)

- [Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability](https://mlsanity.com/paper/2512.10813/) (2025)

## Abstract (arXiv)

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.