在令人着迷的计算机科学领域，解决复杂问题是一场不断的旅程，常被比作攀登险峰。采用经典方法的研究者与探索量子潜力的科学家之间的竞赛激烈且充满波折。每当有量子突破发布，经典社区便迅速寻找方法以匹敌甚至超越这一性能。这是一场推动技术创新的拔河比赛。
永恒的对决：经典 vs. 量子
长期以来，这场竞争几乎以虚拟平局告终。那些承诺速度优势的量子算法，往往很快就会被新的经典方法追赶上，取得类似结果。我最近看到一个例子：一篇关于量子速度提升的论文发表在《科学》杂志上，但随即被两个不同团队质疑，他们演示了如何在经典计算机上完成类似计算。这种动态展示了几十年来经典算法的坚韧与巧妙。
然而，最近的发展似乎打破了这一格局，至少暂时是如此。一篇发表在科学预印本网站 arxiv.org 的论文描述了一种看似令人信服且更实用的量子加速。这种新算法被称为解码量子干涉仪（Decoded Quantum Interferometry，简称 DQI），它在寻找一大类优化问题的良好解法时，速度超过所有已知经典算法。这是该领域令人振奋的时刻。
DQI 有何突破之处？
DQI 的独特之处在于它针对那些对经典计算机来说异常困难的优化问题。优化问题通常涉及在海量可能方案中找到最佳方案。比如物流问题，确定货车拜访多个城市的最优路线，或是如何以最佳方式包装物品。随着问题规模增长，潜在解的数量激增，尽管经典方法常用智能迭代，依然很快变得不可行。
DQI 具体解决的问题是找到一个低复杂度的数学函数（多项式），使其通过给定点集中的最多点。这个挑战在计算机科学多个领域都有体现，比如代码生成、差错编码和密码学。DQI 方法的美妙之处在于其开发者意识到，寻找理想“波浪线”类似于解码嘈杂信息，将其还原为原本含义。这一与解码理论的意外交叉是关键所在。
DQI 背后的意外旅程
有趣的是，DQI 的开发最初并非聚焦于优化问题。Google Quantum AI 的物理学家、DQI 主要架构师之一 Stephen Jordan 讲述了这一发现的“曲折”历程。他于2023年加入 Google，与量子算法先驱 Eddie Farhi 合作。Farhi 探索基于能量概念的优化（更低能量对应更优解），而 Jordan 采取不同路线，专注于量子物理的波动特性。
利用强大的数学工具——量子傅里叶变换，Jordan 找到了一种将一类优化问题可能解转化为量子波的方法。他发现可以操控量子系统，使得波幅更大的波对应更优解。最大障碍在于如何识别这种复杂量子系统中的大幅度波。意想不到的解决方案来自于对错误编码消息的差错修正过程的类比，这一在计算机科学中被称为解码的成熟领域。
这一发现使 Jordan 和同样来自 Google 的 Noah Shutty 能够利用解码技术来开发算法。经过多次尝试及与经典算法的反复对比，他们最终找到了一种源自上世纪60年代、专门纠正单个错误的解码方式，完美适用于所选优化问题。“几乎一开始就获得成功，”Jordan 回忆这次突破时说道。专家 Mary Wootters 的验证也表明，对于该问题，没有已知的经典算法能匹敌 DQI 的速度。这是量子计算领域的重大进展。
DQI 面临的挑战与展望
尽管振奋人心，DQI 仍面临实际挑战。Jordan 承认，现阶段算法因复杂度和硬件需求，无法在目前可用的量子计算机上运行。量子技术仍处于发展阶段，构建能够大规模执行类似 DQI 这类复杂算法的设备，是一项庞大的工程挑战。此外，经典算法社区仍在不断努力。正如因创造能与量子算法匹敌的经典算法闻名的 Ewin Tang 所指出，这次量子突破是对经典研究者探索新路径的号召。健康的竞争推动两者共同进步。
研究永不停歇。自去年八月首次发表以来，研究者已将 DQI 应用扩展到更广泛的优化问题，包括“最短路径”等挑战的变体。Jordan 认为 DQI 在新情境下也将保持领先。量子社区庆祝每一个明确优于经典方法的新算法，因为这类案例相对罕见，并照亮了量子计算真正潜力的道路。
简化对比：经典 vs. 量子（DQI）
| 特征 | 经典算法（复杂优化问题） | 量子算法（DQI） |
|---|---|---|
| 主要方法 | 智能迭代，启发式 | 量子态操控（波动） |
| 特定问题表现（如多项式拟合） | 问题规模大时迅速失效 | 对某类问题展现加速优势 |
| 理论基础 | 数学，计算机科学 | 量子物理，解码理论 |
| 所需硬件 | 传统计算机 | 大规模量子计算机（尚在研发） |
| 当前状态 | 广泛应用，标准稳定 | 理论阶段（依赖未来硬件），充满前景 |
量子优化的潜在应用
- 物流与供应链（车队路径规划）
- 金融（投资组合优化）
- 药物发现（分子模拟）
- 人工智能（模型训练）
- 材料科学（新材料设计）
- 密码学（破译或创建编码）
- 通信网络优化
关于 DQI 和量子算法的常见问题
- 什么是“量子优势”或“量子加速”？ 指量子算法在解决某问题时，速度明显快于任何已知或理论上可能的经典算法。
- DQI 目前有实际应用吗？ 没有，DQI 算法需要尚未具备的大规模量子计算机来运行。这是指向未来潜力的重要理论突破。
- DQI 如何使用“解码”技术？ 它将优化问题转化为量子系统，为寻找最佳解，使用类似于识别和修正编码消息中错误的数学技术。
- 所有优化问题在量子计算机上都会更快吗？ 不一定。量子研究旨在识别那些量子计算较经典高效方法真正优势明显的特定问题类别。
- 什么是“优化问题”？ 指的是在大量可能方案中，寻求某种最优结果（如最大收益、最低成本、最短路径等）的所有问题，通常伴随一定限制条件。
依我看，DQI 的出现再次提醒我们量子计算巨大的潜力。尽管距离能够充分发挥该潜力的机器仍有距离，但每一个像 DQI 这样的新算法都验证了该领域研究的价值，并让我们一瞥未来——今天尚无解的复杂问题，也许将被高效解决。经典与量子方法之间的合作与竞赛，将继续驱动这场演进。
你如何看待经典算法与量子算法之间的这场竞赛？欢迎在下方留言分享！