现代公钥密码学的安全性建立在特定数学问题的计算困难性之上——大整数分解支撑着 RSA，离散对数问题支撑着 Diffie-Hellman 和椭圆曲线密码体系。这些困难性假设在经典计算模型下已经经受了数十年的检验，被广泛认为是可靠的。然而，量子计算（quantum computing）的发展正在从根本上动摇这一信心。1994 年，Peter Shor 提出了一种量子算法，能够在多项式时间内完成大整数分解和离散对数求解，这意味着一旦大规模容错量子计算机成为现实，当前互联网上几乎所有的公钥密码基础设施都将变得不堪一击。
本文是密码学百科系列的第 55 篇。在前一篇关于密码学标准化的讨论基础上，本文将系统讲解量子计算的基本概念和原理。我们不会试图让读者在一篇文章中掌握量子力学的全部深度，而是从密码学从业者的实际需要出发，聚焦于理解量子威胁所必需的核心知识：量子比特与叠加态、量子门与量子电路、量子纠缠、量子并行性与干涉，以及作为入门示例的 Deutsch-Jozsa 算法。这些概念将为后续文章讨论 Shor 算法、Grover 算法以及后量子密码学奠定坚实的理论基础。
一、量子计算的密码学动机
密码学家为什么必须理解量子计算？答案可以从三个层面来回答。
笔者认为，量子计算在密码学社区中同时处于「被过度炒作」和「被低估」的矛盾状态。被过度炒作的是近期威胁——媒体标题中的「量子计算将摧毁加密」给人一种明天就要发生的紧迫感，但现实是，从当前的噪声中等规模量子设备（NISQ）到能运行 Shor 算法攻破 RSA-2048 的容错量子计算机之间，仍有数百万物理量子比特的鸿沟。被低估的是长期影响——量子计算不仅仅威胁现有的公钥密码，它还将从根本上改变我们思考「计算困难性」的方式，催生全新的密码学范式（如量子货币、量子复制保护），并迫使整个数字基础设施进行有史以来规模最大的密码学迁移。
第一个层面是直接威胁。Shor 算法表明，量子计算机能够在多项式时间 O(n^3) 内分解 n 位整数，而目前已知最好的经典算法——通用数域筛法（general number field sieve, GNFS）——的时间复杂度为亚指数级别 exp(O(n^{1/3} (log n)^{2/3}))。这一差距意味着，对于 2048 位的 RSA 模数，经典计算机需要的时间远超宇宙年龄，而一台足够规模的量子计算机可能在数小时内完成分解。类似地，椭圆曲线上的离散对数问题同样可以被量子算法高效求解。这对当今广泛部署的 TLS、SSH、PGP、数字签名等协议构成了存在性威胁。
第二个层面是”先收集后解密”（harvest now, decrypt later）的攻击策略。即使当前尚不存在足以威胁实际密码系统的量子计算机，攻击者完全可以现在就截获并存储加密通信数据，等待未来量子计算机成熟后再进行解密。对于需要长期保密的信息——国家机密、医疗记录、金融数据——这一威胁已经是现实的。因此，迁移到抗量子密码方案的紧迫性远高于量子计算机实际出现的时间点。
第三个层面是对称密码与哈希函数的安全边际问题。Grover 算法能够将无结构搜索问题的复杂度从 O(N) 降低到 O(√N)，这等价于将对称密钥的有效安全性减半：AES-128 在量子攻击者面前仅提供 64 位安全性，AES-256 提供 128 位安全性。虽然这不如 Shor 算法对公钥密码的威胁那样毁灭性，但它迫使我们重新审视所有对称密码方案的安全参数选择。
从时间线的角度来看，量子计算的发展正在加速。2019 年 Google 宣布实现”量子优越性”（quantum supremacy），用 53 个超导量子比特在 200 秒内完成了经典超级计算机需要约一万年才能完成的特定采样任务。此后，IBM、中国科学技术大学等团队在量子比特数量和量子纠错方面持续取得进展。IBM 在其公布的路线图中计划在 2030 年前后实现包含数千个逻辑量子比特的容错量子计算机。尽管从实验室演示到能够运行 Shor 算法攻击实际密码系统所需的数百万物理量子比特之间仍有巨大鸿沟，但密码学界的共识是：迁移必须现在就开始，因为大规模密码基础设施的升级周期本身就需要十年甚至更长时间。美国国家标准与技术研究院（NIST）自 2016 年启动的后量子密码标准化进程正是这一紧迫性的直接体现。
二、量子比特与叠加态
经典计算机的基本信息单元是比特（bit），它取值 0 或 1。量子计算机的基本信息单元是量子比特（quantum bit, qubit），它是一个二维量子力学系统。与经典比特不同，量子比特可以处于 |0⟩ 和 |1⟩ 的叠加态（superposition）。一个量子比特的一般状态可以写为：
|ψ⟩ = α|0⟩ + β|1⟩其中 α 和 β 是复数，称为概率幅（amplitude），满足归一化条件 |α|² + |β|² = 1。当我们对量子比特进行测量（measurement）时，以概率 |α|² 得到结果 0，以概率 |β|² 得到结果 1。测量之后，量子比特的状态会”坍缩”（collapse）到与测量结果对应的基态——如果测量结果是 0，则状态变为 |0⟩；如果测量结果是 1，则状态变为 |1⟩。这一坍缩是不可逆的，测量前的叠加信息在测量后完全丢失。
量子比特的状态空间可以用布洛赫球（Bloch sphere）直观地表示。布洛赫球是一个单位球面，其北极对应 |0⟩，南极对应 |1⟩。球面上的每一个点对应一个纯态量子比特状态。具体地，任意量子比特状态可以参数化为：
|ψ⟩ = cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩其中 θ ∈ [0, π] 是极角，φ ∈ [0, 2π) 是方位角。以下是布洛赫球的示意图：
|0⟩ (北极, θ=0)
○
/ | \
/ | \
/ | \
/ | \
/ _____|_____ \
| / | \ | ← 赤道: 等概率叠加态
|+⟩ ----●-/-------|-------\-●---- |-⟩
(|0⟩+|1⟩)/√2 | (|0⟩-|1⟩)/√2
| \ | / |
\ ‾‾‾‾‾|‾‾‾‾‾ /
\ | θ / θ: 极角 (0 到 π)
\ |↙ / φ: 方位角 (0 到 2π)
\ | /
\ | /
○
|1⟩ (南极, θ=π)
关键位置:
· 北极 |0⟩: θ=0, 概率 P(0)=1, P(1)=0
· 南极 |1⟩: θ=π, 概率 P(0)=0, P(1)=1
· 赤道 |+⟩: θ=π/2, φ=0, P(0)=P(1)=1/2
· 赤道 |-⟩: θ=π/2, φ=π, P(0)=P(1)=1/2
· 任意点 |ψ⟩: P(0)=cos²(θ/2), P(1)=sin²(θ/2)布洛赫球的赤道上分布着等概率叠加态，例如 (|0⟩ + |1⟩)/√2 位于赤道的正 x 方向。这一几何表示对于理解单量子比特门的操作非常有帮助——每个单量子比特门都对应布洛赫球上的一个旋转。例如，Pauli-X 门是绕 x 轴旋转 π，将北极翻转到南极；Hadamard 门则是绕 x-z 平面的对角轴旋转 π，将 |0⟩（北极）旋转到 |+⟩（赤道正 x 方向）。
需要特别强调的是，叠加态并不意味着量子比特”同时是 0 和 1”。这种流行说法虽然在某种层面上反映了量子态的非经典特征，但它容易导致误解。更准确的理解是：量子比特处于一种确定的量子状态，该状态完整地编码了在不同测量基下获得各个结果的概率。叠加态的威力不在于”同时存储多个值”，而在于量子门操作可以同时作用于所有概率幅分量，并且通过精心设计的干涉过程让正确答案的概率幅被增强、错误答案的概率幅被抵消。
一个经常被忽视的观点是：「量子计算机同时尝试所有可能性」这种说法不仅不准确，而且会严重误导对量子计算能力边界的判断。如果量子计算机真的能「同时尝试所有可能性并直接读出答案」，那么它将能在常数时间内解决任何 NP 问题——但这几乎可以肯定是不成立的（学界普遍猜想 NP ⊄ BQP）。真相更加微妙也更加有趣：量子计算机确实可以通过叠加态「同时处理」指数多的计算路径，但它无法直接「看到」所有结果。关键在于量子干涉——算法必须被精心设计，使得正确答案的概率幅通过相长干涉被放大，而错误答案的概率幅通过相消干涉被抑制。这就是为什么量子加速只对具有特定数学结构的问题有效——没有可利用的结构，就没有办法设计出有效的干涉模式。理解这一点对密码学至关重要：它解释了为什么 Shor 算法能利用数论问题的周期结构实现指数加速，而 Grover 算法对无结构搜索只能实现二次加速。
对于多量子比特系统，状态空间的维度呈指数增长。n 个量子比特组成的系统的状态是一个 2^n 维复向量空间中的单位向量。以两个量子比特为例，计算基（computational basis）包含 |00⟩、|01⟩、|10⟩、|11⟩ 四个基态，一般状态为：
|ψ⟩ = α₀₀|00⟩ + α₀₁|01⟩ + α₁₀|10⟩ + α₁₁|11⟩完整描述这个两量子比特状态需要 4 个复数（减去全局相位和归一化约束后有 6 个实参数）。推广到 n 个量子比特，完整描述其状态需要 2^n 个复数。这一指数级的状态空间正是量子计算潜在威力的数学根源——50 个量子比特的状态向量需要 2^50 ≈ 10^{15} 个复数来描述，这已经超出了经典超级计算机直接模拟的能力。
三、量子门与量子电路
量子计算通过量子门（quantum gate）来操纵量子比特的状态。在数学上，量子门是酉矩阵（unitary matrix），即满足 U†U = UU† = I 的矩阵，其中 U† 是 U 的共轭转置。酉性保证了量子态的归一化条件在门操作后仍然成立，同时也意味着量子门操作是可逆的——这与经典计算中的某些不可逆操作（如 AND 门）形成对比。
最重要的单量子比特门包括以下几种。
Pauli-X 门是量子版本的经典 NOT 门，它将 |0⟩ 变为 |1⟩，将 |1⟩ 变为 |0⟩。其矩阵表示为：
X = [[0, 1],
[1, 0]]在布洛赫球上，X 门对应绕 x 轴旋转 π 弧度。
Pauli-Y 门和 Pauli-Z 门分别对应绕 y 轴和 z 轴旋转 π 弧度。Z 门将 |0⟩ 保持不变，将 |1⟩ 变为 -|1⟩，即引入一个相位翻转。它们的矩阵表示为：
Y = [[0, -i], Z = [[1, 0],
[i, 0]] [0, -1]]Hadamard 门（H 门）是量子计算中最核心的门之一。它将计算基态变换为等概率叠加态：
H|0⟩ = (|0⟩ + |1⟩)/√2
H|1⟩ = (|0⟩ - |1⟩)/√2其矩阵表示为：
H = (1/√2) [[1, 1],
[1, -1]]Hadamard 门的重要性在于：它是在经典世界和量子世界之间建立桥梁的基本操作。对 n 个初始化为 |0⟩ 的量子比特并行施加 H 门，可以产生所有 2^n 个计算基态的等概率叠加：
H^{⊗n}|0⟩^{⊗n} = (1/√2^n) Σ_{x=0}^{2^n-1} |x⟩这一操作是许多量子算法的第一步，它将系统置入一个包含所有可能输入的叠加态中。
在双量子比特门中，最重要的是受控非门（controlled-NOT, CNOT）。CNOT 门有两个输入：控制量子比特（control qubit）和目标量子比特（target qubit）。当控制量子比特为 |1⟩ 时，对目标量子比特执行 X 门（取反）；当控制量子比特为 |0⟩ 时，目标量子比特不变。CNOT 门的矩阵表示（在计算基 |00⟩、|01⟩、|10⟩、|11⟩ 下）为：
CNOT = [[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 1],
[0, 0, 1, 0]]CNOT 门在量子计算中的地位类似于经典计算中的 NAND 门——它是构建纠缠态和实现通用量子计算的关键组件。
另一个值得提及的多量子比特门是 Toffoli 门（也称 CCNOT 门），它是一个三量子比特门：当两个控制量子比特都为 |1⟩ 时，对目标量子比特执行取反操作。Toffoli 门本身就是经典可逆计算的通用门——仅用 Toffoli 门就可以模拟任何经典布尔电路。
以下是几个核心量子门的电路符号表示。在量子电路图中，水平线代表量子比特，时间从左向右流动，方框和符号代表量子门操作：
1) Hadamard 门（H）—— 制备叠加态
q: ──┤ H ├──
└───┘
效果: |0⟩ → (|0⟩+|1⟩)/√2
|1⟩ → (|0⟩-|1⟩)/√2
2) CNOT 门 —— 制备纠缠态（贝尔态制备电路）
q0: ──┤ H ├──●── 控制位
└───┘ │
q1: ─────────⊕── 目标位
效果: |00⟩ → (|00⟩+|11⟩)/√2 = |Φ+⟩
3) Toffoli 门（CCNOT）—— 经典可逆计算的通用门
q0: ──●── 控制位 1
│
q1: ──●── 控制位 2
│
q2: ──⊕── 目标位
效果: |q0, q1, q2⟩ → |q0, q1, q2 ⊕ (q0 ∧ q1)⟩
4) Deutsch-Jozsa 算法电路（n=1 情形）
q0: ─┤ H ├──┤ ├──┤ H ├──┤M├── → 0: 常函数
└───┘ │ │ └───┘ └─┘ → 1: 平衡函数
q1: ─┤ X ├──┤ U_f ├──────────────
└───┘ └─────┘
（q1 先经 X 门变为 |1⟩, 再经 H 门进入 (|0⟩-|1⟩)/√2）量子计算的一个基本定理是：任何 n 量子比特酉操作都可以分解为单量子比特门和 CNOT 门的组合。这意味着 {单量子比特门, CNOT} 构成了一个通用量子门集（universal gate set）。在实际应用中，我们通常选择一个有限的近似通用门集，例如 {H, T, CNOT}，其中 T 门是 π/8 相位门。Solovay-Kitaev 定理保证了任何单量子比特门都可以被这个有限门集高效地近似到任意精度。
量子电路（quantum circuit）是量子算法的标准表示形式。它由水平线（代表量子比特）和作用在这些线上的量子门组成，按照从左到右的顺序执行。量子电路模型与经典电路模型在结构上是类似的，但有两个关键区别：量子门必须是酉的（可逆的），以及量子线不允许分叉（不可克隆定理的直接推论）。
四、量子纠缠
量子纠缠（quantum entanglement）是量子力学中最深刻也最违反直觉的现象之一，它同时也是量子计算优越于经典计算的核心资源。当两个或多个量子比特处于纠缠态时，对其中一个量子比特的测量结果会与其他量子比特的测量结果产生即时的、非经典的关联，无论这些量子比特在空间上相距多远。
最简单的纠缠态是贝尔态（Bell state），也称 EPR 对（Einstein-Podolsky-Rosen pair）。四个贝尔态为：
|Φ+⟩ = (|00⟩ + |11⟩)/√2
|Φ-⟩ = (|00⟩ - |11⟩)/√2
|Ψ+⟩ = (|01⟩ + |10⟩)/√2
|Ψ-⟩ = (|01⟩ - |10⟩)/√2以 |Φ+⟩ 为例：如果我们对第一个量子比特进行测量，有 50% 的概率得到 0（此时整个系统坍缩到 |00⟩，第二个量子比特也必然是 0），50% 的概率得到 1（此时系统坍缩到 |11⟩，第二个量子比特也必然是 1）。两个量子比特的测量结果总是完全一致的，即使它们相距光年之遥。这种关联无法用任何经典的局域隐变量理论来解释——Bell 不等式的违反已经在大量实验中得到了确认。
贝尔态可以通过非常简单的量子电路制备：对第一个量子比特施加 Hadamard 门，然后施加一个以第一个量子比特为控制、第二个量子比特为目标的 CNOT 门。以初始状态 |00⟩ 为例：
|00⟩ → (H ⊗ I)|00⟩ = ((|0⟩+|1⟩)/√2)|0⟩ = (|00⟩+|10⟩)/√2
→ CNOT → (|00⟩+|11⟩)/√2 = |Φ+⟩纠缠态的一个关键特征是它不能被写成各个量子比特状态的张量积。对于 |Φ+⟩ = (|00⟩+|11⟩)/√2，不存在单量子比特状态 |a⟩ 和 |b⟩ 使得 |Φ+⟩ = |a⟩ ⊗ |b⟩。这意味着纠缠态中每个量子比特都不拥有独立的量子状态——整个系统只有一个整体的量子状态。
不可克隆定理（no-cloning theorem）是量子力学的另一个基本约束：不存在一个量子操作能够将一个未知量子态完美地复制一份。该定理的证明非常简洁：假设存在一个酉操作 U 使得对任意量子态 |ψ⟩ 都有 U(|ψ⟩|0⟩) = |ψ⟩|ψ⟩，则对于两个不同的态 |ψ⟩ 和 |φ⟩，利用酉操作保内积的性质可以推出 ⟨ψ|φ⟩ = (⟨ψ|φ⟩)²，这意味着 ⟨ψ|φ⟩ 只能为 0 或 1，即 |ψ⟩ 和 |φ⟩ 要么正交要么相同，与”任意量子态”的前提矛盾。不可克隆定理对密码学有着深远的影响：它是量子密钥分发（quantum key distribution, QKD）安全性的物理基础——窃听者无法在不干扰量子态的情况下复制传输中的量子比特。
量子隐形传态（quantum teleportation）是纠缠的另一个重要应用。Alice 和 Bob 共享一个贝尔态 |Φ+⟩，Alice 拥有一个未知量子态 |ψ⟩ = α|0⟩ + β|1⟩ 想要传送给 Bob。通过对她手中的两个量子比特（待传送态和她那半 EPR 对）执行贝尔测量，并将两个经典比特的测量结果通过经典信道告知 Bob，Bob 就可以对他那半 EPR 对执行相应的恢复操作，得到与 Alice 原始态完全相同的量子态。整个过程中没有任何量子态被物理传输，也不违反不可克隆定理（Alice 的原始态在贝尔测量后被破坏了），更不违反相对论（经典信息的传输仍需遵守光速限制）。量子隐形传态是量子网络和分布式量子计算的基础协议。
五、量子并行性与干涉
量子计算的核心优势常被概括为”量子并行性”（quantum parallelism）。其基本思想是：如果将 n 个量子比特置入所有 2^n 个计算基态的等概率叠加中，然后对它们施加一个实现经典函数 f 的酉操作 U_f，则该操作会同时作用于所有 2^n 个输入：
U_f (1/√2^n Σ_x |x⟩)|0⟩ = (1/√2^n) Σ_x |x⟩|f(x)⟩从表面上看，这似乎意味着量子计算机只需一步就完成了经典计算机需要 2^n 步才能完成的工作。然而，量子并行性本身并不直接给出计算优势——问题在于测量。如果我们直接测量上述状态，只能得到一个随机的 x 及其对应的 f(x)，这与经典地随机选择一个 x 来计算 f(x) 没有任何区别。
量子计算的真正威力来自于将量子并行性与量子干涉（quantum interference）相结合。干涉是波动力学的基本现象：当两个波叠加时，同相的分量会增强（相长干涉，constructive interference），反相的分量会抵消（相消干涉，destructive interference）。在量子计算中，概率幅扮演着”波”的角色。量子算法的本质在于精心设计一系列量子门操作，使得正确答案所对应的计算路径的概率幅相长干涉——累加增大，而错误答案所对应的路径的概率幅相消干涉——相互抵消。最终测量时，正确答案以高概率出现。
这种干涉机制是量子算法设计的核心。Shor 算法利用量子傅里叶变换实现干涉，从而在指数多的叠加态中提取出周期信息。Grover 算法通过反复施加”反射”操作，逐步放大目标态的概率幅。Deutsch-Jozsa 算法则利用 Hadamard 变换的干涉效应，在一次查询中完成经典计算机需要指数次查询才能完成的判断任务。理解干涉为何以及如何在这些算法中发挥作用，是掌握量子计算与密码学关系的关键。
值得注意的是，量子并行性所提供的加速并非对所有问题都有效。目前已知的量子加速仅适用于具有特定数学结构的问题——周期性（Shor 算法）、对称性（Grover 算法）、线性代数结构（HHL 算法）等。对于一般的无结构问题，量子计算机相对于经典计算机的优势至多是多项式级别的。这一事实对密码学的启示是：对称密码和哈希函数由于其设计目标就是抵抗结构化攻击，因此受到量子计算的威胁远小于依赖特定数论结构的公钥密码方案。
六、Deutsch-Jozsa 算法
Deutsch-Jozsa 算法是量子计算优越性的第一个理论证明，也是理解更复杂量子算法的绝佳起点。我们先从最简单的 Deutsch 问题（单比特版本）开始，再推广到一般情形。
Deutsch 问题的设定如下：给定一个黑箱函数 f: {0, 1} → {0, 1}，它要么是常函数（constant，即 f(0) = f(1)），要么是平衡函数（balanced，即 f(0) ≠ f(1)）。我们的任务是判断 f 属于哪一类。在经典计算中，我们必须查询 f 两次（分别计算 f(0) 和 f(1)）才能确定答案。Deutsch 算法只需查询 f 一次就能给出确定的答案。
算法的步骤如下。准备两个量子比特，初始状态为 |0⟩|1⟩。对两个量子比特分别施加 Hadamard 门，得到：
((|0⟩+|1⟩)/√2) · ((|0⟩-|1⟩)/√2)然后施加量子预言机（quantum oracle）U_f，它的作用是 |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩。可以验证，当第二个量子比特处于 (|0⟩-|1⟩)/√2 状态时，U_f 的作用等价于在第一个量子比特上引入一个相位：
|x⟩ · (|0⟩-|1⟩)/√2 → (-1)^{f(x)} |x⟩ · (|0⟩-|1⟩)/√2这种技巧被称为相位回踢（phase kickback），是众多量子算法的共同构件。施加 U_f 后，第一个量子比特的状态变为：
((-1)^{f(0)}|0⟩ + (-1)^{f(1)}|1⟩) / √2最后对第一个量子比特施加 Hadamard 门。如果 f(0) = f(1)（常函数），则 (-1)^{f(0)} = (-1)^{f(1)}，第一个量子比特回到 ±|0⟩，测量得到 0。如果 f(0) ≠ f(1)（平衡函数），则两个概率幅符号相反，第一个量子比特变为 ±|1⟩，测量得到 1。因此，只需一次测量就能确定地判断 f 是常函数还是平衡函数。
推广到 n 比特的 Deutsch-Jozsa 问题：给定 f: {0,1}^n → {0,1}，保证 f 要么是常函数（对所有输入返回相同值），要么是平衡函数（恰好对一半输入返回 0，另一半返回 1）。经典确定性算法在最坏情况下需要查询 f 共 2^{n-1}+1 次，而 Deutsch-Jozsa 量子算法只需查询一次。算法流程与单比特版本完全类似：对 n 个量子比特施加 Hadamard 门产生全叠加态，通过量子预言机引入相位，再施加 Hadamard 门实现干涉，最后测量——如果测量结果全为 0，则 f 是常函数；否则 f 是平衡函数。
以下是使用 Python 进行简单矩阵运算模拟 Deutsch 算法的代码，不依赖任何量子计算框架：
import numpy as np
# 基态定义
ket0 = np.array([1, 0], dtype=complex)
ket1 = np.array([0, 1], dtype=complex)
# 量子门定义
H = np.array([[1, 1], [1, -1]], dtype=complex) / np.sqrt(2) # Hadamard
I2 = np.eye(2, dtype=complex) # 单位门
def tensor(a, b):
"""计算两个向量或矩阵的张量积（Kronecker 积）"""
return np.kron(a, b)
def make_oracle(f0, f1):
"""
构造量子预言机 U_f 的 4x4 矩阵。
U_f|x>|y> = |x>|y XOR f(x)>
f0 = f(0), f1 = f(1)
"""
U = np.zeros((4, 4), dtype=complex)
for x in range(2):
fx = f0 if x == 0 else f1
for y in range(2):
# 输入: |x>|y> -> 输出: |x>|y XOR f(x)>
in_idx = x * 2 + y
out_idx = x * 2 + (y ^ fx)
U[out_idx, in_idx] = 1
return U
def deutsch(f0, f1):
"""
运行 Deutsch 算法，判断 f 是常函数还是平衡函数。
f0 = f(0), f1 = f(1)，返回 'constant' 或 'balanced'。
"""
# 步骤 1：初始化 |0>|1>
psi = tensor(ket0, ket1)
# 步骤 2：对两个量子比特施加 Hadamard 门
HH = tensor(H, H)
psi = HH @ psi
# 步骤 3：施加量子预言机 U_f
Uf = make_oracle(f0, f1)
psi = Uf @ psi
# 步骤 4：对第一个量子比特施加 Hadamard 门
H_I = tensor(H, I2)
psi = H_I @ psi
# 步骤 5：测量第一个量子比特
# 计算第一个量子比特处于 |0> 的概率
prob_0 = abs(psi[0])**2 + abs(psi[1])**2
if prob_0 > 0.5:
return "constant"
else:
return "balanced"
# 测试所有四种可能的函数
print("Deutsch 算法模拟结果：")
print(f" f(0)=0, f(1)=0 → {deutsch(0, 0)}") # 常函数
print(f" f(0)=1, f(1)=1 → {deutsch(1, 1)}") # 常函数
print(f" f(0)=0, f(1)=1 → {deutsch(0, 1)}") # 平衡函数
print(f" f(0)=1, f(1)=0 → {deutsch(1, 0)}") # 平衡函数
# 输出中间态以帮助理解相位回踢
print("\n相位回踢过程详解（f(0)=0, f(1)=1 的情况）：")
psi = tensor(ket0, ket1)
print(f" 初始态 |01>：{psi}")
HH = tensor(H, H)
psi = HH @ psi
print(f" H⊗H 后：{np.round(psi, 4)}")
Uf = make_oracle(0, 1)
psi = Uf @ psi
print(f" U_f 后： {np.round(psi, 4)}")
H_I = tensor(H, I2)
psi = H_I @ psi
print(f" H⊗I 后： {np.round(psi, 4)}")
prob_0 = abs(psi[0])**2 + abs(psi[1])**2
prob_1 = abs(psi[2])**2 + abs(psi[3])**2
print(f" 第一个量子比特：P(|0>)={prob_0:.4f}, P(|1>)={prob_1:.4f}")运行上述代码将验证：对于常函数（f(0)=f(1)），测量结果总是 |0⟩，算法输出”constant”；对于平衡函数（f(0)≠f(1)），测量结果总是 |1⟩，算法输出”balanced”。这一确定性结果完全来自于 Hadamard 门引起的相长与相消干涉。
虽然 Deutsch-Jozsa 算法解决的问题本身没有实际的密码学应用价值，但它精彩地展示了量子计算的三个核心要素如何协同工作：叠加态实现并行查询、相位回踢将函数值编码为概率幅的符号、Hadamard 变换实现干涉从而提取全局性质。Shor 算法和 Grover 算法正是在同样的框架上，针对具有密码学意义的问题，设计出了更为精巧的干涉模式。
七、量子计算模型
前面介绍的量子电路模型（gate model）是最常用的量子计算模型，但并不是唯一的。了解不同的量子计算模型有助于全面理解量子计算的能力边界和硬件实现的多样性。
门电路模型（gate model, circuit model）是由 Deutsch 在 1989 年形式化的量子计算模型。在这个模型中，计算由初始化量子比特、施加一系列量子门、最终测量三个步骤组成。绝大多数量子算法（包括 Shor 算法和 Grover 算法）都是在门电路模型下描述的。当前主流的量子计算硬件平台——超导量子比特（IBM、Google）、离子阱（IonQ、Quantinuum）——都是基于门电路模型设计的。
绝热量子计算（adiabatic quantum computing）模型基于量子力学的绝热定理：如果一个量子系统的哈密顿量（Hamiltonian）从初始值缓慢地变化到最终值，系统将始终保持在其瞬时基态（ground state）。要解决一个优化问题，将其编码为最终哈密顿量的基态，然后从一个已知基态的简单初始哈密顿量出发，缓慢演化到目标哈密顿量——演化结束后系统所处的基态就编码了优化问题的解。D-Wave 公司的量子退火器（quantum annealer）就是基于这一原理构建的。绝热量子计算在计算能力上等价于门电路模型，但在抗噪声方面可能具有不同的特性。
基于测量的量子计算（measurement-based quantum computing, MBQC），也称一次性量子计算（one-way quantum computing），是一种完全不同的计算范式。首先制备一个大规模的纠缠态（通常是图态 cluster state），然后仅通过对各个量子比特的单量子比特测量来驱动计算。每次测量的基的选择取决于之前测量的结果，从而实现自适应的计算流程。MBQC 在计算能力上同样等价于门电路模型，并且在光子量子计算等特定硬件平台上可能更易于实现。
拓扑量子计算（topological quantum computing）利用被称为非阿贝尔任意子（non-Abelian anyon）的准粒子来编码和操纵量子信息。信息存储在任意子的拓扑性质中，这些性质对局部扰动具有天然的免疫力，因此拓扑量子比特在原理上具有极强的抗噪声能力。微软的拓扑量子比特计划即基于这一思路，尽管实验实现仍面临重大挑战。
从当前硬件发展来看，超导量子比特技术最为成熟，IBM 和 Google 的处理器已拥有超过 1000 个物理量子比特。离子阱技术在量子比特质量（低错误率、高连通性）方面具有优势。光子量子计算则在室温操作和网络连接方面有独特优势。中性原子平台近年来也取得了快速进展，展示了超过 1000 个量子比特的阵列操控能力。每种硬件路线都在竞相实现容错量子计算的目标。
八、量子纠错简介
量子计算面临的最大实践障碍是噪声和退相干（decoherence）。现实中的量子比特极其脆弱——它们与环境的微小相互作用就会导致量子信息的丢失。量子纠错（quantum error correction, QEC）是解决这一问题的理论框架。
与经典纠错的关键区别在于：量子纠错必须处理连续的错误（量子态是连续的）、不能直接测量量子态（测量会导致坍缩）、以及不能复制量子态（不可克隆定理）。尽管这些约束看似使得量子纠错比经典纠错困难得多，但 Shor 在 1995 年和 Steane 在 1996 年分别证明了量子纠错是可能的。
Shor 码是第一个量子纠错码。它使用 9 个物理量子比特来编码 1 个逻辑量子比特，能够纠正任意单量子比特错误。其基本思想是将比特翻转纠错和相位翻转纠错组合起来：先用三量子比特重复码纠正比特翻转错误，再用另一层三量子比特码纠正相位翻转错误。虽然 Shor 码在实用性上并非最优，但它证明了量子纠错的原理可行性。
当前最有前景的量子纠错码是表面码（surface code）。表面码将量子比特排列在二维网格上，通过测量相邻量子比特之间的稳定子（stabilizer）来检测错误，而不干扰所编码的逻辑信息。表面码的最大优势在于它只需要最近邻的量子比特交互，这与超导量子比特的物理布局天然契合。此外，表面码具有相对较高的容错阈值——当单个物理量子比特的错误率低于约 1% 时，就可以通过增加码距来指数级地降低逻辑错误率。
逻辑量子比特和物理量子比特之间的比率是衡量量子纠错开销的核心指标。对于表面码，实现一个逻辑量子比特通常需要数千个物理量子比特。要运行 Shor 算法分解 2048 位的 RSA 模数，最保守的估计需要约 2000 个逻辑量子比特，这意味着可能需要数百万甚至上千万个物理量子比特。这一巨大的开销解释了为什么尽管当前的量子处理器已经拥有上千个物理量子比特，距离对密码学构成实际威胁仍有相当的距离。
容错量子计算（fault-tolerant quantum computing）的概念是指：即使在量子门操作本身不完美的情况下，通过量子纠错和精心设计的电路结构，仍然可以实现任意长的可靠量子计算。阈值定理（threshold theorem）给出了这一目标的理论保证：只要物理量子门的错误率低于某个阈值（对于表面码约为 1%），就可以通过多层纠错来实现任意低的逻辑错误率。从当前的硬件进展来看，多个平台的单量子比特门和双量子比特门错误率已经接近或低于这一阈值，但要实现完整的容错量子计算，还需要在量子比特数量、纠错编码效率、以及经典控制系统等方面取得进一步突破。乐观的估计认为，具有密码学相关性的容错量子计算机可能在 2030 年代末到 2040 年代初出现。
九、量子计算对密码学的威胁概览
综合前面的讨论，我们可以系统地梳理量子计算对密码学的威胁全景。
对公钥密码的毁灭性威胁来自 Shor 算法。Shor 算法能在多项式时间内解决以下问题：大整数分解（从而攻破 RSA）、有限域上的离散对数问题（从而攻破 Diffie-Hellman 和 DSA）、以及椭圆曲线上的离散对数问题（从而攻破 ECDH、ECDSA 和 EdDSA）。这意味着当前互联网上使用最广泛的公钥密码方案——RSA 密钥交换、ECDHE 密钥协商、RSA/ECDSA 数字签名——在足够强大的量子计算机面前将全部失效。需要强调的是，Shor 算法的威胁是”全有或全无”式的：不存在通过简单增加密钥长度就能抵抗 Shor 算法的方案（因为 Shor 算法的复杂度是多项式级的，而非仅仅降低了某个常数因子）。
对对称密码的威胁来自 Grover 算法。Grover 算法能够将在 N 个元素中搜索目标的复杂度从 O(N) 降低到 O(√N)。将此应用于密钥穷举搜索，k 位密钥的搜索复杂度从 2^k 降低到 2^{k/2}，等价于将有效密钥长度减半。因此：AES-128 在量子攻击下仅提供约 64 位安全性，而 AES-256 提供约 128 位安全性。应对策略相对简单——将密钥长度加倍即可恢复原有的安全级别。对于哈希函数，Grover 算法可以将碰撞搜索和原像搜索的复杂度都降低到其平方根量级，但由于生日攻击已经将碰撞搜索的复杂度降到 O(2^{n/2})，Grover 算法对碰撞攻击的额外加速有限——对 n 位哈希函数碰撞搜索的量子复杂度为 O(2^{n/3})。
从时间线来看，密码学界通常将”密码学相关量子计算机”（cryptographically relevant quantum computer, CRQC）定义为能够在实际时间内运行 Shor 算法攻破 RSA-2048 的量子计算机。目前的主流估计是 CRQC 可能在 2030 年代中后期到 2040 年代初出现，但存在相当大的不确定性。一些乐观的研究者认为新的算法优化和硬件突破可能将这一时间线提前，而也有研究者认为工程挑战可能将其推迟到更远的未来。
无论 CRQC 的确切到来时间如何，密码学界已经达成了明确的共识：向后量子密码（post-quantum cryptography, PQC）的迁移必须立即开始。
笔者认为，围绕「量子威胁时间线」的辩论——量子计算机究竟是 2035 年还是 2045 年能攻破 RSA——虽然重要，但在很大程度上偏离了真正的核心问题。真正的问题不是「我们还有多少年」，而是「我们的密码基础设施是否具备足够的密码敏捷性（crypto-agility）来应对这一转变」。一个具备良好密码敏捷性的系统，无论量子计算机何时到来，都能在合理的时间和成本内完成算法切换。而一个密码敏捷性差的系统——比如将密码算法硬编码在固件中、或者在数百万台物联网设备上部署了不可升级的加密方案——即使再给它二十年的预警期也可能来不及迁移。从这个角度看，「后量子迁移」的本质不是一个密码学问题，而是一个系统工程和组织协调问题。这也是为什么 NIST 在发布后量子标准的同时，反复强调密码敏捷性的重要性。
NIST 在 2024 年正式发布了首批后量子密码标准——基于格的密钥封装机制 ML-KEM（原 CRYSTALS-Kyber）和数字签名算法 ML-DSA（原 CRYSTALS-Dilithium），以及基于哈希的签名方案 SLH-DSA（原 SPHINCS+）。这些方案的安全性建立在被认为能够抵抗量子攻击的数学困难问题之上。后续文章将深入讨论 Shor 算法和 Grover 算法的具体机制，以及后量子密码方案的设计原理。
密码学百科系列 · 第 55 篇
← 上一篇：密码学标准化 | 系列目录 | 下一篇：Shor 算法与 Grover 算法 →