谷歌开发解码量子干涉测量算法，为海量优化难题提供指数级加速

量子计算和经典计算的竞争由来已久。研究人员不断寻找量子算法能够显著优于经典算法的问题，这些努力构成了量子计算领域进步的主要动力。

2025 年 3 月，D-Wave 团队在 Science 期刊发表研究，声称使用量子退火处理器在模拟量子动力学方面实现了超越经典计算的能力。他们研究了二维、三维和无限维自旋玻璃系统的量子退火动力学，并指出经典算法无法在合理时间内达到相同精度。

这一声明很快受到挑战。瑞士洛桑联邦理工学院的研究者开发了时变变分蒙特卡洛方法（arXiv:2503.08247），而 Flatiron 研究所的团队则展示了张量网络与信念传播结合的方法（arXiv:2503.05693）。两个团队均证明，经典算法不仅能匹配，甚至能超越量子退火器的结果。

这种情形其实在量子计算历史上一直反复出现：量子算法宣称突破，而后经典算法迅速赶上。这种竞争促进了两个领域的进步，但也让人怀疑量子计算是否真能在实用问题上提供无可争议的优势。不过，2024 年由谷歌 Quantum AI 团队提出的一种量子算法——解码量子干涉测量（DQI，Decoded Quantum Interferometry）算法似乎打破了这一循环，展示了一种在数学上可证明的量子加速，这一点至今未被经典算法所匹敌。

将经典问题空间转化为量子概率振幅空间

与其他量子算法不同，DQI 采用了全新的技术路径，这也是其能够实现真正量子加速的关键。传统量子优化算法如量子退火通常从能量视角出发，将最优解对应到最低能量状态。这种方法虽然直观，但往往难以证明其在计算复杂性上的优势。而 DQI 则基于波动观点，利用量子物理学的波动性质来解决优化问题，这种范式转变使得量子加速的数学证明成为可能。

DQI 的核心机制可以详细分解为几个关联紧密的步骤。首先，算法使用量子傅里叶变换将优化问题的所有可能解决方案映射为量子波。这不仅是一个数学转换，更是一个物理概念的转变——将经典问题空间转化为量子概率振幅空间。在这个空间中，每个可能的解对应一个量子态，这些态的叠加构成了问题的完整表示。

转换完成后，DQI 在量子空间中通过特殊的量子门操作调整这些波的振幅，这一过程使得对应更优解决方案的状态获得更高的量子振幅。量子门操作的序列依赖于具体问题的结构，但其目的始终是强化那些代表更好解的量子态。这种调制过程在传统量子计算中并不常见，但这也正是 DQI 的创新之处。

最后，也是最具突破性的部分，DQI 应用了源自经典通信理论的解码技术。在通信中，解码用于从噪声信号中恢复原始信息；在 DQI 中，解码成为了从复杂量子状态中提取最优解的关键工具。这种跨领域的方法融合是 DQI 最显著的创新点——它将通信理论的解码原理与量子计算相结合，创造了一种全新的算法范式。

具体而言，DQI 采用的解码技术源自 20 世纪 60 年代开发的用于找出并修复编码消息中单个错误的算法。这种解码方法在 DQI 中被重新构想，用于从量子振幅分布中识别“正确”的解。这一步骤解决了量子计算中的一个核心挑战——如何有效地从量子叠加态中提取有用信息而不丧失量子优势。

DQI 针对的优化问题是一类在数学上被称为“低度多项式拟合”的问题：给定一组数据点，需要找到一个不过于复杂（度数有限）的多项式函数，使其通过尽可能多的点。这个问题看似简单，但实际上与密码学、错误纠正码以及机器学习中的核心问题有着深刻联系。这种问题的数学表述可以看作是在一个高维空间中找到最接近给定点集的低复杂度曲面，这是一个计算复杂性较高的任务。

从技术角度看，DQI 实现了这一任务的指数级加速。经典算法需要逐一评估可能的多项式或使用复杂的近似方法，其运行时间随问题规模呈多项式或更高增长。相比之下，DQI 利用量子叠加态同时处理所有可能的多项式，然后通过量子干涉和解码提取最优解，理论上实现了指数级加速。

充满意外的开发过程

这项成果的主要作者，来自 Google Quantum AI 的物理学家 Stephen Jordan 表示，开发 DQI 的过程其实充满了意外。

最开始，这项研究的目标实际上并不明确，它的发现源于团队对量子波动性质的基础探索，这种探索最终导向了实用的算法突破。

Jordan 在 2023 年加入 Google 时，开始与量子算法领域的资深研究者 Eddie Farhi 合作。Farhi 之前的研究主要基于能量视角，将优化问题映射为能量最小化问题。但 Jordan 决定探索不同路径，转向量子物理学的波动性质。这种方法选择不仅是技术上的区别，更反映了对量子计算本质的不同理解。

Jordan 最初的思路是将量子傅里叶变换应用于优化问题。量子傅里叶变换是量子计算中的基本操作，能够在指数级大小的空间中高效地转换数据表示。通过这种变换，Jordan 将问题解空间表示为量子波的叠加，理论上更优的解对应更大的波（更高的量子振幅）。这一思路在概念上优雅，但实际实现面临着巨大挑战。

在量子系统中，直接测量“哪个振幅最大”并不像观察海滩上最高的波那么简单。量子测量会导致波函数坍缩，单次测量只能获得一个可能的结果，而非完整的振幅分布。这一基本困难使得从量子状态中提取最优解成为一个非常复杂的任务。

经过多次失败尝试后，Jordan 取得了重大突破。他意识到，从量子状态中选择最佳解的过程与通信系统中剔除编码消息错误的过程在数学上存在深刻相似性。这一认识将他引向了通信理论和错误纠正领域，这些领域拥有丰富的技术可供探索。通过将优化问题转换为量子问题，并应用解码的概念框架，Jordan 发现了发展量子算法的新途径。

于是 Jordan 开始与 Google 的同事 Noah Shutty 合作测试各种解码方案，评估它们在不同优化问题上与经典算法的竞争力。最初的结果并不理想，Jordan 回忆道：“经典算法很难被击败。经过几个月的尝试，我们仍然没有为量子算法取得任何胜利。”

关键的转折点出现在他们发现了一种特定的解码方法，这种方法最初在 20 世纪 60 年代被开发用于通信中的错误纠正。将这种解码方法与量子算法结合，他们几乎立即发现了量子加速的证据。这种结合不仅提供了技术上的解决方案，也建立了两个看似不相关领域之间的理论桥梁。

为了确保这一发现的可靠性，他们咨询了编码理论专家 Mary Wootters（她恰好是 Shutty 在斯坦福大学的前博士导师）。她进行了全面的分析，寻找可能与 DQI 性能匹敌的已知经典算法。这种严格的评估对于验证量子优势至关重要，因为许多声称的量子优势最终被证明可以被巧妙的经典算法复制。在这种严格审查下，DQI 的优势依然存在，这增强了研究团队的信心。

“每一种新算法都是庆祝的理由。”

从理论层面来说，DQI 的核心价值在于它提供了一个数学上可证明的量子加速案例。与很多量子算法不同，DQI 的加速不依赖于启发式方法或实验观察，而是基于严格的计算复杂性分析，也就是我们前面所提到的，对于低度多项式拟合问题，DQI 在时间复杂度上相比最佳已知经典算法实现了指数级改进。

这种理论上的确定性是量子计算研究中的黄金标准，但很少有算法能够达到这一标准。量子计算的知名怀疑者，Reichman 大学的 Gil Kalai 对此高度评价：“寻找显示优于经典算法的量子算法是过去三十年来一项非常令人兴奋的工作，而显示出这种优势的确定算法数量并不多。因此，每一种新算法都是庆祝的理由。”

DQI 的理论基础建立在几个关键要素上：量子叠加原理允许同时处理指数级数量的可能解；量子干涉可以增强对应优解的振幅；解码技术提供了从这种增强状态中高效提取信息的方法。这些要素相互配合，形成了一个在理论上健全且实际可行的量子算法。

而这种算法的应用范围也远远超过了初始问题。研究团队已将其扩展到更广泛的优化问题类别，包括：

1. 密码学：在某些密码系统的分析中，多项式重构是核心挑战。

2. 错误纠正：在通信系统中，找到最佳编码方案涉及类似的优化问题。

3. 机器学习：某些模型训练和特征选择问题可以重新表述为 DQI 擅长解决的格式。

但其实际应用目前还面临硬件限制。Jordan 坦言：“DQI 无法在现有量子计算机上运行。”现有量子处理器的量子比特数量、相干时间和错误率都无法支持完整的 DQI 实现。

此外，DQI 的理论假设了理想的量子操作和测量，实际实现中的噪声和不完美会影响算法的性能。研究人员需要开发适应现实量子硬件限制的修改版算法，这可能涉及量子噪声缓解技术和混合量子-经典方法的结合。

尽管存在这些挑战，DQI 仍然代表了量子算法研究的重要里程碑。即使在实际硬件实现之前，它提供了一个有力的概念证明，表明量子计算在某些问题上确实可以提供数学上可证明的计算优势。这种理论上的确定性为量子计算的实用价值提供了有力支持。

参考资料：

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

2.https://arxiv.org/abs/2408.08292

3.https://www.science.org/doi/10.1126/science.ado6285

运营/排版：何晨龙