量子算法
可视化漫游
不需要物理背景，也不需要繁复公式。从一个量子比特出发，亲手转动布洛赫球、搭建量子线路、运行 Grover 搜索与 Shor 分解——看清量子计算机究竟“快”在哪里，又“不快”在哪里。
为什么是量子？Why Quantum
经典计算机的每个比特非 0 即 1。量子计算机的基本单元——量子比特——遵循量子力学：描述 n 个量子比特，需要 2n 个复数“振幅”。
1981 年，物理学家理查德·费曼提出了一个问题：既然自然界本身是量子的，用经典计算机去模拟它为何如此困难？答案是——量子系统的状态空间随粒子数指数增长。每多一个量子比特，描述它所需的数字就翻一倍。
费曼的想法很简单：与其费力模拟量子系统，不如直接用可控的量子系统来计算。这就是量子计算的起点。下面拖动滑块，感受一下这种增长有多恐怖。
指数墙：经典计算机要多少内存才能“记住”n 个量子比特？
2n 个振幅并不意味着能一次读出 2n 个答案。测量一次只能得到一个 n 位的结果，其余信息随之消失。量子算法的全部艺术，在于巧妙地编排干涉：让错误答案的振幅相互抵消、正确答案的振幅相互加强，使测量时大概率得到我们想要的结果。
量子算法的三件法宝
叠加 Superposition
量子比特可以处于 |0⟩ 与 |1⟩ 的线性组合中。n 个量子比特可以同时承载 2n 个基态的振幅，为并行处理提供“舞台”。
干涉 Interference
振幅可正可负、甚至是复数，因此不同计算路径会像波一样相长或相消。这是量子算法从“舞台”上筛出正确答案的关键。
纠缠 Entanglement
多个量子比特之间可以形成无法拆分成独立部分的关联。没有纠缠，量子计算机就能被经典计算机高效模拟。
量子比特与布洛赫球Qubit & Bloch Sphere
一个量子比特的状态，可以画成单位球面上的一个点。所有单比特量子门，都只是这个球的一次旋转。
量子比特的一般状态写作（狄拉克符号里的 |·⟩ 读作“ket”）：
|ψ⟩ = α|0⟩ + β|1⟩α、β 是复数“振幅”，满足 |α|² + |β|² = 1测量它时，以 |α|² 的概率得到 0，以 |β|² 的概率得到 1，而且测量后状态会坍缩到对应的结果上。
由于整体相位无法观测，任何单比特态都可以写成两个角度的形式：
|ψ⟩ = cos(θ/2)|0⟩ + eiφ sin(θ/2)|1⟩θ 决定了“纬度”（偏向 0 还是 1），φ 决定了“经度”（相对相位）。于是每个状态都对应布洛赫球上的一个点：北极是 |0⟩，南极是 |1⟩，赤道上是等概率的叠加态。
X 门 · 量子非门
绕 x 轴转 180°，把 |0⟩ 与 |1⟩ 互换。
H 门 · 阿达马
把 |0⟩ 变成 |+⟩，制造等概率叠加。最常用的门。
Z 门 · 相位翻转
绕 z 轴转 180°，概率不变，但 |1⟩ 的振幅变号。
S 门 / T 门
绕 z 轴分别转 90° 与 45°，精细地调节相位。
布洛赫球：亲手旋转一个量子比特
在球上拖动可以旋转视角点击一个门，观察态矢量如何绕轴旋转。试试连续按两次 H。
彩色条为实测频率，白色刻度为理论概率。
你可能注意到了……
- H 门按两次会回到原处：H·H = I。第一次制造叠加，第二次又把叠加“撤销”——这其实是下一章“干涉”的雏形。
- Z、S、T 门不改变测量概率，只让态矢量沿纬线转动。相位看似“看不见”，却是量子算法的灵魂：它决定了后续干涉是相长还是相消。
- 测量会破坏叠加：测量一次后，态矢量跳到北极或南极，原来的 θ、φ 信息永远丢失。所以“重复 1000 次”必须每次重新制备同一个态。
数学一点点：量子门的矩阵形式 可选
把 |0⟩ 写成列向量 (1, 0)ᵀ，|1⟩ 写成 (0, 1)ᵀ，量子门就是 2×2 的酉矩阵（U†U = I，保证概率总和恒为 1）。
干涉：量子算法真正的引擎Interference
经典概率只会相加，永远不会“抵消”。量子振幅却可以——这一点区别，几乎解释了所有量子加速。
想象一个最简单的实验：对 |0⟩ 先做一次 H，再插入一个相位门 P(φ)（只给 |1⟩ 分量乘上 eiφ），最后再做一次 H，然后测量。
第一个 H 把量子比特送进“两条路径”：一条经过 |0⟩，一条经过 |1⟩。第二个 H 再把两条路径重新汇合。最终得到 0 的振幅是两条路径贡献之和：
振幅(0) = ½ + ½·eiφ 振幅(1) = ½ − ½·eiφ每条路径的振幅像一支箭头（复平面上的向量），箭头首尾相接就是总振幅振幅箭头：拖动相位，看干涉如何改变结果
一个“看不见”的相位，通过干涉变成了“看得见”的概率。几乎所有量子算法都遵循同一个套路：叠加 → 用相位标记信息 → 干涉 → 测量。
与经典概率的根本区别
如果把 H 门换成“随机抛硬币”，那么不论中间做什么，最后都是 50% / 50%：两条路径的概率只能相加，永远不会彼此抵消。量子力学则是先把振幅相加、再平方得到概率。正因为振幅可以互相抵消，量子计算机才能“删除”错误答案。
纠缠：无法拆开的关联Entanglement
爱因斯坦称之为“鬼魅般的超距作用”。它是量子计算区别于经典计算的另一块基石。
对两个 |0⟩ 先在第一个比特上做 H，再做一次受控非门（CNOT）：当控制比特为 1 时翻转目标比特。结果得到著名的贝尔态：
|Φ⁺⟩ = ( |00⟩ + |11⟩ ) / √2这个态无法写成“第一个比特的态 ⊗ 第二个比特的态”。单独看任一比特，它都是完全随机的 0 或 1；但两个比特的测量结果总是一致——即使把它们分隔到宇宙两端。
纠缠测量：两个量子比特的“默契”
切换模式，对比纠缠态与独立随机比特不能超光速通信
Alice 无法控制自己测到 0 还是 1，Bob 单独看到的永远是 50/50 的随机数。只有事后比对，才会发现两者的关联。纠缠不能用来传递信息。
不只是“预先约定”
如果只在 0/1 基下测量，经典的“预先装好的手套”也能模仿这种关联。但换用不同角度测量时，纠缠态的关联强度会突破贝尔不等式（CHSH 值可达 2√2 ≈ 2.83，而任何经典模型 ≤ 2）。2022 年诺贝尔物理学奖正是授予了相关实验。
计算的“必需品”
可以证明：如果一个量子线路始终只产生很少的纠缠，经典计算机就能高效地模拟它。纠缠是量子加速的必要条件（但并非充分条件）。
量子线路：像搭积木一样编程Quantum Circuits
量子程序通常画成“线路图”：每条横线是一个量子比特，时间从左向右流动，方框是作用在比特上的量子门。
下面是一个可以自由编辑的小型量子线路模拟器。先从左侧选择一个门，再点击线路上的格子放置它。实心圆点 ● 是“控制”：同一列中只要有控制点，这一列的其他门就只在所有控制比特都为 1 时才生效——● 与 X 放在同一列就是 CNOT，两个 ● 加一个 X 就是 Toffoli 门。
量子线路编辑器
点格子放置 · 再点一次删除 · 色彩表示相位试试“相位反冲”
载入示例后观察：CNOT 的“目标”处于 |−⟩ 时，相位会反过来“踢”回控制比特。这是 Deutsch–Jozsa、Grover、Shor 共同的底层技巧。
试试 2 比特 Grover
只用一次“标记 + 扩散”，就能从 4 个候选里以 100% 概率找到 |11⟩。经典方法平均需要 2.25 次查询。
用滑块单步执行
拖动“执行到第 k 列”，逐列观察振幅如何流动、相位如何变化——这就是量子计算的“慢动作回放”。
Deutsch–Jozsa：一次查询定胜负The First Exponential Separation · 1992
历史上第一个证明“量子计算机能在某些问题上指数级地超越确定性经典算法”的例子。
问题
有一个黑盒函数 f，输入 n 位二进制串，输出 0 或 1。已知它要么是常数函数（全部输出相同），要么是平衡函数（恰好一半输入输出 0，另一半输出 1）。请判断是哪一种。
经典做法
一个个去查。最坏情况下，你查了一半输入都得到相同结果，仍然无法下结论——必须查 2n−1 + 1 次才能确定。
量子做法
只需1 次查询。把黑盒做成“相位黑盒”：|x⟩ → (−1)f(x)|x⟩。先用 H 制造全部输入的叠加，查询一次，再用 H 干涉。若 f 为常数，所有路径在 |00…0⟩ 上相长；若 f 平衡，正负振幅恰好在 |00…0⟩ 上完全抵消。
经典 vs 量子：猜黑盒
左边逐个查询，右边一步到位初始状态：|000⟩。点击 ① 开始。
如果允许极小的出错概率，经典随机算法只需随机查询十来次就能以很高的置信度给出答案。所以 Deutsch–Jozsa 的意义不在实用，而在于它第一次清晰地展示了“叠加 + 相位 + 干涉”的威力，直接启发了 Simon 算法（1994）与随后的 Shor 算法。
Grover 搜索：大海捞针的平方加速Grover's Algorithm · 1996
在 N 个无序的候选项中找出唯一的“目标”。经典方法平均要翻找 N/2 次，Grover 算法只需约 (π/4)·√N 次。
Grover 算法从所有候选项的均匀叠加出发，反复执行两个操作：
- 标记（Oracle）：把目标项的振幅取反。概率不变，只是悄悄打了一个“负号”标记。
- 扩散（Diffusion）：把每个振幅关于平均值做镜像：a → 2μ − a。因为目标是唯一的负数，它远低于平均值，镜像后会被高高抛起；其余项则略微下降。
每轮迭代，目标的振幅都会增加约 2/√N。大约 (π/4)√N 轮后，目标的概率接近 100%。
超过最优次数后，目标概率反而会下降（“过冲”），因为每次迭代本质上是在一个二维平面里旋转固定角度 2θ，转过头就离目标越来越远。在下面的实验里，试着多按几次看看。
Grover 搜索：看振幅如何被“放大”
点击任意柱子可以更换目标它到底意味着什么？
- 平方加速是可证明最优的：对于完全无结构的搜索，任何量子算法都至少需要约 √N 次查询（BBBV 定理，1997）。所以量子计算机无法指数级加速暴力搜索。
- 对密码学的影响有限：Grover 能把 128 位对称密钥的暴力破解从 2128 降到约 264 次“量子查询”。应对办法很简单：改用 256 位密钥（如 AES-256）。
- 是通用的“加速子程序”：振幅放大（Amplitude Amplification）的思想可以嵌入许多算法，为约束满足、优化、蒙特卡洛估计等带来平方级的改进。
Shor 算法：把“分解”变成“找周期”Shor's Algorithm · 1994
RSA 加密的安全性建立在“大整数难以分解”之上。1994 年，Peter Shor 证明：量子计算机可以在多项式时间内完成分解。
Shor 算法的精妙之处在于，它把一个数论难题转化成了量子计算机最擅长的事——寻找周期。整个流程中只有一步需要量子计算机，其余都是经典的预处理与后处理。
随机选一个数 a
选 1 < a < N。如果 gcd(a, N) ≠ 1，运气爆棚，直接得到一个因子；否则继续。
求 a 的“阶” r
函数 f(x) = ax mod N 是周期函数，周期 r 满足 ar ≡ 1 (mod N)。量子计算机对所有 x 的叠加同时计算 f(x)，再用量子傅里叶变换（QFT）让周期信息通过干涉显现为尖峰，测量后得到近似 s/r 的数值。
连分数还原 r
测量结果 k 满足 k/Q ≈ s/r。用连分数展开即可高效地从中读出分母 r。
得到因子
若 r 为偶数且 ar/2 ≢ −1 (mod N)，则 gcd(ar/2 − 1, N) 与 gcd(ar/2 + 1, N) 就是 N 的非平凡因子。随机选 a 时，这一步成功的概率至少为 1/2。
Shor 算法模拟器：分解一个小整数
量子部分的测量分布为精确计算结果量子傅里叶变换为什么快？
对 2n 个数做经典快速傅里叶变换（FFT）需要约 n·2n 次运算；而 QFT 只需约 n²/2 个量子门。代价是：变换结果“藏”在振幅里，不能直接读出全部数值——但对于找周期来说，一次测量就够了，因为概率几乎全部集中在 s·Q/r 附近的尖峰上。
复杂度对比
目前最好的经典分解算法（数域筛法）的运行时间约为 exp(c·n1/3(log n)2/3)，是“亚指数”的；Shor 算法只需约 O(n³) 个门（n 为位数）。这是一个超多项式的加速。
RSA 会被破解吗？
理论上会，但需要大规模容错量子计算机。2025 年 Google 的 Craig Gidney 给出的估算是：分解 2048 位 RSA 大约需要不到一百万个带噪声的物理量子比特、运行约一周。而目前最先进的芯片只有数百到一千多个物理比特，且错误率仍然偏高。
尽管如此，“先存储、后解密”的风险已经存在：今天截获的密文，未来可能被解开。因此美国 NIST 在 2024 年正式发布了首批后量子密码标准（FIPS 203 / 204 / 205，即 ML-KEM、ML-DSA、SLH-DSA），全球正在逐步迁移。
近期算法、纠错与硬件NISQ Era & Beyond
Shor 与 Grover 需要“完美”的量子计算机。在那之前，研究者们在有噪声的中等规模量子设备（NISQ）上探索着另一类算法。
变分量子算法：量子 + 经典协同
变分量子本征求解器（VQE，2014）与量子近似优化算法（QAOA，2014）采用同一种思路：用一个浅层、带参数的量子线路准备候选态，测量其“能量”或“代价”，再交给经典优化器调整参数，循环往复。
线路足够浅，就能在噪声淹没信号之前完成计算。VQE 的目标是求分子的基态能量（量子化学），QAOA 的目标是组合优化问题（如最大割）。不过，它们能否在实际问题上稳定超越经典方法，目前仍没有定论。
量子模拟
费曼最初的梦想，也是最被看好的应用：模拟分子、材料与高能物理中的量子多体系统，例如固氮酶的催化机理、高温超导的成因。
HHL 线性方程组
2009 年提出，在特定条件下可指数加速求解线性方程组。但它要求数据能高效载入量子态、只输出量子态而非完整解，实际优势需要仔细审视。
量子机器学习
热门但充满争议的方向。不少早期“指数加速”后来被“去量子化”的经典算法追平（如推荐系统问题），真正的优势仍在探索中。
量子纠错：通往实用量子计算的必经之路
量子比特极其脆弱，与环境的一丝相互作用就会导致退相干。量子纠错的思路是用许多物理比特编码一个逻辑比特，并持续检测、纠正错误。只要物理错误率低于某个阈值（表面码约为 1%），增加编码规模就能让逻辑错误率指数下降。
2024 年底，Google 的 Willow 芯片首次在表面码上清晰地展示了“越编码越好”的低于阈值行为：码距从 3 增加到 5、再到 7，逻辑错误率每次约减半。这被普遍认为是迈向容错量子计算的里程碑。
主要硬件路线
超导
在接近绝对零度的芯片上用约瑟夫森结构造“人造原子”。门操作快、易于集成，但需要大型稀释制冷机。
离子阱
用电磁场囚禁带电原子，以激光操控。保真度高、全连接，但门速度相对较慢、扩展难度较大。
中性原子
用光镊排列成阵列的中性原子，借助里德堡态实现相互作用。规模扩展迅速，可动态重排比特。
光量子
以光子为载体，可在室温下传播、天然适合通信。已用于玻色采样等量子优势实验。
拓扑
希望利用马约拉纳零模等拓扑态在物理层面抵抗噪声。理论上非常诱人，但实验仍处于早期且存在争议。
真相与误区Myths vs Facts
量子计算是被误解最多的科技话题之一。读完前面的章节，你已经可以亲手戳破这些流行说法了。
BQP：量子计算机“擅长”的问题
BQP 是量子计算机能以高概率在多项式时间内解决的问题类。它包含了经典的 P 与 BPP，也包含整数分解、离散对数这类被认为经典困难的问题。
但 BQP 很可能并不包含NP 完全问题。换句话说，量子计算机的优势来自问题中隐藏的代数结构（如周期性），而不是蛮力。
另一方面，模拟量子系统本身就是 BQP 中的天然问题——这也是为什么许多人相信，量子计算最早的“杀手级应用”会出现在化学和材料领域。
| 问题 | 最好的经典算法 | 量子算法 | 加速类型 |
|---|---|---|---|
| 无结构搜索 | O(N) | Grover：O(√N) | 平方加速（已证最优） |
| 整数分解 / 离散对数 | 数域筛法：亚指数 | Shor：多项式 | 超多项式加速 |
| 量子多体系统模拟 | 一般需指数资源 | 哈密顿量模拟：多项式 | 指数加速（普遍认为） |
| Deutsch–Jozsa 问题 | 确定性：2n−1+1 次查询 | 1 次查询 | 指数（相对确定性算法） |
| Simon 问题 | 指数次查询 | 约 n 次查询 | 指数加速（查询模型） |
| 稀疏线性方程组 | 共轭梯度：约 O(N) | HHL：约 O(log N) | 有严苛前提的指数加速 |
| 组合优化（如最大割） | 启发式 / 近似算法 | QAOA 等 | 尚无定论 |
发展历程Timeline
从一个思想实验，到实验室里的上百个量子比特，量子计算走过了四十余年。
- 1981 – 1982
费曼提出量子模拟的设想
在 MIT 的演讲《用计算机模拟物理》中指出：要高效模拟自然，计算机本身就应当是量子的。同期 Benioff 提出了量子图灵机模型。
- 1985
Deutsch：通用量子计算机
David Deutsch 给出了通用量子计算机的理论描述，并构造了第一个比经典更快的量子算法雏形。
- 1992 – 1994
Deutsch–Jozsa、Bernstein–Vazirani、Simon
一系列“黑盒”算法展示了量子计算在查询复杂度上的指数优势，为 Shor 算法铺平了道路。
- 1994
Shor 算法
Peter Shor 发表多项式时间的量子分解与离散对数算法，量子计算从此由学术好奇变成了战略问题。
- 1995 – 1996
量子纠错与 Grover 算法
Shor、Steane 提出量子纠错码，证明“脆弱”的量子信息可以被保护；1996 年 Lov Grover 提出量子搜索算法。
- 1998 – 2001
第一批实验演示
核磁共振（NMR）系统上实现了 2 比特的 Deutsch 算法；2001 年 IBM 团队用 7 个核自旋比特完成了 15 = 3 × 5 的 Shor 分解演示。
- 2009 – 2014
新算法浪潮
HHL 线性方程组算法（2009）、变分量子本征求解器 VQE（2014）与量子近似优化算法 QAOA（2014）相继提出。
- 2019
“量子优越性”实验
Google 用 53 比特的 Sycamore 处理器完成随机线路采样，宣称经典超算需要上万年（此后经典算法不断改进，差距有所缩小）。
- 2020 – 2021
九章与祖冲之号
中国科大的光量子计算原型机“九章”完成高斯玻色采样；超导量子处理器“祖冲之二号”完成随机线路采样，中国成为第二个在两条路线上实现量子优越性的国家。
- 2023
逻辑比特时代开启
哈佛—QuEra 团队在中性原子平台上演示了 48 个逻辑比特上的算法；IBM 发布千比特级芯片 Condor。
- 2024
低于阈值的纠错 · 后量子密码标准
Google Willow 芯片首次清晰演示表面码“低于阈值”的纠错；NIST 发布首批后量子密码标准。
- 未来
容错量子计算
业界路线图普遍瞄准 2030 年前后实现可运行有用算法的容错量子计算机。届时，量子化学与材料模拟有望率先迎来真正的应用。
术语表Glossary
遇到不熟悉的词，回来这里查一查。
- 量子比特qubit
- 量子信息的基本单位，状态是 |0⟩ 与 |1⟩ 的复数线性组合，可用布洛赫球上的点表示。
- 振幅amplitude
- 叠加态中每个基态前的复数系数。其模长的平方就是测得该结果的概率。
- 叠加superposition
- 量子系统可以同时处于多个基态的线性组合中，直到被测量。
- 干涉interference
- 不同计算路径的振幅相加时相长或相消的现象，是量子算法提取答案的核心机制。
- 纠缠entanglement
- 多粒子系统的状态无法分解为各粒子状态的乘积，表现为超越经典的测量关联。
- 测量与坍缩measurement
- 按照振幅平方的概率随机得到一个经典结果，同时量子态变为与该结果对应的基态。
- 量子门quantum gate
- 作用在量子比特上的酉变换，是量子线路的基本操作，例如 H、X、CNOT。
- 相位phase
- 振幅的“角度”。单独测量看不到，但通过干涉会影响最终概率。
- 黑盒 / 预言机oracle
- 以量子方式访问的函数，常把答案编码为相位翻转。算法的效率常以调用它的次数来衡量。
- 量子傅里叶变换QFT
- 离散傅里叶变换的量子版本，只需 O(n²) 个门，是 Shor 算法与相位估计的核心。
- 退相干decoherence
- 量子系统与环境相互作用而失去量子特性的过程，是构建量子计算机的最大敌人。
- 保真度fidelity
- 衡量实际操作与理想操作接近程度的指标。两比特门保真度 99.9% 是当前前沿水平。
- 逻辑比特logical qubit
- 由许多物理比特经纠错编码而成、错误率远低于单个物理比特的“受保护”比特。
- NISQNoisy Intermediate-Scale Quantum
- John Preskill 于 2018 年提出的术语，指含噪声、几十到上千比特、尚未实现纠错的量子设备时代。
- 量子优越性quantum advantage
- 量子设备在某项具体任务上超越所有已知经典方法的情形，又称“量子霸权”。
- BQPcomplexity class
- 量子计算机能以有界错误概率在多项式时间内解决的判定问题类。
- 后量子密码PQC
- 运行在经典计算机上、但被认为能抵抗量子攻击的密码算法，例如基于格的 ML-KEM。
- CNOT 门controlled-NOT
- 两比特门：当控制比特为 1 时翻转目标比特。它与单比特门一起构成通用门集合。