量子算法：Shor 与 Grover 之后的软件边界

量子计算有两个最著名的算法：Shor 算法（1994）能在多项式时间内分解大整数，打破 RSA；Grover 算法（1996）能对无序数据库搜索给出二次方加速（$O(\sqrt{N})$ vs 经典 $O(N)$）。这两个结果让很多人相信：量子计算机一旦成熟，就能"解决经典计算机无法解决的一切"。

这是严重的高估。量子优势的边界，比想象中细得多。

破除误解：量子计算机不是"万能加速器"#

量子计算机不是比经典计算机快的同类机器，而是一种利用不同物理原理运算的机器。它在某些结构上拥有深刻优势，在大多数任务上与经典计算机性能相当甚至更差。

还有一个更顽固的科普误区值得专门点破："量子计算机同时尝试所有答案"是错的。 一个 $n$ 量子比特的系统确实可以处于 $2^n$ 个基态的叠加，但你无法直接读出这个叠加——测量只会以一定概率坍缩到其中一个结果。量子算法的全部技巧，恰恰在于设计干涉（interference）：让错误答案的概率幅相互抵消、正确答案的概率幅相互增强，从而在最后一次测量时大概率读到对的答案。Shor 算法之所以厉害，不是因为它"并行试所有因子"，而是因为它用量子傅里叶变换把待求的周期信息编码成一个能被干涉放大的结构。没有这种巧妙的干涉设计，叠加本身一文不值——这也正是为什么量子优势只存在于极少数有特殊数学结构的问题上。

关键区分：

指数级加速（Shor 算法、量子傅里叶变换）：只适用于具有特定数学结构（如周期性）的问题。这类加速是真实的，不可否认，但适用范围极窄。

二次方加速（Grover 算法）：适用范围更广，但二次方加速在实践中的价值远比公式上诱人的"$\sqrt{N}$"要弱。原因有两层：其一，量子纠错本身有巨大开销，Babbush 等（Google Quantum AI, 2021）的分析指出，在早期容错量子计算机上，仅有二次方加速的算法几乎不可能真正跑赢经典——纠错的常数因子开销会吃掉这点优势，除非纠错技术大幅改进；其二，在 NISQ 硬件上，构造和运行"预言机"（oracle）每一步的代价，往往就抵消了 Grover 迭代省下的那点步数。换言之，Grover 加速是真实的渐近优势，却很可能在可预见的硬件上没有实用意义。

无加速（排序、大多数机器学习）：排序有经典 $O(n \log n)$ 下界；对于量子机器学习，Aaronson 等研究者已经证明，很多被宣称的量子 ML 优势，在经典计算机有同等数据访问权的条件下会消失。

变分量子算法：NISQ 时代的现实路线#

当代量子硬件处于"嘈杂中等规模量子"（NISQ，Noisy Intermediate-Scale Quantum，Preskill 2018 年提出的术语）时代：量子比特数在几十到几百，错误率仍然很高，没有完整的量子纠错。Shor 算法在这个条件下根本无法运行。

面对这个现实，研究者转向了变分量子算法（VQA）：

核心思路：设计一个参数化量子电路（ansatz），用经典优化器（梯度下降等）调整参数，使量子电路输出最小化某个损失函数。

代表算法：

变分量子本征求解器（VQE，Peruzzo 等, 2014）：用量子电路估算哈密顿量的基态能量，适合量子化学计算。

量子近似优化算法（QAOA，Farhi 等, 2014）：用于组合优化问题（如 MAX-CUT）。理论上可能有优势，但目前尚未在实际问题上超越经典算法。

VQA 的前途充满争议：

支持者：这是当前硬件下唯一可能在化学模拟等领域展示实用优势的路线，值得探索。

批评者：VQA 遇到了"贫瘠高原"（Barren Plateau）问题——随着电路深度增加，梯度指数消失，优化极其困难；且 2022-2024 年间多项工作表明，VQA 的经典仿真难度可能并不高于量子版本（即经典算法也许可以同样高效地完成同样的任务）。

量子化学：最有希望的近期应用#

在有错误纠正的量子计算机上，量子化学是目前学界共识最接近"可行量子优势"的领域：

模拟分子电子结构——即求解薛定谔方程找到分子基态——对于足够大的分子，经典计算资源需求指数增长。一个量子系统在另一个量子系统（量子计算机）上模拟，理论上只需多项式资源。

具体应用包括：催化剂设计（工业合成氨、电池电极材料）、药物靶点的精确能量计算、新型材料的电子结构预测。

现实挑战：即使是小分子（如 FeMo-co，固氮酶活性位点），精确量子化学计算也需要数百到数千个逻辑量子比特——而非物理量子比特。实现这个规模需要大量量子纠错，目前距离还有相当距离（见quantum-error-correction条目）。

Babbush 等（Google Quantum AI）在 2023-2024 年的一系列论文中，对容错量子计算机上的量子化学计算资源需求做了更精确的估算，部分修正了此前过于乐观的预期，但仍认为量子化学是最有望实现实用优势的领域之一。

量子优势的软件边界#

John Preskill（Caltech）和 Scott Aaronson（UT Austin）等研究者长期致力于厘清量子优势的真实边界：

BQP 与 PH 的关系：量子计算机能高效解决的问题类（BQP）与多项式层级（Polynomial Hierarchy, PH）的关系，是计算复杂性中的核心开放问题。如果 BQP 完全包含于 PH，则量子计算机的优势有严格限制。

量子采样问题：Google Sycamore（2019）和后续的玻色子采样实验，展示了在随机电路采样这个人工设计的问题上的量子优越性。但这不是任何实用任务——它只是一个对量子计算机容易、对经典计算机（据信）很难的问题。此后经典算法不断改进（如 Pan et al. 2022 年的高效经典仿真），缩小了这个"优越性"的差距。

整合证据：Bravyi、Gosset 与 König（Science 2018）证明，在某类特定的"浅层电路"（shallow circuit，即固定常数深度的并行电路）问题上，量子电路相对经典有无条件可证明的优势——这里"无条件"很关键：它不依赖 P≠NP 之类的未证假设，而是严格数学定理。2020 年的后续工作（Bravyi 等, Nature Physics）进一步证明，即使量子电路被限制为三维几何局部门、且带有噪声，这一优势依然成立。这是少数几个有严格理论证明（不是猜测）的量子优势例子之一，但要注意它针对的是浅层电路这一受限模型，而非通用量子计算。

后量子密码学：算法挑战应对#

不需要等量子计算机真正破解 RSA，后量子密码学的迁移已经在进行：

NIST 于 2024 年 8 月发布的后量子标准（ML-KEM、ML-DSA、SLH-DSA），基于格密码学和哈希函数，对当前最好的量子算法也难以有效攻击（见public-key-rsa条目）。

这是量子算法研究"已经改变世界"的罕见案例——不是因为量子计算机已经存在，而是因为 Shor 算法已经被证明可以高效破解 RSA，所以全球密码基础设施需要提前迁移。

代价与争议#

过度宣传的历史：量子计算领域有大量被后来研究否定或削弱的"量子优势"宣称。D-Wave 的量子退火机器长期被质疑是否有真实量子效应；多种量子机器学习算法被发现有经典等价物。区分"已证明的量子优势"和"未经验证的量子优势"，是学界的持续工作。

容错时代的时间表：实现真正有用的 Shor 算法（分解 2048 位 RSA），需要约数百万个高质量物理量子比特。这一目标的时间线，各机构估计从 2030 年代到 2040 年代不等，而且基于当前技术轨迹的假设——并非保证。

NISQ 算法的价值：是否存在任何 NISQ 算法在任何实际应用上能优于经典算法，仍然是一个开放问题。每年都有新的声明，也都在更精细的分析后被质疑。

未知的边界#

• 是否存在除 Shor 和 Grover 之类之外的新"量子基本算法"，带来当前未知的量子优势？
• VQA 和 NISQ 算法是否会在容错量子计算机可用之前找到实际应用，还是这只是一条死胡同？
• 量子优势在量子化学之外是否有其他可靠的实用领域？优化问题（量子退火等）的实际优势目前存疑。
• 如果量子计算机时间表持续推迟，量子软件和算法研究的产业生态能否持续？
• BQP 与 PH（多项式层级）的关系是否会有新的理论突破，为量子优势划出更清晰的数学边界？
• "贫瘠高原"问题是否有根本性的解决方案，还是 VQA 注定在特定规模以上失效？这关系到整个 NISQ 路线的长期价值。
• 量子机器学习中，去除数据加载的量子优势（"去量子化"），是否说明其他类型量子算法也有经典仿真等价物？这是 2024-2025 年仍在激烈争论的方向。
• 量子模拟（用量子计算机模拟其他量子系统）是费曼最初的量子计算构想，目前是最被广泛认可的近期应用方向之一，但具体哪些化学或材料问题能在实践中率先获得量子优势，仍无定论。

跨域连接#

• RSA 公钥密码：这是量子算法唯一已经改变现实的地方，而且是在硬件到位之前。因为"先记录后解密"成立，迁移不能等到机器造出来才开始——今天被截获的密文，可以留到未来再解。所以后量子标准化是提前布局，而非应对已发生的攻击。
• 量子计算理论：必须分清两类主张。在受限的浅层电路模型上，量子相对经典的优势有严格证明，不依赖任何未证假设；而通用意义上的量子优势仍是猜想。至于采样类的优越性宣称，其分量取决于对最优经典算法的估计，而这个估计一直在被改写。
• 量子化学：目前共识最集中的应用方向。经典方法记录多电子态所需资源随体系增大而指数增长，量子模拟原则上只需多项式资源。但门槛写在逻辑比特而非物理比特上——中间隔着纠错的巨大开销，这正是资源估算不断被修正的原因。
• 最优化：组合优化被反复宣称是近期出口，实际证据不足。平方根级的搜索加速在纠错开销面前很可能被吃掉，而变分线路遇到梯度随深度指数消失的困难；不少被宣称的加速，在经典算法获得同等数据访问权后也随之消失。
• 量子退相干：噪声不是工艺瑕疵，而是系统与环境纠缠的必然结果。它给当前硬件划出一条电路深度的硬上限：超过这个深度，信号被噪声淹没。这条上限决定了为何深电路算法只能等纠错，而不能靠"再优化一点"提前跑起来。

参考文献#

• Shor, P. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5), 1997.
• Preskill, J. Quantum Computing in the NISQ Era and Beyond. Quantum 2, 79 (2018).
• Aaronson, S. Read the Fine Print. Nature Physics 11, 291–293 (2015). （量子机器学习宣称的批判性分析）
• Babbush, R. et al. Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage. PRX Quantum 2, 010103 (2021).
• Bravyi, S., Gosset, D. & König, R. Quantum Advantage with Shallow Circuits. Science 362, 308–311 (2018). （浅层电路上无条件量子优势的原始证明）
• Bravyi, S. et al. Quantum Advantage with Noisy Shallow Circuits. Nature Physics 16, 1040–1045 (2020). （上述结果在带噪声、几何局部约束下的推广）