5.4 Shor、Grover 与 QFT：王牌算法的噪声存活率

5.4 Shor、Grover 与 QFT：王牌算法的噪声存活率

本节摘要：量子傅里叶变换是王牌算法共用的发动机，肖尔靠它求周期、相位估计靠它提精度、格罗弗靠振幅放大实现平方加速。本节在三比特沙盘上完整跑通格罗弗搜索，然后把王牌算法的深度账单与第 3 章的保真度预算对账——看清它们为何必须等防线建成才能登场。

一张被广泛误读的成绩单

谈起王牌算法，流传最广的是一句含混的总结："量子计算机能破解一切加密。"把成绩单摊开看，真相要具体得多：肖尔算法威胁的是依靠大数分解与离散对数的公钥体系，对对称加密（如分组密码）只能靠格罗弗的平方加速，而那点加速被"密钥长度加倍"就地化解。更关键的是第三行账：这两支王牌都是深度怪物——肖尔算法分解密码学长度的整数需要以十亿计的逻辑门操作，格罗弗攻击一百二十八位密钥需要约二十位二进制次（一点八乘十的十九次方）迭代。对照第 3 章的保真度预算，这种深度在任何未纠错的器件上都活不过第一微秒。王牌不是不能打，是必须等第 4 章的防线交付之后。本节先把发动机拆给你看，再把账单算给你看。

一、QFT：王牌算法共用的发动机

量子傅里叶变换把计算基下的振幅向量做离散傅里叶变换：|x\rangle \mapsto \frac{1}{\sqrt{N}}\sum_y e^{2\pi i xy/N}|y\rangle，其中 N = 2^n。线路由哈达玛与受控相位门叠成，精确实现深度为平方级，工程上常用近似版本把深度压到对数乘线性。它为什么是发动机？因为"找周期"这件事在频域里一眼可见：一个带周期的态经过 QFT，振幅会聚拢在与周期对应的频率峰上——测量到的随机性背后是确定的频域结构。肖尔算法的全流程因此清晰：经典数论把分解问题化归为求模幂函数的阶（周期），量子侧用相位估计喂给 QFT 读出周期信息，剩下的辗转相除交回经典计算机。相位估计本身也是 QFT 的直接应用——求么正算符本征值的精度工具，它贯穿了 5.2 节变分算法的启发源头、哈密顿模拟与振幅放大之外的第三条算法主干。

格罗弗是另一族打法。几何图像干净利落：均匀叠加态里目标态的振幅极小，"神谕翻转目标振幅符号，再对平均振幅做一次反射"，两步构成一次放大，每轮把目标振幅向一推进恒定角度。最优迭代次数约为 \frac{\pi}{4}\sqrt{N}——平方加速的来源，也是它的上限：指数加速只有肖尔这类利用代数结构的算法才有，对无结构的黑箱搜索，平方根已是量子力学的全部馈赠。

二、演练：三比特沙盘上的格罗弗

八个候选里找一个目标，经典平均要试四次，格罗弗只需两轮放大。沙盘上把它完整跑一遍：

# grover3.py：三比特格罗弗搜索目标 |101>（仅标准库）
import math

class Sim:
    """最小态矢量模拟器（与 5.1 同源，位序约定一致）。"""
    def __init__(self, n):
        self.n = n
        self.state = [complex(0)] * (1 << n)
        self.state[0] = 1

    def hadamard_all(self):
        s = 1 / math.sqrt(2)
        for q in range(self.n):
            for idx in range(1 << self.n):
                if (idx >> q) & 1:
                    continue
                i0, i1 = idx, idx | (1 << q)
                a0, a1 = self.state[i0], self.state[i1]
                self.state[i0] = (a0 + a1) * s
                self.state[i1] = (a0 - a1) * s

    def oracle_mark(self, target):
        self.state[target] *= -1              # 翻转目标振幅符号

    def diffusion(self):
        mean = sum(self.state) / len(self.state)
        self.state = [2 * mean - a for a in self.state]   # 对平均振幅反射

    def probs(self):
        return [abs(a) ** 2 for a in self.state]

TARGET = 0b101                                   # 目标：比特串 101
sim = Sim(3)
sim.hadamard_all()
print("初始目标概率:", round(sim.probs()[TARGET], 4))   # 0.125
for it in range(1, 3):                           # 最优迭代次数 round(pi/4*sqrt(8)) = 2
    sim.oracle_mark(TARGET)
    sim.diffusion()
    print(f"第 {it} 轮放大后目标概率: {sim.probs()[TARGET]:.4f}")
best_iter = round(math.pi / 4 * math.sqrt(8))
print(f"理论最优迭代次数: {best_iter}；再继续放大反而回落（过转）")
​

输出把放大几何演示得明明白白：目标概率从零点一二五起步，一轮放大到接近零点八，两轮到零点九五附近；再放大会越过峰值回落——振幅是在圆周上转动的，转过头就得重来，这个"过转"是格罗弗算法实践中最常被忘记的坑。代码里还有一处值得驻足：神谕与扩散算子在沙盘里都是免费的整表操作，真机上它们要分解成完整线路（目标比特越多，神谕的线路越深），所以"平方加速"说的是查询次数，不是总门数——攻击实际密码时，总门数才是预算口径，这正是下一节对账的重点。

表：王牌算法的深度账单与出场条件

三、对账：把王牌放进第 3 章的预算

用 3.3 节的算法给肖尔算一笔裸线路的账：深度取十亿门、双门保真度取百分之九十九点九五（离子阱的当代最好水平），存活率是零点九九九五的十亿次方——换成标准计数就是彻底归零，连"随机输出"都算不上体面。同样的算法放进第 4 章的防线里重算：码距九的逻辑比特，每逻辑门开销百级物理比特、九轮循环，十亿逻辑门对应千亿量级的物理门操作、按纠错循环频率跑数小时——这就是"百万到千万物理比特"路线图的出处。两笔账一对照，本章开头那句结论便有了全部数字支撑：王牌算法的战场在容错时代，而当下设备上真正能打的，是 5.2 节那类浅线路战术。

给软件工程师的迁移路径也顺手铺好：上述沙盘逻辑对应到工业框架里，格罗弗的神谕（oracle）与扩散层都有现成积木，Qiskit 的示例库可跑出同款概率分布——把沙盘代码逐块翻译成框架调用，是检验你是否真懂放大几何的最好练习。

本节要点回顾

• QFT 是共用发动机：周期信息在频域聚峰，肖尔与相位估计都靠它读出。
• 平方加速是格罗弗的全部馈赠：迭代次数约根号 N，存在"过转"回落的几何上限。
• 查询次数不等于门数：神谕与扩散分解成线路后的深度才是预算口径。
• 裸线路账必归零：十亿深度对百分之九十九点九五的保真度，存活率是零点九九九五的十亿次方。
• 容错账单对得上路线图：防线内重算肖尔，得到"百万级物理比特、数小时"的当代估算区间。

战术层收官。下一章走出沙盘与理论：带着全部防御视角，去看应用战场、产业格局与通向容错的路线图。