用量子退火求解带额外节点的旅行商问题，提升解的质量与效率。
Steiner Traveling Salesman Problem with Quantum Annealing
- 通过预处理压缩网络规模，降低问题复杂度
- 量子退火在减少总路径成本上表现优于经典方法
- 适合对量子计算优化算法感兴趣的科研人员
Steiner旅行商问题（STSP）是经典旅行商问题的变体，需引入额外的Steiner节点以优化路径、降低总旅行成本。由于其属于NP难问题，本文提出基于量子退火的求解方法，利用D-Wave硬件实现。为提升计算可行性，设计了一种预处理技术，有效缩减网络规模。实验表明，该方法显著降低问题复杂度，使二次无约束二值优化（QUBO）形式更适配现有量子硬件。结果验证了量子退火在解决STSP中的潜力，是一种有前景且创新的解决方案。
原文摘要 · Abstract (English)
The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set but that can be added to the route to enhance the overall solution and minimize the total travel cost. Given the NP-hard nature of the STSP, we propose a quantum approach to address it. Specifically, we employ quantum annealing using D-Wave's hardware to explore its potential for solving this problem. To enhance computational feasibility, we develop a preprocessing method that effectively reduces the network size. Our experimental results demonstrate that this reduction technique significantly decreases the problem complexity, making the Quadratic Unconstrained Binary Optimization formulation, the standard input for quantum annealers, better suited for existing quantum hardware. Furthermore, the results highlight the potential of quantum annealing as a promising and innovative approach for solving the STSP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。