混合量子经典算法显著提升旅行商问题求解精度与稳定性。
Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem
- 用聚类分解问题，机器学习优化路径，结合量子变分算法
- 80城市时近似比达1.0287，较纯量子方法提升47.5%
- 适合关注量子优势落地、需稳定结果的优化研究者
旅行商问题（TSP）是典型的NP难组合优化问题，对物流和网络设计至关重要，但大规模实例受限于指数级复杂度。本文提出一种混合量子-经典框架，结合变分量子本征值求解器（VQE）与经典机器学习，利用K-means聚类进行问题分解，并采用RandomForestRegressor进行路径精炼。在包含4至80个欧洲城市的测试集上（共38,500个样本），通过Qiskit AerSimulator与ibm_kyiv 127比特量子后端评估，该混合方法优于纯量子方案，在80城市情形下实现1.0287的近似比，相较纯量子方法的1.9614提升47.5%，逼近经典基线。机器学习使路径距离的四分位距（IQR）从0.06降至0.04，有效降低噪声环境下的波动性。该框架验证了混合策略在可扩展TSP优化中的潜力，未来硬件发展有望实现实际量子优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。