Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915525135695872 |
|---|---|
| author | Lytrosyngounis, Christos Lytrosyngounis, Ioannis |
| author_facet | Lytrosyngounis, Christos Lytrosyngounis, Ioannis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_26229 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem Lytrosyngounis, Christos Lytrosyngounis, Ioannis Quantum Physics Machine Learning 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. |
| title | Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem |
| topic | Quantum Physics Machine Learning |
| url | https://arxiv.org/abs/2509.26229 |