让旅行商不再迷茫！物理学家用量子计算机更快解决 TSP 问题

内容来源：量子前哨（ID：Qforepost）

编辑丨浪味仙 编译/排版丨沛贤

在组合优化领域，旅行商问题 (TSP) 是圣杯一样的存在，它已经被全球各地的一流应用数学家们研究了几十年，却始终未能取得令人欣喜的进展。

简单来说，旅行商问题 (TSP) 是指一位商品推销员要走访 N 个城市，要求所有城市不能重复经过，最后回到出发城市，他该如何规划最短路径？

乍一看，只需一张稿纸和笔，你就能帮到这位不知所措的推销员。可事实是，随着城市数量的增加，找到可能的最短路径组合所耗费的时间也在增加，而且是恐怖的阶乘级增长。别说一张稿纸，就是让超级计算机来求解，也绝非易事。

尽管超算拥有数千个 CPU 和 GPU，具备超强性能，但在高度复杂的计算问题面前，也不可避免地受到 20 世纪晶体管技术的限制。而有别于经典物理的量子计算机，却凭借着神奇量子特性带来的超强并行计算能力，成为解决特定复杂计算问题的一把好手。

相比传统计算机，量子计算机能够更好更快地解决旅行商问题 (TSP)，理论物理学家 Jens Eisert 教授团队对此进行了证明。

“围绕量子计算机有很多神话，有时还有一定程度的夸夸其谈与炒作。然而，我们用数学方法严格验证、并就该问题提供了可靠的结果。最重要的是，我们已经澄清了它在哪些层面上具有量子优势。”

1、至关重要的旅行商问题 (TSP)

TSP 是组合优化中的一个经典问题，在物流和供应链行业中具有重要的经济意义。映射到现实中，与之相关的应用场景包括作业调度、资源分配、投资组合优化、蛋白质折叠等。

鉴于以上场景所承载的社会和经济意义，例如寻求最高效的供应链调度方式、最经济的配送路线安排等，能够对我们的日常生活产生积极影响，所以组合优化问题一直是相关领域的重点研究主题。

解决 TSP 有很多好处。比如高效按时交付货物、减少行驶距离和时间以节省燃料用量等等，再进一步还有助于减少碳足迹、改善空气质量、减缓气候变化、加快经济增长。

尽管好处多多，但研究却遍布挑战。例如在考虑交通拥堵、运营成本上升、路线突然变化、客户要求等多个制约因素的同时，怎样才能高效实现多个目的地间的最佳送货路线。

在解决 TSP 的方法中，一种常见方法叫做穷举法。这是一种大力出奇迹的手段，通过计算所有可能的排列组合方案，从中找到最短的路线。在分支限界算法中，TSP 问题被分解为几个系列的子问题，每个阶段的解决方案都会影响后续阶段找到的解决方案。

在动态规划中，重点是避免冗余计算。在近似最近邻搜索算法中，我们可以在其中任一起始位置开始，然后停在最近的位置，一旦覆盖所有城市，就会回到起点。这种算法虽然实用且相对快速，但它并不总能提供有效的路线。

随着技术的不断进步，比如人工智能 (AI) 的加持，研究者可以通过快速分析大量数据，更有效地解决路线规划和优化等问题。同样，研究者们认为，能够提供计算加速的量子计算机，非常有助于改善 TSP 的近似值。

2、使用量子计算技术求解 TSP

近些年来，尽管量子计算引起了人们的极大兴趣，并为某些问题提供了更优解，但量子优势的潜力在很大程度上仍未得到充分发掘。

对此，在由理论物理学家 Eisert 教授及其同事 Jean-Pierre Seifert 领导的最新研究中，仅使用分析方法来评估具有量子比特的量子计算机如何解决 TSP 问题，用充分的建设性证据证明，量子计算机在寻找组合优化问题的近似值方面，实际上可以胜过传统计算机。

Eisert 教授团队使用 Shor 算法找到整数的质因数，再求解这类优化问题的子类。这样一来，随着城市数量的增加，计算时间将不再爆炸式增长，取而代之为多项式增加，由此得到的解会比使用传统算法更靠近近似解。

该研究借助密码学概念和计算学理论，为证明“量子计算机在解决近似组合优化问题方面，比经典计算机具有超多项式优势”提供了建设性的证据，具有重大的社会和经济影响。

该研究由爱因斯坦研究部门、柏林数学研究中心（MATH+ Cluster of Excellence）、BMBF（Hybrid）、BMWK（EniQmA）、慕尼黑量子谷和 DFG 资助，德国联邦教育和研究部也提供了财政支持。

3、探索量子计算的潜力

这并非量子计算首次被用于解决旅行商问题 (TSP)。

2022 年 12 月，有论文提出一种基于 GAS (Grover 自适应搜索) 的 TSP 量子算法。在 GAS 框架下，至少存在两个根本难点：解决方案不可行，以及当前有限的量子比特数无法满足最低要求。这就限制了量子算法在组合优化问题中的应用。

Eisert 教授团队的论文完善了哈密顿循环检测（HCD）预言机，它可以在算法执行过程中自动删除不切实际的解决方案，并设计了一种“锚寄存器”策略来节省量子比特的使用，充分考虑到量子计算的可逆性要求，克服了使用的量子比特不能被简单地覆盖或释放的困难，允许研究只需要 31 个量子比特，就能让解决方案的成功率达到 86.71%。

2019 年，应用科学顾问分析师约瑟夫·卡米奇 (Joseph Cammidge) 撰写了一篇关于使用退火量子处理器有关的文章，该处理器使他能够解决七个城市的旅行推销员问题，并且一旦技术限制消除，就具有解决九个城市的理论潜力。

量子退火这一新的计算方法已显示出比传统技术更快解决优化问题的潜力，其理论表明，量子位在过冷时将达到最佳的低能量状态。

然而在 2021 年，强生供应链数字与数据科学资助的一项研究发现，量子退火器只能处理 8 个或更少节点的问题规模，其性能在时间和准确性方面都低于经典求解器。

使用量子计算解决 TSP 问题已经持续了一段时间。二十多年前，也就是 2001 年，一项研究开始寻找一种量子算法来解决这个问题。

在这篇论文中，阿拉巴马大学的巴克利·霍珀（Buckley Hopper）研究了格罗弗和肖尔的量子计算机算法。他指出，格罗弗的算法仅提供了平方根的改进，这意味着它无法使经典的棘手问题在量子计算机上变得易于处理。至于肖尔的算法，霍珀观察到，虽然它可以将一个可能难以解决的质因数问题转换为在量子机器上易于处理的问题，但它只适用于非常特定类型的问题。

总的来说，霍珀认为“对于计算旅行推销员问题的近似解的算法，没有找到令人满意的结果”。

几年后，受遗传算法和量子计算的启发，电气和电子工程师协会 (IEEE) 提出了一种解决该问题的新算法。IEEE 发现，在旅行商问题的某些实例中应用所提出的算法的结果比标准遗传算法提供的结果要好得多。

目前，致力于量子计算研究和开发的公司有不少。

比如 IBM，推出具有 1121 个蜂窝状排列的超导量子计算机 Condor，以及首个模块化量子计算机和以量子为中心的可扩展超级计算架构 Quantum System Two，并为公众提供基于其 IBM Quantum 平台的远程量子计算服务，最近还引入了一种新的量子纠错代码，据 IBM 科学家表示，能比以前的方法效率高出十倍左右。

再比如 D-Wave，这是一家成立于 1999 年、全球第一家进入量子计算市场的商业公司，目前已是量子计算系统、软件和服务领域的领导者。前不久，D-Wave 表示，其量子机器现在可以比任何普通计算机更快地解决现实世界应用的问题，而在今年早些时候，D-Wave 推出了一款具有 1,200 个量子比特、10,000 个耦合器的量子计算机，令解决复杂优化问题的时间缩短了 20 倍。

预计到 2028 年，量子计算市场规模将达到 65 亿美元，其解决旅行商问题 (TSP) 的潜力一旦发挥，对制造业、物流、供应链管理、电商、运输和研究等多个行业都会产生实质性的增强作用，尤其表现为提高生产力、削减开支，以及刺激行业创新。