量子计算理论

1994 年，美国数学家彼得·肖尔（Peter Shor）发表了一个算法。这个算法可以在多项式时间内分解大整数——而人类目前已知最好的经典算法（普通计算机上运行的算法）需要次指数时间。

这个差距有多大？分解一个 2048 位的 RSA 密钥，最好的经典算法需要数百万年；肖尔算法在一台足够大的量子计算机上，理论上只需要数小时。

整个互联网的加密体系，绝大多数建立在"大整数分解很难"这个假设之上。肖尔算法在理论上把这个基础打碎了——如果足够大的量子计算机被建造出来，今天所有用 RSA 加密的通信都将变得可破解。

这不是科幻小说，而是已被严格证明的数学定理——只是实现它所需的量子计算机尚未存在。

破除误解：量子计算机不是"更快的计算机"#

量子计算机不是靠更快的时钟速度或更多的内存来超越经典计算机的。它建立在一套完全不同的物理原理之上，允许某类特定计算以根本上不同的方式执行。

更准确地说：量子计算机在某些特定问题上具有理论上无法被经典计算机追赶的优势，但在大多数日常计算任务上，它既不快也不慢——它根本不是为这些任务设计的。

量子计算机不能解决图灵机无法解决的问题（在邱奇-图灵论题框架内），它改变的是某些可解问题的复杂度等级，不是可计算性的边界。

现场：1980 年代的思想实验#

量子计算的理论起点，往往被追溯到理查德·费曼（Richard Feynman）1982 年的演讲。费曼是量子物理学家，他注意到：用经典计算机模拟量子系统需要指数级资源——模拟 $n$ 个量子粒子，需要 $2^n$ 个经典比特来存储量子态的全部信息。

他的问题是：如果我们用量子系统来模拟量子系统，会不会根本上更高效？

1985 年，大卫·多伊奇（David Deutsch）给出了量子计算机的第一个严格定义——量子图灵机（Quantum Turing Machine），并证明它能高效完成一类经典计算机无法高效完成的任务（尽管他构造的那个任务是人工的，不具有实际意义）。这是量子计算理论的奠基时刻。

此后十年是一条清晰的递进链。1992 年，多伊奇与约萨（Richard Jozsa）给出第一个在"神谕"（oracle，即黑盒查询）模型下可证明的指数级量子优势——问题本身是人为设计的，但它第一次严格展示了量子干涉能做到确定性经典计算做不到的事。1993 年，伯恩斯坦与瓦齐拉尼（Ethan Bernstein、Umesh Vazirani）把这条线索系统化为量子复杂性理论，定义了后来成为整个领域核心的复杂性类 BQP（见下文）。1994 年，西蒙（Daniel Simon）构造了一个"找出隐藏周期"的问题并给出指数级量子加速——正是西蒙的算法直接启发了肖尔：肖尔后来多次提到，他是在听人转述西蒙的结果后意识到，同样的思路可以搬到整数分解上。从人工的玩具问题到打碎 RSA 的实用算法，中间只隔了这一步。

量子力学基础：叠加与纠缠#

量子计算的力量来自两个量子力学现象：

叠加（Superposition）：经典比特（bit）只能处于 0 或 1 的状态。量子比特（qubit）可以处于 0 和 1 的叠加态： $$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$$ 其中 $\alpha, \beta$ 是复数，满足 $|\alpha|^2 + |\beta|^2 = 1$。$|\alpha|^2$ 是测量时得到 0 的概率，$|\beta|^2$ 是得到 1 的概率。

$n$ 个 qubit 处于叠加态时，可以同时表示 $2^n$ 个经典状态的叠加。这不等于"同时进行 $2^n$ 个计算"（那是量子并行的常见误解），但它允许某些量子算法利用叠加的干涉来放大正确答案的概率。

纠缠（Entanglement）：两个（或多个）qubit 可以处于无法被分解为各自独立态的联合量子态，例如： $$|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$ 这意味着测量第一个 qubit，会立即确定第二个 qubit 的状态——无论它们相隔多远。纠缠是量子算法和量子密码协议的关键资源。

测量与波函数坍缩：对叠加态的 qubit 进行测量，会以相应概率得到 0 或 1，且叠加态随即坍缩为确定态。这意味着量子算法必须被仔细设计，使得正确答案的概率在测量时足够高。

量子复杂性：BQP#

量子计算对应的复杂性类是 BQP（Bounded-error Quantum Polynomial time），由伯恩斯坦与瓦齐拉尼在 1993 年定义：

BQP 是所有可以被量子计算机在多项式时间内以至少 2/3 的成功概率解决的决策问题。（"Bounded-error"意指错误概率有上界，可以通过重复运行降低到任意小。）

BQP 与经典复杂性类的关系： $$P \subseteq BPP \subseteq BQP \subseteq PSPACE$$ 其中 BPP 是经典随机多项式时间。BQP 是否严格大于 BPP 是量子计算理论最核心的开放问题之一——事实上，目前没有严格证明任何问题在 BQP 中但不在 BPP 中（这需要证明量子计算机比经典随机计算机更强大，类似于 P ≠ NP 之难）。

不过有两类重要的间接证据。其一，在神谕模型下分离是已知存在的：伯恩斯坦与瓦齐拉尼在定义 BQP 的同一篇论文里就构造了相对某个黑盒函数、量子有而经典随机没有的加速；2018 年拉兹与塔尔（Ran Raz、Avishay Tal）更进一步，构造了相对某个神谕 BQP 甚至超出整个多项式层级（PH）的问题。神谕结果不能替代真实世界的证明，但它说明任何证明 BQP = BPP 的企图都必须用到经典与量子模型的内部结构，纯黑盒论证注定失败。其二，整数分解这样的具体候选问题躺在 BQP 里，而经过几十年攻击仍没有经典多项式算法——经验证据强，但同样不是定理。

著名的是：整数分解（Factoring）在 BQP 中（由肖尔算法），但目前不知道它是否在 P 中（如果在 P 中，RSA 就算没有量子计算机也是不安全的）。

肖尔算法：打碎 RSA 的数学#

肖尔算法（1994）的核心思想建立在 数论 和量子傅里叶变换的结合之上：

整数分解问题可以被规约为周期查找（Period Finding）：找到函数 $f(x) = a^x \mod N$（其中 $N$ 是要分解的数，$a$ 是随机选取的整数）的周期 $r$（满足 $a^r \equiv 1 \pmod{N}$）。一旦找到 $r$，用数论的技巧就能以高概率分解 $N$。这个规约本身是经典结果，真正的分水岭在于经典世界与量子世界做周期查找的代价天差地别：经典侧最好的通用分解算法是通用数域筛法（GNFS），其运行时间是次指数的——形如 $\exp\big((\ln N)^{1/3}(\ln\ln N)^{2/3}\big)$ 量级，每翻一倍密钥长度，代价远超翻倍。作为参照，迄今公开的最大分解纪录是 2020 年完成的 RSA-250（829 位），动用了约 2700 核年的 CPU 算力；而密码实践推荐的最小密钥是 2048 位，其经典分解代价还要再高出数个数量级。

量子傅里叶变换（QFT）能在多项式时间内完成这个周期查找——这正是量子加速的来源。经典世界里有极快的 快速傅里叶变换（FFT），但它必须输出全部 $2^n$ 个系数，问题不在变换本身而在数据量；QFT 的巧妙之处是从不输出这些系数——它把 $2^n$ 维的谱藏在一个 $n$ qubit 的叠加态里，再经精心设计的一次测量只取出周期信息。换言之，量子加速不来自"算得快"，而来自把答案编码进干涉图样、只问一个问题。

肖尔算法的影响是即时的：它同样以多项式时间求解离散对数，因此基于椭圆曲线的公钥体系一并失守。密码学界由此开始认真对待 后量子密码（Post-Quantum Cryptography，PQC）——即使在大型量子计算机存在的情况下仍然安全的密码协议。2024 年 8 月，美国国家标准与技术研究院（NIST）正式发布了首批后量子密码标准（FIPS 203/204/205），主体基于格密码学（lattice cryptography）。

格罗弗算法：搜索的平方根加速#

格罗弗算法（Grover's Algorithm，1996）解决无结构搜索问题：在 $N$ 个元素中找到满足某条件的目标。

经典计算机平均需要 $O(N)$ 次查询；格罗弗算法只需要 $O(\sqrt{N})$ 次量子查询——平方根加速。

这个加速看起来没有肖尔算法那么惊人（指数 vs 多项式），但它是通用的：几乎任何"搜索"问题（包括许多 NP 问题）都可以用格罗弗算法获得平方根加速。例如，破解 128 位 AES 对称加密，经典计算机需要 $2^{128}$ 次操作，量子计算机需要 $2^{64}$ 次——仍然非常大，但安全边际缩小了一半。这正是为什么后量子密码标准推荐将对称密钥长度加倍。

平方根同时也是天花板。1997 年，本内特、伯恩斯坦、布拉萨尔与瓦齐拉尼证明：对无结构的搜索黑盒，任何量子算法找到目标的查询次数下界都是 $\Omega(\sqrt{N})$——格罗弗算法在这个模型下是最优的，没有更好的通用搜索算法存在。这个下界给"量子加速从何而来"划出了清晰的边界：加速来自问题结构（周期、对称性），而不是量子力学本身；对完全没有结构的问题，量子力学也只肯交出平方根。这也是为什么各类 量子算法 的设计几乎都在做同一件事——寻找或构造可供干涉放大的结构。

量子纠错：实现量子计算机的工程挑战#

理论上的量子计算机很漂亮，但真实量子比特极其脆弱：退相干（Decoherence）——qubit 与环境的相互作用——会破坏叠加态，引入错误。实验室中的量子比特的相干时间（保持叠加态的时间）通常只有微秒到毫秒量级。

量子纠错（Quantum Error Correction）是应对退相干的理论框架。1995 年，肖尔提出了第一个量子纠错码；随后，表面码（Surface Code）成为最有前途的纠错方案之一。

支撑这一切的理论基石是 1996–1997 年间由阿哈罗诺夫与本-奥尔、基塔耶夫、尼尔-拉弗拉姆与楚雷克等人分别证明的阈值定理（Threshold Theorem）：只要物理 qubit 的单门错误率低于某个常数阈值（表面码下约为百分之一量级），通过不断增加编码冗余，逻辑错误率可以被压到任意低，从而原则上可以运行任意长的量子计算。这个定理把"量子计算机是否可能"从一个哲学问题变成了一个工程问题——剩下的只是把物理错误率压过阈值、再堆出足够多的 qubit。2024 年 12 月，Google 的 Willow 芯片（105 个超导 qubit）首次在实验中演示了低于阈值的行为：表面码的距离从 3 增到 5 再到 7，逻辑错误率逐级减半——这是阈值定理预言的指数抑制第一次在硬件上被直接看到（结果发表于《Nature》）。

量子纠错的代价极高：要保护一个逻辑 qubit（不受噪声影响），在表面码下需要大约 1000 个物理 qubit（嘈杂的真实量子比特）来冗余编码。运行完整肖尔算法分解 2048 位 RSA 约需 4000 个逻辑 qubit；按 Gidney 与 Ekerå 的经典工程估算（2019 年预印、2021 年发表于《Quantum》），对应约 2000 万个物理 qubit（运行约 8 小时）。近年的改进持续压低这个数字：Gidney 本人 2025 年 5 月的新估算（借助更省空间的算法与 yoked surface code 等新编码）已把分解 RSA-2048 的门槛降到不足一百万个物理 qubit；IBM 则在 2025 年 6 月公布了名为 Starling 的容错机器路线图，目标 2029 年建成约 200 个逻辑 qubit、可运行一亿次门的系统，并押注量子 LDPC 码以进一步降低物理-逻辑比。但对照现实：目前最先进的量子处理器（如 IBM Heron、Google Willow）只有百余到一千个物理 qubit，且错误率仍偏高——理论估算的每一次下修都是真实的进步，而"百万 qubit"与"数百 qubit"之间的鸿沟依然以数量级计。

代价与争议#

量子霸权（Quantum Supremacy）：2019 年，Google 宣称其 53-qubit 量子处理器 Sycamore 在一项随机电路采样任务上比最强经典计算机快约 $10^9$ 倍（约 200 秒 vs 一万年）。IBM 随即反驳，称只要优化经典模拟（充分利用 Summit 超算的硬盘存储），同样的任务约 2.5 天即可完成，差距远没有那么大；此后多个团队进一步缩小了经典模拟的耗时。这场争议揭示了一个根本问题：量子优越性的声明极度依赖于对经典算法最优性能的估计，而这个估计本身就充满不确定性。

NISQ 的定位之争：普雷斯基尔（John Preskill）在 2018 年提出 NISQ（Noisy Intermediate-Scale Quantum，含噪声中等规模量子）一词刻画当下这批设备：规模已超出经典暴力模拟的舒适区，但没有纠错，可用电路深度被噪声锁死。这个概念既是描述也是警示——NISQ 设备能否在容错时代到来之前提供任何有实际价值的量子优势，至今没有定论。曾被寄予厚望的变分量子算法（VQE、QAOA 等，把量子处理器当作经典优化器的协处理器）遭遇了"贫瘠高原"（barren plateau）等训练障碍，让相当一部分早期乐观预期归于谨慎；诚实地说，截至 2026 年，还没有任何一个有商业价值的实际问题被量子计算机解决得比经典方法更好——所有量子优势演示都针对人为构造的基准任务。

BQP 与 NP 的关系：量子计算机不能在多项式时间内解决所有 NP 问题（除非 $NP \subseteq BQP$，目前理论界认为这不成立）。NP 完全问题如旅行商问题，量子计算机只能获得格罗弗式的平方根加速，而非指数加速——量子计算机不是 NP 问题的银弹。

跨域连接#

• 计算复杂性：量子的能力被装进一个复杂度类，它夹在经典随机多项式时间与多项式空间之间。关键在于两端的严格包含至今都没被证明——没有任何具体问题被证明属于量子类而不属于经典随机类，所以"量子更强"目前是主流猜想而非定理。
• 量子纠缠：叠加常被讲成"同时试遍所有答案"，这是错的：测量只会以概率坍缩到一个结果，读不出整片叠加。真正的资源是干涉——让错误答案的概率幅相消、正确答案相长。没有精心设计的干涉结构，叠加本身一文不值。
• 量子纠错：真实比特会与环境纠缠而退相干，且态既不能复制也不能直接测量。纠错只能测校验子，暴露"哪里错了"而不暴露"存的是什么"，代价是一个逻辑比特要靠大量物理比特撑着。硬件路线图的核心数字，正是这个比例。
• 密码学基础：威胁是分层而非全面的：基于分解与离散对数的公钥体系有多项式时间的量子算法，属于确证的威胁；而对称密码只受平方根级搜索加速，把密钥长度加倍即可抵消。所谓"量子破解一切加密"混淆了这两层。
• 量子化学：这条路线的原始动机来自模拟：用经典机器记录多粒子量子态，所需资源随粒子数指数增长。用一个量子系统去模拟另一个量子系统，把指数换成多项式——这是量子优势最有物理理由、也最不依赖复杂度猜想的一类主张。

参考文献#

• Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26(5) (1997): 1484–1509. （肖尔算法原始论文）
• Grover, L. K. A Fast Quantum Mechanical Algorithm for Database Search. Proc. 28th ACM STOC (1996): 212–219. （格罗弗算法）
• Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information. Cambridge University Press (2000). （量子计算的权威教科书）
• Feynman, R. Simulating Physics with Computers. International Journal of Theoretical Physics 21(6–7) (1982): 467–488. （量子计算思想的起点）
• Bernstein, E. & Vazirani, U. Quantum Complexity Theory. SIAM Journal on Computing 26(5) (1997): 1411–1473. （BQP 的定义性论文，会议版 1993）
• Bennett, C. H., Bernstein, E., Brassard, G. & Vazirani, U. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing 26(5) (1997): 1510–1523. （格罗弗搜索的最优性下界）
• Preskill, J. Quantum Computing in the NISQ Era and Beyond. Quantum 2 (2018): 79. （NISQ 概念的出处）
• Gidney, C. How to Factor 2048 Bit RSA Integers with Less Than a Million Noisy Qubits. arXiv:2505.15917 (2025). （RSA-2048 量子资源估算的最新下修）