对比多种量子架构解旅行商问题，发现光子型系统更适配大规模实例。
Solving the Traveling Salesman Problem via Different Quantum Computing Architectures
- 用量子退火与光子伊辛机等架构求解TSP，比传统方法更快。
- 真实量子设备受限于噪声，仅能处理最多6个城市的实例。
- 光子型伊辛机可解至18城，适合超大规模优化场景。
我们研究新兴光子与量子计算架构在求解旅行商问题（TSP）中的应用，这是一个经典的NP难优化问题。考察了模拟退火（SA）、量子退火与光子相干伊辛机实现的二次无约束二元优化（QUBO-Ising）方法，以及基于门模型量子计算机的量子近似优化算法（QAOA）和量子相位估计算法（QPE）。QAOA与QPE在IBM Quantum平台进行测试。QUBO-Ising方法使用基于超导约瑟夫森结的D-Wave量子退火机和QCi Dirac-1熵量子优化机。门模型量子计算机在仿真中对小规模TSP实例表现准确，但实际量子设备受噪声和可扩展性限制，电路复杂度随问题规模增长，性能仅限于最多6个节点的实例。相比之下，基于伊辛的架构在更大规模问题上展现出更好可扩展性：基于SQUID的伊辛机可处理最多12个节点，而混合光电子组件实现的熵计算可扩展至18个节点。然而，由于硬件限制和难以收敛至基态，解的质量通常次优。尽管如此，伊辛机相比经典方法具有显著时间优势，是高效求解大规模TSP的有前景方案。
原文摘要 · Abstract (English)
We study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem. We investigate several approaches: Simulated Annealing (SA), Quadratic Unconstrained Binary Optimization (QUBO-Ising) methods implemented on quantum annealers and Optical Coherent Ising Machines, as well as the Quantum Approximate Optimization Algorithm (QAOA) and the Quantum Phase Estimation (QPE) algorithm on gate-based quantum computers. QAOA and QPE were tested on the IBM Quantum platform. The QUBO-Ising method was explored using the D-Wave quantum annealer, which operates on superconducting Josephson junctions, and the Quantum Computing Inc (QCi) Dirac-1 entropy quantum optimization machine. Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. However, real quantum devices are hindered by noise and limited scalability. Circuit complexity grows with problem size, restricting performance to TSP instances with a maximum of 6 nodes. In contrast, Ising-based architectures show improved scalability for larger problem sizes. SQUID-based Ising machines can handle TSP instances with up to 12 nodes, while entropy computing implemented in hybrid optoelectronic components extend this capability to 18 nodes. Nevertheless, the solutions tend to be suboptimal due to hardware limitations and challenges in achieving ground state convergence as the problem size increases. Despite these limitations, Ising machines demonstrate significant time advantages over classical methods, making them a promising candidate for solving larger-scale TSPs efficiently.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。