量子算法：Shor 与 Grover

导语：用量子力学破解数学难题

1994 年，Peter Shor 在贝尔实验室发现：量子计算机可以在多项式时间内完成大整数因数分解。这个消息震动了整个密码学界——因为 RSA 加密的安全性就建立在"大整数分解是计算困难问题"的假设上。

两年后，Lov Grover 发现了另一个量子优势：在未排序数据库中搜索特定元素，量子计算机只需 √N 次查询，而经典计算机平均需要 N/2 次。

这两个算法揭示了量子计算的真正力量：利用量子叠加和量子傅里叶变换，在特定结构上实现指数级或平方根级加速。

一句话总结：Shor 算法威胁 RSA/GPG/SSL 的安全基础，Grover 算法让对称加密密钥有效长度减半——它们定义了量子计算对传统密码学的冲击边界。

1. Shor 算法 ：量子因数分解

1.1 问题背景

经典因数分解的最好算法（通用数域筛 GNFS）的子指数复杂度约为：

O(exp((64/9)^(1/3) * (ln N)^(1/3) * (ln ln N)^(2/3)))

分解一个 2048 位的 RSA 密钥，经典计算机需要数千年

Shor 算法的量子复杂度是 O((log N)³)——多项式时间！

1.2 Shor 算法的核心思想

因数分解被归约为一个经典易解的问题：

问题：分解 N = p × q

步骤1：随机选择 a < N，检查 gcd(a, N)
       如果 gcd > 1，直接找到因子（幸运）
       如果 gcd = 1，继续

步骤2：找到 a 模 N 的阶 r：
       a^r ≡ 1 (mod N)
       
       如果 r 是偶数：
           a^(r/2) ± 1 可能与 N 有非平凡公因子
           gcd(a^(r/2) ± 1, N) 可能就是 p 或 q

关键洞察：找到阶 r 是困难的经典问题，但量子计算机可以通过**量子傅里叶变换（QFT）**高效完成。

1.3 量子部分：周期查找

"""
Shor 算法的量子电路（简化版，以 N=15, a=7 为例）

需要 2n 个量子比特（n = ⌈log₂N⌉）
N=15 → n=4 → 需要 8 个量子比特

量子寄存器1: |0⟩^(⊗4)  ---H gates---QFT⁻¹---Measurement
                      │
                      │ 控制-U^2^j 操作
                      │
量子寄存器2: |1⟩      ─────────────────────────────

步骤：
1. 寄存器1 进入叠加态：Σ|x⟩
2. 计算 f(x) = a^x mod N（量子并行）
3. 对寄存器1 应用逆量子傅里叶变换
4. 测量得到周期 r 的近似值
5. 经典后处理得到 r
"""

# 模拟：N=15, a=7
# f(x) = 7^x mod 15 的周期
# 7^0=1, 7^1=7, 7^2=4, 7^3=13, 7^4=1, ...
# 周期 r = 4

# 因为 r=4 是偶数
# a^(r/2) = 7^2 = 4
# gcd(4+1, 15) = gcd(5, 15) = 5 ✓
# gcd(4-1, 15) = gcd(3, 15) = 3 ✓
# 所以 15 = 3 × 5

1.4 量子傅里叶变换（QFT）

QFT 是量子算法中最重要的子程序之一：

import numpy as np

def qft(n):
    """
    n 量子比特的量子傅里叶变换矩阵
    QFT|j⟩ = (1/√(2^n)) Σ_k e^(2πijk/2^n) |k⟩
    """
    N = 2**n
    omega = np.exp(2j * np.pi / N)
    return np.array([[omega**(j*k) for k in range(N)] for j in range(N)]) / np.sqrt(N)

# QFT 将周期信号转换为频率域
# 这正是 Shor 算法能从叠加态中提取周期的数学机制

1.5 实际挑战

Shor 算法虽已证明理论可行性，但实际运行仍面临巨大挑战：

乐观估计：有容错能力的量子计算机可能在 2030 年代中后期实现 Shor 算法。

一句话总结：Shor 算法的理论威力毋庸置疑，但从理论到实践需要数千个物理量子比特、纠错码、极低错误率——目前最先进的量子计算机离这个目标还有 1-2 个数量级的差距。

2. Grover 算法：量子搜索加速

2.1 问题定义

给定 N 个未排序元素的列表和一个判定函数 f，找到使得 f(x) = 1 的 x。

# 经典搜索：平均需要 N/2 次查询
# Grover 量子搜索：只需要 O(√N) 次查询

# 对于 N = 1,000,000
# 经典：~500,000 次查询
# Grover：~1,000 次查询
# 加速比：√N

2.2 Grover 算法的几何直觉

Grover 算法的迭代过程（几何可视化）：

                             |好⟩ (目标态)
                              ↑
                             /|
                            / |
                           /  |
     初始态 |s⟩ ───────► /   │
    (均匀叠加)          /    │ ← 每次 "Grover 扩散"
                       /     │   将振幅向 |好⟩ 旋转
                      /      │
                     /       │
                     ─────────┼─── 正交于 |好⟩ 的平面
                              │
                              ↓
                            |坏⟩ (非目标态)

角度 θ：sin(θ) = √(M/N)，M 是目标数量
每次迭代旋转 2θ
经过约 (π/4)√(N/M) 次迭代后，|好⟩ 的振幅达到最大

2.3 Grover 扩散算子

import numpy as np

def grover_oracle(n, marked_state):
    """
    构造 Oracle：翻转标记态的相位
    """
    N = 2**n
    oracle = np.eye(N)
    oracle[marked_state, marked_state] = -1  # 标记态相位翻转
    return oracle

def grover_diffusion(n):
    """
    Grover 扩散算子：关于平均振幅的反射
    """
    N = 2**n
    s = np.ones(N) / np.sqrt(N)  # 均匀叠加态
    return 2 * np.outer(s, s) - np.eye(N)

def grover_search(n, marked_state):
    """
    完整的 Grover 搜索（模拟）
    """
    N = 2**n
    iterations = int(np.pi / 4 * np.sqrt(N))
    
    # 初始态：均匀叠加
    state = np.ones(N) / np.sqrt(N)
    
    oracle = grover_oracle(n, marked_state)
    diffusion = grover_diffusion(n)
    
    for _ in range(iterations):
        state = oracle @ state      # Oracle：标记目标
        state = diffusion @ state   # 扩散：放大目标振幅
    
    return state

# 演示：在 8 个元素中搜索
n = 3  # 3 个量子比特，N=8
marked = 5  # 目标状态是 |101⟩

result = grover_search(n, marked)
print("测量概率分布:")
for i, prob in enumerate(np.abs(result)**2):
    marker = " <-- TARGET" if i == marked else ""
    print(f"|{i:03b}⟩: {prob:.4f}{marker}")

# 输出：|101⟩ 的概率接近 1

2.4 Grover 的最优性

Grover 算法是最优的——没有任何量子算法可以在少于 O(√N) 次查询内解决未排序搜索问题。这已经被数学证明（Bennett-Bernstein-Brassard-Vazirani 下界）。

这意味着：

• 对于密码学中的密钥搜索，量子计算机可以将 128 位密钥的有效安全性降为 64 位
• 对于数据库搜索，量子优势是平方根级，不是指数级

一句话总结：Grover 算法通过振幅放大（Amplitude Amplification）将正确解的概率从 1/N 提升到近 1，搜索速度提升 √N 倍——这是量子计算"无条件最优"的结果。

3. 量子优势的边界

3.1 什么样的算法能用量子加速？

3.2 量子计算不能做什么

• 不能替代所有计算：只有特定结构的问题才能量子加速
• 不能解 NP 完全问题：Grover 给出 √N，但 P=NP 仍未知
• 不能无限制并行：测量破坏叠加，n 量子比特只能读出 n 个经典比特
• 不能即时通信：纠缠不能用于超光速通信（不违反相对论）

一句话总结：量子计算是"专用加速器"而非"通用超级计算机"——它在周期查找、量子模拟、无结构搜索上有量子优势，但对大多数日常计算任务并无帮助。

4. 总结

这两个算法定义了"后量子密码学"的范围：

• 需要被替换：RSA、DH、ECC（所有基于因数分解/离散对数的算法）
• 需要升级：AES-128 → AES-256，SHA-256 → SHA-384/512
• 不受影响：对称加密、哈希函数（Grover 仅平方根加速）

延伸阅读：

• 量子计算对密码学的影响与后量子密码 — 如何在量子时代保护信息安全
• Qiskit 与 Python 量子编程实战 — 动手实现这些算法