【量子】三大量子算法直觉课：Deutsch-Jozsa、Grover 与 Shor【系列第 3 篇】
量子计算系列 · 第 3 篇
第 1 篇聊「能改变什么」，第 2 篇讲「qubit 是什么」。本篇进入 算法——三个里程碑式算法，分别回答三个不同的问题：
量子能不能比经典「少问几次就分出两类函数」？能不能更快搜到目标？能不能更快分解大整数？
先建立坐标系：量子加速不是同一种加速
| 算法 | 问题类型 | 经典复杂度 | 量子复杂度 | 实际影响 |
|---|---|---|---|---|
| Deutsch-Jozsa | 判断函数是否「恒定」 | O(2ⁿ⁻¹) 最坏 | O(1) 一次查询 | 教学意义 > 工程 |
| Grover | 无序数据库搜索 | O(N) | O(√N) | 对称密码学密钥长度建议加倍 |
| Shor | 大整数分解 / 离散对数 | 亚指数（经典最优） | 多项式 | 威胁 RSA/ECC，推动 PQC |
三者的共同点：利用干涉（interference）把「错误答案」的概率幅抵消，「正确答案」的概率幅放大——而不是「2ⁿ 个并行宇宙各算一遍再汇总」。
算法一：Deutsch-Jozsa ——「问一次就够」的教科书开场
问题设定
有一个隐藏函数 f: {0,1}ⁿ → {0,1}，承诺属于两类之一：
- 恒定（constant）：所有输入输出相同，如 f(x)=0 或 f(x)=1
- 平衡（balanced）：恰好一半输入得 0、一半得 1
经典算法最坏要查 2ⁿ⁻¹ + 1 次才能确定类别。
Deutsch-Jozsa（DJ）算法：1 次 对 f 的「量子查询」即可判定。
直觉（n=1 的最简版）
|0⟩ ──H──●──H── 测 → 0 则 constant，1 则 balanced
|1⟩ ──H──⊕──H──
f
- 第一个 H 制造叠加：同时「询问」f(0) 与 f(1) 的输入
- Oracle（黑盒 f）把相位写入：f(0) 时 |0⟩ 不变，f(1) 时 |1⟩ 取负——**相位 kickback**
- 第二个 H 让路径 **相长 / 相消干涉**
- 测量：恒定函数 → 一定测得 0；平衡函数 → 一定测得 1
### 为什么重要、为什么不常用
**重要**：历史上 **第一个严格证明** 量子计算可在特定任务上 **指数级减少查询次数**。
**不常用**：现实世界很少遇到「函数承诺恒定或平衡」这种人造约束；它是 **理解 oracle + 干涉** 的训练轮。
---
## 算法二：Grover —— 无序搜索的 √N 加速
### 问题设定
在 N = 2ⁿ 个条目中，恰好 1 个标记为「目标」。经典最坏要试 **N 次**；Grover 约 **π/4 · √N** 次。
### 几何直觉：在 Bloch 空间里旋转
把「目标态 |t⟩」和「其余均匀叠加态」张成二维平面：
1. **Oracle**：对 |t⟩ 做 **相位翻转**（乘以 -1）
2. **Diffusion（扩散算子）**：对均匀态做反射——「关于平均值的镜像」
每重复一轮 Oracle + Diffusion，状态向量 **向 |t⟩ 旋转约 2θ**，其中 sin θ ≈ 1/√N。
大约 **√N 轮** 后，测得 |t⟩ 的概率接近 1。
初始均匀态
↘ Oracle 翻转目标相位
↘ Diffusion 放大差异
↘ 重复 ~√N 次
→ 高概率测中目标
能加速什么、不能加速什么
| 适用 | 不适用 |
|---|---|
| 暴力破解对称密钥（AES 密钥搜索） | 排序（有结构的问题，经典更优） |
| SAT、图问题在某些启发式框架里作子程序 | 任意 NP 问题自动多项式加速（没有这种通用结果） |
| 组合优化（配合 QAOA 等变分方法） | 「把 Grover 套在 LLM 训练上」——不成立 |
对安全的实际含义
Grover 把 对称密码 的有效密钥长度减半（128 位 AES → 量子下约等价 64 位经典搜索难度，但仍需极大量子资源）。
所以 AES-256 在 post-quantum 语境下仍是合理选择；真正急的是 RSA/ECC（见 Shor）。
算法三：Shor —— 改变复杂度「类别」的分解算法
问题设定
给定合数 N，求一个非平凡因子。
RSA 的安全性建立在：经典计算机分解大整数「 практически不可行」。
Shor（1994）证明：在量子计算机上，分解 N 可在 多项式时间 完成——不是快常数倍，是 从亚指数到多项式 的跃迁。
核心思路：分解 ≈ 找周期
- 随机选 a < N，求 gcd(a, N)；若 >1 则 lucky，直接得因子
- 否则考虑函数 f(x) = aˣ mod N 的 周期 r
- 经典：求周期很难
- 量子：量子相位估计（QPE） + 量子傅里叶变换（QFT） 提取周期
量子傅里叶变换（QFT）在干什么
经典离散傅里叶变换：O(N log N)。
量子 QFT 对 n 个 qubit 的状态：O(n²) 个门——对 2ⁿ 维向量做 FFT 的量子版本。
QPE 把「本征相位 φ」读出来，φ 与 aˣ mod N 的周期 r 相关；
知道 r 后，用经典算法 gcd(a^(r/2) ± 1, N) 得到因子。
威胁有多大、什么时候成真
| 因素 | 现状（2026 视角） |
|---|---|
| 算法 | Shor 已成熟 |
| 硬件 | 分解 RSA-2048 估计需 数百万逻辑 qubit + 极长相干时间 |
| 时间线 | 业界常提 2030s–2040s 才可能威胁现行 RSA |
| 对策 | NIST PQC 已标准化 ML-KEM、ML-DSA 等，迁移应 现在启动 |
Harvest Now, Decrypt Later：对手今天截获密文，等量子机成熟再解密——长期保密数据（政府、医疗、基础设施）尤其紧迫。
三算法对比：一张表带走
| DJ | Grover | Shor | |
|---|---|---|---|
| 年代 | 1992 | 1996 | 1994 |
| 加速类型 | 查询复杂度指数 | 搜索平方 | 分解/离散对数 指数→多项式 |
| 核心工具 | 相位 kickback + H | Oracle + Diffusion | QFT + QPE |
| 工程价值 | 低（玩具问题） | 中（对称密码、优化子程序） | 高（公钥密码存亡） |
| 学习价值 | 入门干涉 | 理解振幅放大 | 理解 QFT 与密码学 |
伪代码级流程（Grover，n=3 即 N=8）
# 概念流程，非完整 Qiskit
n = 3
qc = uniform_superposition(n) # H⊗n |0⟩
iterations = int(pi/4 * sqrt(2**n)) # ≈ 2 次 for N=8
for _ in range(iterations):
qc.oracle_mark_target(t) # 目标相位 -1
qc.diffusion() # 关于平均反射qc.measure_all()
# 高概率得到 |t⟩
```
Shor 的完整电路 远更复杂（模幂、QFT、经典后处理），建议用 Qiskit 教程 shor 模块跑小 N（如 15=3×5）看整体 pipeline，不必手推每个门。
常见误解澄清
| 误解 | 正解 |
|---|---|
| 「Grover 能破解 AES」 | 只能 平方级加速暴力搜索；AES-256 仍安全裕度大 |
| 「Shor 一出来 HTTPS 全废」 | 需大规模 容错 机；且 PQC 可替换握手算法 |
| 「DJ 证明了量子计算机万能」 | 只针对 极特殊承诺 的 oracle 问题 |
| 「有量子算法就能在 NISQ 上跑 Shor 分解 RSA」 | 当前噪声规模 远不够；Shor 演示多在 tiny N |
与 AI / 数据科学的关系（本系列为何写在这里）
- Grover 可加速 无结构搜索——某些超参搜索、哈希碰撞、特征子集暴力筛选在理论上受益（常数大，实际慎用）
- Shor / 后量子 影响 模型部署、联邦学习、API 密钥 的长期加密方案
- QFT / 相位估计 是 量子机器学习 里很多变分算法的数学 cousin
- 理解「 什么能加速、什么不能 」——避免被「量子 AI 1000 倍训练」营销忽悠
系列导航
| 篇序 | 主题 | 状态 |
|---|---|---|
| 第 1 篇 | 容错量子机若今日可用，能改变什么 | 已发 /forum/12/ |
| 第 2 篇 | 量子比特：叠加、纠缠、测量 | 待发 forum-quantum-series-02.md |
| 第 3 篇 | 三大算法：DJ、Grover、Shor | 本文 |
| 第 4 篇 | 量子纠错：物理比特 vs 逻辑比特 | 待写 |
| 第 5 篇 | 量子机器学习： hype 与真实用例 | 待写 |
| 第 6 篇 | 普通人如何入门：Qiskit、学习路径 | 待写 |
下一篇预告：为什么 Google 用 1000 个物理 qubit 才换 1 个「逻辑 qubit」？表面码、阈值定理、以及 NISQ 与容错之间还差什么。