通过量子计算解决“旅行商问题”

计算机科学领域的一个经典算法问题称为旅行商问题 (TSP)，它是组合优化问题的一个典型例子。

TSP到底是什么？这本数学经典涉及寻找最短路线，在返回出发城市之前恰好访问 N 个城市一次。然而，随着城市数量的增加，可能的路线和寻找最优解决方案的计算时间也会增加。 虽然这个问题可以使用近似方法来解决，但量子计算机可以提供更好的解决方案并且速度更快。 

这正是理论物理学家所说的 Jens Eisert 教授的团队演示了：使用量子计算机可以更好更快地解决此类问题。

量子计算利用利用量子力学的硬件和算法来解决传统技术（包括超级计算机）无法解决的复杂问题。尽管超级计算机（具有数千个 CPU 和 GPU 核心的大型经典计算机）功能强大，但在解决高度复杂的问题时，由于依赖 20 世纪的晶体管技术而受到限制。 

这就是量子物理学的用武之地。与以二进制位（0 和 1）编码信息的经典计算机相反，量子计算机使用量子位或量子位来运行多维量子算法。 

此外，与使用风扇进行冷却的传统计算机不同，量子计算机要求其量子处理器保持在极冷的温度下以保持其量子态。这是通过过冷超流体实现的。 

超导体是表现出临界量子力学效应的材料，允许电子毫无阻力地穿过它们。当电子通过时，它们配对以携带电荷穿过势垒。当两个超导体放置在绝缘体的两侧时，就会形成约瑟夫森结，用于传导超导量子位。  

量子比特在一项重要任务中发挥着重要作用：将其量子信息置于叠加态（量子比特可能配置的组合）。叠加态的量子比特组能够创建复杂的多维计算空间，从而用于表示复杂的问题。

在这里，通过两个量子位的纠缠，一个量子位的变化可以直接影响另一个量子位，而当这些纠缠的量子位处于叠加状态时，我们得到了很多概率。量子计算机上的计算通过准备所有可能的计算状态的叠加来进行，并通过干扰找到解决方案。

当然，构建具有许多量子位的量子计算机是一个非常复杂的过程，尽管正在探索几种方法来了解此类计算机可以完成的任务。 

艾塞特是能源材料研究中心赫尔姆霍兹中心 (HZB) 和柏林自由大学公共研究大学联合研究小组的负责人，他表示：

“关于它有很多神话，有时还有一定程度的夸夸其谈和炒作。然而，我们使用数学方法严格地解决了这个问题，并就该主题提供了可靠的结果。最重要的是，我们已经澄清了在什么意义上可以有任何优势。” 

关键的旅行商问题

TSP 是一个优化问题，在物流和供应链行业中具有重要的经济意义。它属于更广泛的组合优化问题类别，其中还包括作业调度、资源分配、投资组合优化，甚至蛋白质折叠，所有这些对各个部门都至关重要。

鉴于这些问题的社会和经济意义，它们一直是深入研究的主题。因此，找到最高效的供应链和最便宜的送货路线等问题的答案对我们的日常生活产生积极影响。

然而，优化多个目的地的配送路线，同时考虑各种限制，例如交通拥堵、运营成本上升、路线突然改变、最后一刻的业务预约和客户要求，使得 TSP 的解决难度更大。尽管存在这些挑战，解决 TSP 对于高效交付货物至关重要，从而确保可行的商业模式。 

解决这个问题有很多好处，包括减少行驶距离和时间以及节省燃料使用。最大限度地减少出行距离有助于显着减少碳足迹，从而改善空气质量、减缓气候变化和经济增长。此外，解决TSP可以帮助按时交付货物和及时与客户会面，从而增强客户体验和现场服务业务。

正如我们所看到的，解决问题不仅可以帮助企业，而且这些好处也会惠及客户，丰富每个参与者的体验。

解决 TSP 问题的方法有很多种。其中一种方法是“强力”法，它会计算所有可能的排列组合，以找到最短路径。在分支定界法中，问题被分解为一系列子问题，每个阶段的解都会影响后续阶段的解。

在动态规划中，重点是避免冗余计算。与此同时，最近邻是一种近似算法，从起始位置开始，然后在最近的位置停止。覆盖完所有城市后，您将返回起点。虽然实用且相对快速，但该方法可能并不总是提供有效的路线。

随着技术的进步，路线规划和优化可以更加有效地完成。尤其是人工智能（AI）还可以通过快速分析海量数据来帮助解决问题，帮助许多现代企业做出运营和战略决策。

量子计算机也正在被研究来解决这个问题；毕竟，它们比传统计算机提供了相当大的计算速度。长期以来，人们一直认为这些计算机实际上可能有助于改进对这些问题的近似。 

利用量子计算技术解决TSP

虽然量子计算引起了人们的极大兴趣并为某些问题提供了有希望的结果，但这种量子优势的程度在很大程度上仍未得到探索。 

因此，这项研究提供了充分的建设性证据，证明量子计算机在寻找组合优化问题的近似值方面实际上可以优于传统计算机。

由 Eisert 和他的同事 Jean-Pierre Seifert 领导的最新研究仅使用分析方法来评估具有量子位的量子计算机如何解决 TSP 问题。 

Vincent Ulitzsch 解释说：“无论物理实现如何，我们只是假设有足够的量子位，并研究用它们执行计算操作的可能性”，这与密码学中的一个常见问题（即数据加密）相似。 ，博士。柏林工业大学的学生。 

然后，该团队使用量子算法 Shor 算法来查找整数的素因数，并求解此类优化问题的子类。这样，随着城市数量的增加，计算时间将不再呈爆炸式增长。它只会以多项式形式增长，即 Nx，其中 x 为常数。这样，​​得到的解在质量上也远优于使用传统算法从近似解中得出的解。

通过使用密码学概念和计算学习理论，该研究给出了“完全有建设性的证据，证明量子计算机在近似组合优化问题方面比经典计算机具有超多项式优势。” 

该研究进一步指出，研究团队在量子计算机可能为组合优化问题的近似解决方案提供哪些潜在的重要问题上取得了重大进展，这具有重大的社会和经济影响。

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

探索量子计算的潜力 

虽然这是一项伟大的成就，但这并非量子计算首次用于解决旅行商问题。之前有很多爱好者和研究人员正在探索利用量子计算来解决这个问题。 

2022年XNUMX月， 纸 提出了一种基于 Grover 自适应搜索 (GAS) 的 TSP 量子算法。在GAS框架下，至少存在两个根本性的困难——解决方案可能不可行，以及当前量子计算机的量子比特数量非常有限，无法满足最低要求，限制了量子算法在组合优化问题上的应用。 

因此，论文完善了哈密顿环检测（HCD）预言机，它可以在算法执行过程中自动删除不切实际的解。他们还设计了一种“锚定寄存器”策略来节省量子位的使用，充分考虑了量子计算的可逆性要求，克服了所使用的量子位不被简单覆盖或释放的困难。它使得该研究只需要 31 个量子比特，解决方案的成功率为 86.71%。

2019年，自我定义的物理行家Joseph Cammidge 写 关于使用退火量子处理器，这使他能够解决七个城市的旅行商问题，并且一旦消除技术限制，理论上有可能解决九个城市的问题。 

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

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

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

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

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

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

单击此处了解量子计算的当前状态。

从事量子计算的公司 

现在，让我们来看看一些致力于量子计算研究和开发的名字：

＃1。 IBM

国际商业机器公司（IBM）业务范围广泛，包括人工智能、云服务、IT、客户融资和商业融资。这家科技巨头还通过其IBM量子平台参与量子计算，该平台向公众和高级用户提供其基于云的量子计算服务。这些服务包括一套IBM的量子处理器原型、量子计算教程和一本互动教科书。

最近，IBM 科学家 说 他们距离克服障碍又近了一步，从而释放了量子计算机改变游戏规则的潜力。为此，他们引入了一种新的量子纠错码，据称其效率比以前的方法高出大约十倍。 

去年年底，该公司还推出了名为 Condor 的量子计算机，拥有 1,121 个超导量子位，呈蜂窝状排列。 IBM 还推出了 IBM 量子系统二号，这是其首款模块化量子计算机和以量子为中心的超级计算架构，该架构具有可扩展性，因此可以使用未来五年内推出的芯片进行升级。

IBM 市值 175 亿美元，股价报 190.86 美元，年初至今 (YTD) 上涨 16.66%。IBM 公布的营收 (TTM) 为 61.86 亿美元，每股收益 (TTM) 为 8.03 美元，市盈率 (TTM) 为 23.76 美元，净资产收益率 (TTM) 为 33.36%。该公司的股息收益率为 3.48%。

＃2。 D-Wave系统公司

这家量子计算公司开发并提供相关系统、软件和服务。其产品包括 The Leap 和 The Advantage，为调度、物流、药物发现、制造工艺等提供量子应用。 

本月早些时候，D-Wave 表示，量子机器现在可以比任何普通计算机更快地解决现实世界应用程序的问题。今年早些时候，该公司宣布推出一款具有 1,200 个量子位、10,000 个耦合器的量子计算机，并且解决硬优化问题的时间加快了 20 倍。

该公司股价目前为1.86美元，年初至今上涨138.6%，市值为267亿美元。该公司公布的销售额（TTM）为8.247万美元，每股收益（TTM）为-0.66美元，市盈率（TTM）为-3.19美元，并宣布其20年第四季度和年末的销售额均增长超过4%，预订量分别增长了2023%和34%。 

有趣的是，该公司首席执行官艾伦·巴拉茨博士 (Dr. Alan Baratz) 宣布了公司的发展势头，列举了公司与 Zapata AI 的多年战略合作伙伴关系、1,200+ 量子比特 Advantage2 原型的推出、与 NEC 澳大利亚和德勤加拿大的合资企业，以及前国土安全部部长克尔斯滕·尼尔森 (Kirstjen Nielsen) 被任命为董事会成员。

结语

量子计算市场预计 达到6.5亿美元 到 2028 年，它解决旅行商问题 (TSP) 的潜力将对制造业、物流、供应链管理、电子商务、运输和研究等多个行业产生影响。毕竟，它可以带来巨大的好处，特别是提高生产力、削减开支并刺激不同行业的创新。

单击此处查看最佳五家量子计算公司的列表。