[中文正文内容]

由 Simons Foundation 支持的编辑独立出版物。 Follow Quanta Facebook [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/twitter.com/QuantaMagazine) Youtube Instagram RSS [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/bsky.app/profile/did:plc:vfktz6qe6vy7serr3wqutpzt) Newsletter 获取最新消息，直接发送到您的收件箱。 Email Subscribe 近期新闻通讯 Gift Store Shop Quanta gear Quanta Homepage

Saved Articles

通过单击您希望保存的文章旁边的稍后阅读图标来创建阅读列表。 查看所有已保存的文章

Log out

Change password

输入搜索词并按Enter键 What are you looking for? Search Popular Searches

Home Quantum Speedup Found for Huge Class of Hard Problems Comment Save Article Read Later

Share

Facebook [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/twitter.com/share?url=https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/&text=Quantum+Speedup+Found+for+Huge+Class+of+Hard+Problems&via=QuantaMagazine) Copied! Copy link (opens a new tab) Email Pocket Reddit Ycombinator [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/bsky.app/intent/compose?text=https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/)

quantum computing

针对一类难题发现 Quantum Speedup

By Stephen Ornes March 17, 2025 一直以来，找到量子计算机能够比经典计算机更快解答的重要问题是困难的，但一种新的算法似乎可以为一些关键的优化任务做到这一点。 Comment Save Article Read Later A quantum boat engine speeding past a normal board Daniel Garcia for Quanta Magazine

Introduction

By Stephen Ornes Contributing Writer March 17, 2025 View PDF/Print Mode algorithms computational complexity computer science cryptography quantum computing All topics (opens a new tab)

对于计算机科学家来说，解决问题有点像登山。首先，他们必须选择一个要解决的问题——类似于确定一个要攀登的山峰——然后他们必须制定一个解决它的策略。经典和量子研究人员使用不同的策略进行竞争，两者之间存在着健康的竞争。量子研究人员报告了一种快速解决问题的方法——通常是通过攀登一座没有人认为值得攀登的山峰——然后经典团队竞相查看他们是否能找到更好的方法。

这场竞赛几乎总是以虚拟平局告终：当研究人员认为他们已经设计出一种比其他任何算法都更快或更好的量子算法时，经典研究人员通常会提出一个与之匹敌的算法。就在上周，发表在《Science》杂志上的一项据称的 quantum speedup，立即遭到了两个独立团体的怀疑，他们展示了如何在经典机器上执行类似的 计算。

但是在去年发布在科学预印本网站 arxiv.org 上的一篇论文中，研究人员描述了一种看起来既令人信服又有用的 quantum speedup。研究人员描述了一种新的量子算法，该算法在寻找解决各种优化问题（在大量选择中寻找最佳可能解决方案）的良好解决方案方面，比所有已知的经典算法都快。

到目前为止，还没有经典算法能够取代这种名为 decoded quantum interferometry (DQI) 的新算法。Reichman University 的数学家 Gil Kalai 说道，这是“量子算法的一项突破”，他同时也是量子计算领域一位著名的怀疑论者。量子算法的报告会让研究人员感到兴奋，部分原因是它们可以启发关于难题的新思路，部分原因是，尽管围绕量子机器的讨论沸沸扬扬，但尚不清楚哪些问题实际上会从中受益。一种在优化任务上优于所有已知经典算法的量子算法，将代表着在利用量子计算机潜力方面迈出的重要一步。

量子算法能够提供优于最先进算法的速度优势，这在很大程度上仍然是一个悬而未决的问题。

“我对此感到兴奋，”荷兰国家数学和计算机科学研究所 CWI 的理论计算机科学家 Ronald de Wolf 说道，他没有参与这种新算法的研究。但他同时警告说，研究人员最终仍有可能找到一种同样出色的经典算法。而且由于缺乏量子硬件，他们还需要一段时间才能凭经验测试这种新算法。

加州大学伯克利分校的计算机科学家 Ewin Tang 说道，这种算法可能会激发经典方面的新工作，她十几岁时就因创建与量子算法相匹配的经典算法 而声名鹊起。她说，这些新主张“非常有趣，以至于我会告诉经典算法领域的人：‘嘿，你应该看看这篇论文，并研究这个问题。’”

前进的最佳方式？

当经典算法和量子算法竞争时，它们通常在优化的战场上竞争，优化领域专注于寻找解决棘手问题的最佳方案。研究人员通常专注于可能的解决方案数量随着问题变大而爆炸性增长的问题。送货卡车在三天内访问 10 个城市的最佳方式是什么？您应该如何包装后面的包裹？解决这些问题的经典方法，通常涉及以巧妙的方式筛选可能的解决方案，但很快变得难以维持。

DQI 解决的具体优化问题大致如下：给定一张纸上的一组点。您需要提出一个经过这些点的数学函数。具体来说，您的函数必须是多项式——变量的组合，变量被提高到整数指数并乘以系数。但是它不能太复杂，这意味着幂不能太高。这会为您提供一条弯曲的线，该线在页面上移动时会上下摆动。您的工作是找到接触最多点的摆动线。

这种问题的变体以各种形式出现在计算机科学中，尤其是在错误编码和密码学中——这些领域专注于安全和准确地编码传输的数据。DQI 的研究人员基本上认识到，绘制更好的线类似于将嘈杂的编码消息移动到其准确含义的附近。

但所有这些都是后来的事。当 DQI 背后的研究人员开始研究他们的算法时，他们甚至都没有考虑到这个问题。

一个被解码的问题

斯蒂芬·乔丹 Stephen Jordan 帮助提出了一种量子方法来解决某些问题，这种方法比任何经典方法都更好——到目前为止。 Courtesy of Stephen Jordan

“对于一个以目标为导向的研究人员来说，从陈述问题开始，然后调查量子算法是否可以比经典算法更快地解决它，这将是完全合理的，”Google Quantum AI 的物理学家 Stephen Jordan 说道，他是 DQI 的主要架构师之一。“当然，对我们来说，事实并非如此。我们是通过一种倒退和迂回的路线来实现的。”

Jordan 于 2023 年开始了这条路线，当时他加入了 Google，并发现他将与 Google 的物理学家 Eddie Farhi 合作，他的工作长期以来一直专注于优于经典算法的量子算法。（Farhi 曾经是 Jordan 在麻省理工学院的博士生导师。）Jordan 知道，在 2014 年，Farhi 通过思考能量对优化问题进行了量子攻击，较低的能量对应于更好的解决方案。对于 Farhi 来说，能量将优化与量子物理学联系起来。

但 Jordan 想要做一些不同的事情。他转向了量子物理学中内置的另一个概念——将一切都视为波。使用一种名为 quantum Fourier transform 的数学工具，Jordan 找到了一种方法将对已知的一类优化问题的所有潜在答案转化为量子波。通过这样做，他可以操纵量子系统，使更大的波（以更高的量子幅度形式）对应于更好的解决方案。

但仍然存在一个必须克服的巨大挑战。在量子系统中，问“什么幅度最大？”并不像识别海滩上最大的波浪那么简单。量子环境非常复杂，而且不清楚如何识别与最佳解决方案相对应的量子幅度。

经过多次失败的尝试，Jordan 取得了一项突破：选择最佳解决方案的过程原来类似于消除编码消息中的错误的过程，这被称为解码。这是计算机科学中一个经过充分研究的领域，其中充满了 Jordan 可以探索的技术。通过将优化问题转化为量子问题，然后将解码镜头应用于它，他偶然发现了一种开发量子算法的新方法。

最佳线

Jordan 与同样在 Google 工作的 Noah Shutty 一起，开始测试解码方案，看看它们在各种优化问题上与经典算法的相比表现如何。他们既需要正确的方法，也需要一个适合该方法的问题。“事实证明，经典算法很难击败，”Jordan 说道。“经过几个月的尝试，我们仍然没有为量子领域取得任何胜利。”

但最终，两人发现了一种在 20 世纪 60 年代首次引入的解码算法，用于查找和修复编码消息中的单个错误。找到那个问题是关键。“当我们进行调查时，我们似乎几乎立即取得了成功，”Jordan 说道。最终，他们找到了一个问题和一种方法，它们共同看起来像是一个 quantum speedup。

当然，这并不意味着它是万无一失的。“也许有一些经典方法可以有效地复制你的整个方法，”Jordan 说道。“这种去量子化并不总是显而易见的。”

获得信心

为了消除这些担忧，他们咨询了编码理论专家 Mary Wootters（也是 Shutty 在斯坦福大学的前博士生导师）。她仔细搜索了任何已知的经典算法，这些算法可能与他们的 quantum speedup 相匹配。优势依然存在。该团队的检查同样表明，它将继续存在。“他们做了应有的尽职调查，”Tang 说道。

在这一分析的支持下，他们更仔细地研究了他们正在解决的优化问题。Jordan 曾担心它可能太小众，没有更广泛的应用，但 Shutty 认识到，这种解码问题是加密和其他领域中众所周知且有用的问题的变体。

相关文章：

  1. 物理学家终于找到了一个只有量子计算机才能解决的问题

  2. 三十年后，量子分解的速度得到了提升

  3. 量化量子性的探索

  4. 是什么让量子计算如此难以解释？

Jordan 承认，如果没有足够大的量子机器，DQI 仍将是一项理论突破。“DQI 无法在当今的量子计算机上运行，”他说。但他们仍在前进。自从该小组去年 8 月发布他们的工作以来，他们已经将 DQI 的应用范围扩展到超出原始问题之外，扩展到更广泛的优化问题类别，其中包括更多这些“最佳路径”问题的案例。

Jordan 说道，到目前为止，他预计 DQI 也可以在这些问题上击败经典算法。

目前，量子社区仍然兴高采烈。“找到能够显示出优于经典算法的量子算法是过去三十年来一项非常令人兴奋的工作，而且显示出这种优势的明确算法的数量并不多，”Kalai 说道。“因此，每一种新算法都是庆祝的理由。”

分享这篇文章 Facebook [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/twitter.com/share?url=https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/&text=Quantum+Speedup+Found+for+Huge+Class+of+Hard+Problems&via=QuantaMagazine) Copied! Copy link (opens a new tab) Email Pocket Reddit Ycombinator [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/bsky.app/intent/compose?text=https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/) Newsletter 将 Quanta Magazine 发送到您的收件箱 立即订阅 近期新闻通讯 By Stephen Ornes Contributing Writer March 17, 2025 View PDF/Print Mode algorithms computational complexity computer science cryptography quantum computing All topics (opens a new tab) 分享这篇文章 Facebook [] (https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/https:/twitter.com/share?url=https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/&text=Quantum+Speedup+Found+for+Huge+Class+of+Hard+Problems&via=QuantaMagazine) [Copied! Copy