量子算法：一个行动呼吁

原文：https://quantumfrontiers.com/2025/04/20/quantum-algorithms-a-call-to-action/ 

作者：robbieking1000 

译者：Kurt Pan

量子计算正处于一个特殊的境地。从技术层面来看，经过数十亿美元的投入和数十年的研究，量子计算机的研发已接近尾声。然而，关于量子计算机，人们最常问的问题依然和二十年前一样：它们到底有什么用？诚实的答案揭示了一个显而易见的秘密：我们还不完全清楚。对于像我这样的理论家来说，这是一个机遇，一个行动的号召。

技术动力

假设几十年后我们还没有量子计算机。原因是什么？我们不太可能遇到一些难以克服的工程障碍。量子纠错的理论基础是坚实的，一些平台正在接近或低于纠错阈值（ 哈佛 、 耶鲁 、 谷歌 ）。实验人员相信，今天的技术可以扩展到 100 个逻辑量子比特和个门 ——即“超级量子时代” 。如果人类在未来几十年投入 1000 亿美元，我们很可能能够建造一台量子计算机。

• https://www.nature.com/articles/s41586-023-06927-3
• https://www.nature.com/articles/s41586-023-05782-6
• https://www.nature.com/articles/s41586-024-08449-y
• https://dl.acm.org/doi/abs/10.1145/3723153

量子计算可能失败的一个更令人担忧的原因是，缺乏足够的激励来证明在研发和基础设施上如此大规模的投入是合理的。我们不妨将其与核聚变进行比较。与量子硬件一样，它们也面临着具有挑战性的科学和工程难题。然而，如果一个核聚变实验室能够成功建造核聚变反应堆，其应用前景将不言而喻。但量子计算并非如此——它就像一把寻找钉子的大锤。

尽管如此，业界对量子计算的投资目前正在加速 。为了保持这一势头，关键在于将投资增长和硬件进步与算法能力相匹配。探索量子算法的时机已到。

赋能理论家

理论研究具有前瞻性和预测性。像杰弗里·辛顿这样的理论家奠定了当前人工智能革命的基础。但几十年后，随着计算硬件的丰富，人工智能已变得更加依赖于经验。我期待量子硬件能够达到丰富状态的那一天，但那一天尚未到来。

如今，量子计算已成为理论家们拥有非凡影响力的领域。彼得·肖尔（Peter Shor）的几页数学著作激励了成千上万的研究人员、工程师和投资者投身于该领域。或许，阅读此博客的某人再写几页，就能为该行业开创一个改变世界的未来。数学拥有如此巨大影响力的领域并不多见。整个实验学家、工程师和企业界都在向理论家们寻求灵感。

挑战

传统上，人们认为理想的量子算法应该具备三个特征。首先，它应该是可证明的正确性，从而保证可靠地执行量子电路能够实现预期结果。其次，底层问题应该是经典难题——量子算法的输出在计算上难以用经典算法复制。第三，它应该是实用的，具有解决现实世界中相关问题的潜力。Shor 算法几乎满足了所有这三个标准。然而，绝对地要求这三个标准可能是不必要的，甚至可能适得其反。

可证明的正确性至关重要，因为目前我们还无法在硬件上大规模地对量子算法进行实证测试。但是，对于经典难度，我们应该要求多大程度的证据呢？目前，如果不解决像 P vs NP 这样的重大开放性问题，就无法获得经典难度的严格证明，但存在一些更“软”的证明形式，例如归约为已充分研究的经典困难假设。

我认为，我们应该用一种更务实的方法取代“可证明困难”这一理想：量子算法应该以超二次方的加速比超越已知最佳的经典算法，同时产生相同的输出 。[1] 强调可证明的经典困难可能会无意中阻碍新量子算法的发现，因为真正新颖的量子算法可能会引入一个与现有经典困难假设根本不同的新假设。提出和打破新假设的反复过程是一个富有成效的方向，有助于我们确定量子优势所在。

直接用量子算法来解决现有的现实问题也可能徒劳无功。具有量子优势的基础计算任务非常特殊，我们目前的例子很少，但它们必然为任何最终的量子应用奠定基础。我们应该探索更多这样的基础任务，并将它们与实际应用进行匹配。

话虽如此，区分哪些量子算法有朝一日能为实际相关的计算提供基础，哪些则不会。在现实世界中，除非计算可验证或至少可重复，否则计算毫无用处。例如，考虑一个计算物理可观测量的量子模拟算法。如果两台不同的量子计算机运行模拟并得到相同的答案，则可以确信这个答案是正确的，并且它对世界做出了稳健的预测。有些问题（例如因式分解）很容易用经典方法验证，但我们可以把标准设得更低：一个有用的量子算法的输出至少应该可以被另一台量子计算机重复。

第四个至关重要的要求往往被忽视，但又极其微妙，可以用下面的试金石来概括：如果明天给你一台量子计算机，你能实现你的量子算法吗？为了做到这一点，你不仅需要一个量子算法，还需要一个运行该算法的输入分布。因此，经典算法的难度必须在该输入分布的平均情况下进行判断，而不是在最坏情况下。

本节最后，我将特别提醒大家，对于输出为可观测量期望值的量子算法，需要谨慎考虑。这些方案未能达到经典难度的一个常见原因是，期望值会随着输入的分布呈指数级集中。当这种情况发生时，一个简单的经典算法只需输出每个输入的集中值（典型值）即可复制量子结果。为了避免这种情况，我们必须寻找量子电路集合，其期望值会表现出有意义的变化，并且对不同的输入具有敏感性。

我们可以将这些优先事项具体化为以下挑战：

挑战
找到一个量子算法及其输入分布，具备以下特征：
—（可证明正确性）该量子算法具有可证明的正确性。
—（经典困难性）在该输入分布上，量子算法相较于最佳已知经典算法在平均情况下实现超二次加速。
—（潜在实用性）输出结果可验证，或至少可重复。

我们可以根据量子算法的输出形式对其进行分类。首先，有一些用于搜索问题的量子算法，它们生成满足某些约束的比特串。这些约束可以是某个数字的质因数、某个数据集中的植入特征，或者是某个优化问题的解。其次，有一些量子算法可以计算某个值到一定精度，例如某个物理可观测量的期望值。然后，有一些量子性证明，其中涉及一个验证者使用某个隐藏密钥生成测试，并且该密钥可用于验证输出。最后，有一些量子算法可以从某个分布中进行采样。

哈密顿模拟或许是最广为人知的量子实用性来源。物理学和化学中有许多物理量，自然界可以轻松计算，但即使是我们最好的经典模拟也无法企及。量子计算能够直接模拟自然，这让我们有充分的理由相信，量子算法能够计算经典计算困难的物理量。

量子计算机能够帮助我们解答尚未解决的科学问题的例子已经有很多，例如确定哈伯德模型的相图或 FeMoCo 的基态能量。这些无疑具有科学价值。然而，它们只是孤立的例子，而我们更希望找到证据，证明量子可解问题的池子是无穷无尽的。我们能否从强关联物理中汲取灵感，写出一组具体的哈密顿模拟实例，其中存在经典难观测量？这将为量子模拟的持续广泛效用收集证据，也有助于我们理解量子优势的产生地点和方式。

在计算机科学界，已经有很多关于oracle separations的研究，例如welded trees和 forrelation ，这应该能让我们更加相信量子计算机的能力。我们能否以一种在实践中仍然保持经典难度的方式实例化这些oracle？这对于我们通过之前的试金石测试，即为明天运行量子算法做好准备，是必要的。

• https://dl.acm.org/doi/abs/10.1145/780542.780552
• https://dl.acm.org/doi/abs/10.1145/2746539.2746547?casa_token=vSf9GIqdBDcAAAAA:0NK87mBjIZ9TeBCWE-n0ygLXuy3rTEpM9ZUys4_3jiJmE7XdcRiP-6AG4TDmIbVN0VpXg0TOvTXY7w

除了汉密尔顿模拟之外，还有其他几大类量子算法，包括用于线性方程组和微分方程的量子算法 、 用于机器学习的变分量子算法 ，以及用于优化的量子算法 。这些框架有时会附带 BQP 完备性的证明。

• https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.103.150502
• https://www.nature.com/articles/s41467-018-07090-4
• https://arxiv.org/abs/1411.4028

这些宽泛框架的问题在于，它们通常没有指定输入的分布。我们能否找到这些框架中新的输入集合，并表现出超二次方加速比？BQP 完备性表明，人们已经将量子计算的概念转化为一种不同的语言，这使得人们能够将现有的量子算法（例如 Shor 算法）嵌入到你的框架中。但为了发现一种新的量子算法，你必须找到一个不源自 Shor 算法的 BQP 计算集合。

上表表明，单独的采样任务毫无用处，因为它们甚至无法在量子上重复。有人可能会好奇，采样任务是否在某些方面有用。毕竟，经典的蒙特卡罗采样算法在实践中被广泛应用。然而，采样的应用通常使用样本来提取有意义的信息或底层分布的特定特征。例如，蒙特卡罗采样可用于计算贝叶斯推理和统计物理中的积分。相比之下，从随机量子电路获得的样本缺乏任何可辨别的特征。如果一组量子算法生成的样本包含有意义的信号，可以从中提取经典上难以计算的值，那么这些算法将有效地过渡到计算值的类别。

上表还声称量子性证明毫无用处。这并不完全正确——一个潜在的应用是生成可证明的随机性。然而，这类应用通常本质上是密码学的，而非计算性的。具体来说，量子性证明无法帮助我们解决问题，也无法回答那些我们尚不清楚答案的问题。

最后，量子技术在传感与计量 、 通信 、 量子记忆学习以及流媒体等领域的应用前景令人振奋。这些方向都非常有趣，我希望人类量子力学的第二个世纪能够带来各种各样的能力。然而，目前的技术发展势头主要集中在构建量子计算机以获得计算优势，因此，这些领域的突破将产生最直接的影响。

• https://arxiv.org/abs/2501.07625
• https://dl.acm.org/doi/pdf/10.1145/301250.301343
• https://ieeexplore.ieee.org/abstract/document/9719827?casa_token=oEewXN1iaHAAAAAA:w5lHZrJwr8NFRMFzJavfAo8rSLITpyTuoowfWkXFzXEkiNxtuhMOSKMkqIiaeLozZjrHw_OjfQ
• https://dl.acm.org/doi/pdf/10.1145/3618260.3649709

不要太害怕

在年度QIP大会上，每年数百篇论文中只有少数几篇试图推进新的量子算法。考虑到风险，为什么这个数字如此之低？一个常见的解释是，量子算法研究实在太难了。尽管如此，近年来我们还是看到了量子算法的实质性进展。在 2000 年至 2020 年期间，具有实用潜力的端到端提案严重匮乏之后，上表展示了过去五年来的几项突破。

• https://rsvp.duke.edu/event/qip2025/accepted-talks

在盲目乐观和逆来顺受的悲观之间，拥抱使命驱动的心态可以推动我们的领域不断前进。我们应该允许自己采取更具探索性、更大胆的方法：我们可以在尚未研究的问题中寻找量子优势，或者在小数点后三位寻找微妙的信号。取得有意义的进展的门槛比想象的要低，即使是渐进式的进步也同样有价值。别太害怕！

[1] 二次加速很普遍，但由于与量子纠错相关的开销， 不会构成实际量子优势的基础。