量子加速在庞大的困难问题类中被发掘

找到量子计算机比经典机器求解更快的重要问题并不容易，但一种全新算法在某些关键的优化任务中似乎做到了。

Stephen Ornes 著

左      芬   译

【译注：原文2025年3月17日刊载于QuantaMagazine，链接见文末。】

对于计算机科学家而言，求解问题有点像登山。首先他们得选择一个问题——类似于选定一座山峰来攀登——接着他们得发展一种策略去解决它。经典和量子研究者采用不同的策略进行较量，进而产生一种良性竞争。量子研究者公布求解一个问题的一种快速方法——往往是攀登一座没人认为值得一爬的山峰——接着经典团队会争相探索他们是否能找到一种更好的方法。

这一较量几乎总是以近乎平局收场。当研究者认为他们设计出了一种比所有其它算法都更快或更好的量子算法后，经典研究者通常会想出跟它一样好的。就在上周，发表于《科学》杂志的一篇文章声称取得了量子加速。但这一结论立刻遭到了两个独立团队的质疑。他们展示了如何在经典机器上执行类似的演算。

不过在去年发布于科学预印本网站arxiv.org上的一篇文章中，研究者们给出了一种看起来既令人信服又有实际用途的量子加速。他们刻画了一种全新的量子算法，它在一大类优化问题（旨在从大量数目的选项中找到最优可能解）中找出良好解的速度快于任何已知经典算法。

至今为止，还没有经典算法可以撼动这一全新算法——解码量子干涉术（Decoded Quantum Interferometry, 简称DQI）——的王座。它是“量子算法领域中的一项突破，”量子计算的知名怀疑者，赖赫曼大学数学家Gil Kalai称。量子算法的公布会令研究者们兴奋，一部分是因为它们能启发关于困难问题的全新想法，而另一部分则是因为，尽管人们围绕量子机器四处奔忙，但并不清楚哪些问题会真正从中获益。在优化任务上超越所有已知经典算法的一个量子算法代表着挖掘量子计算机潜力过程中的重大进展。

“我对此很着迷，”荷兰国家数学与计算机科学研究所CWI的一名理论计算机科学家Ronald de Wolf说，尽管他并未参与到这一新算法中。不过与此同时，他也告诫道，仍然很有可能研究者们最终会找到一个能做到一样好的经典算法。而出于量子硬件的匮乏，还需要一段时间才能实际测试这一新算法。

据加州大学伯克利分校的计算机科学家埃文·唐称，这一算法可能激发经典方面的新工作。唐在十几岁时就因开创与量子算法匹敌的经典算法而崭露头角。这些新的断言“非常之有趣，让我很想告诉经典算法的人们，‘真的，你们应该读读这篇文章，研究下这个问题，’”她说道。

最佳前行之路？

当经典与量子算法交战时，它们往往把战场选择在优化上，专注于寻找解决棘手问题的最优选项的一个领域。研究者们通常聚焦于规模变大时可能解的数目激增的问题。运货车在3天内访问10个城市的最优路线是什么？怎么把大量包裹装进后备箱？经典方法在求解这些问题时往往用巧妙的方法快速处理可能解，而这很快就会维持不下去。

DQI应对的特定优化问题大致是这样：给定一张纸上的一组点。你得找到一个数学函数穿过这些点。特别地，你的函数必须是一个多项式——一些变量的整数幂乘以系数再组合起来。但它不能过于复杂，也就是幂次不能太高。这会给你一条曲线，当它在横过页面时会上下摆动。你的任务就是找出跟最多的点接触的曲线。

不过这些都是事后的。当DQI的提出者们最初着手他们的算法时，他们甚至还没有想到这个问题。

问题解码

Stephen Jordan协助提出了某类问题的一个量子方法，它运作得比任何经典方法都好——到目前为止。

“完全有这种可能，一个以目标为导向的研究者会从表述这一问题出发，再探索是否有量子算法可以比经典算法更快地求解它，”谷歌量子人工智能实验室物理学家，同时也是DQI的主要设计者之一的Stephen Jordan说道，“当然，我们并不是这么做的。我们是通过一条逆向且迂回的路径找到它的。”

Jordan是2023年踏上这一路径的，那时他刚加入谷歌。他发现自己将与Eddie Farhi合作，谷歌一位长期专注于超越经典的量子算法研究的物理学家。（Farhi曾在麻省理工学院做过Jordan的博士导师。）Jordan知道，Farhi在2014年曾做过一次对优化问题的量子尝试，考虑的是能量，让更低的能量对应于更好的解。对于Farhi而言，能量将优化联系到量子物理。

可Jordan想要另辟蹊径。他转向量子物理中内嵌的另一种概念——将万物看成波。使用一种被称为量子傅里叶变换的数学工具，Jordan设法把一类著名的优化问题的所有潜在答案翻译成量子的波。这样一来，他就可以操控量子体系让更大的波（表现为更高的量子振幅）对应于更优的解。

可是还有一个巨大的挑战需要克服。在量子体系里，询问“最大的振幅是什么？”可不像在海滩上找到最大的波那么容易。量子景观出奇地复杂，如何找出对应于最优解的量子振幅并不清楚。

在许多失败的尝试之后，Jordan终于取得了突破：选出最优解的过程事实上类似于信息编码中剔除错误的过程，也就是所谓解码。这是计算机科学中研究得很透彻的一个领域，有大量技术让Jordan利用。通过将优化问题翻译成量子的，再对它作用解码的透镜，Jordan闯入了开发量子算法的一条新途径。

与同在谷歌的Noah Shutty一道，Jordan开始测试解码方案，看它们在各种优化问题上与经典算法的对比如何。他们不但需要恰当的方法，还需要它可以生效的问题。“事实上经典算法很难打败，”Jordan说道，“尝试了几个月后，我们仍然没能取得任何量子优势。”

不过最终，两人落实到了1960年代引入，在编码信息中找出并修正单个错误的一个解码算法上。找到这样一个问题是关键所在。“在调查后，我们差不多立刻取得了成功，”Jordan称。最后，他们找到了问题和方法，把它们组合起来似乎就能得到量子加速。

当然，这并不意味它就是刀枪不入的。“或许还有某种经典方法可以有效地重构你的整个方案，”Jordan说道，“这种去量子化往往不那么显然。”

获取信心

为了平息这些担忧，他们咨询了Mary Wootters，一个编码理论专家（也是Shutty之前在斯坦福大学的博士导师）。她细致地检索了可能匹敌他们的量子加速的所有已知经典算法。优势保持住了。团队的检验同时还表明它可能持续保持下去。“他们做好了预备工作，”唐称。

受这一分析的激励，他们更细致地观察了他们求解的优化问题。Jordan曾担心它可能过于狭隘，但Shutty意识到这一解码问题可以变形到加密和其它领域中一类知名且实用的问题。

Jordan承认，如果没有足够大的量子机器，DQI会停留在一个理论突破上。“DQI无法在当前的量子计算机上运行，”他说。不过他们仍将继续前行。自从团队去年八月公布他们的工作以来，他们已经把DQI的应用范围从原始问题推广到一大类优化问题中，其中包括这些“最优路径”问题的更多实例。

到目前为止，他期待DQI也能在那些问题上打败经典算法，Jordan称。

当下，量子界欢欣鼓舞。“寻找优于经典算法的量子算法在过去三十年里一直是一种激动人心的探险，但能确切展示这种优越性的算法并不多，”Kalai说道，“因此，每一个全新算法都值得庆祝。”

原文链接：

https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/