量子算法：到底能加速什么

7.1 先建立一个「加速等级」概念

复杂度描述资源如何随输入规模增长，但先要问清「规模」是什么：分解整数 M 时，输入长度是 n = ⌈log₂(M+1)⌉ 位；搜索时，N 是候选条目数，若用 n 个比特编号，则 N = 2ⁿ。多项式时间指相对于输入长度，不是相对于整数的数值。

量子模拟的时间演化优势有适用条件，详见 7.5。判断宣传要问：相对谁、什么成本、哪个问题版本？

7.2 Deutsch-Jozsa 算法：第一个「量子更快」的演示

问题：有一个黑盒函数 f，输入 n 位二进制数，输出 0 或 1。已知它要么是「常数函数」（对所有输入输出相同），要么是「平衡函数」（一半输入输出 0、一半输出 1）。问：它是哪一种？

• 经典确定性、精确方法：最坏情况下查询 2^(n-1) + 1 次；
• 理想量子算法：查询 1 次，再通过干涉精确区分两类。

这里有两层限定。第一，它是一个承诺问题：不属于常数或平衡的函数不在题目保证范围内。第二，比的是 oracle 查询，不含构造黑盒所需的门数。若允许经典随机算法有少量误判，独立均匀抽 k 个输入；只要见到两种输出就判平衡，否则判常数。平衡函数被误判的概率为 2^(1-k)，因此固定误差容忍度下，只需少量查询，与 n 无关。

干涉为什么有效？将输入置于均匀叠加，用 f(x) 写入正负相位，再作用 Hadamard 门。全零结果的概率幅为 Σₓ(-1)^f(x)/2ⁿ：常数时为 ±1，平衡时为 0。它展示的是特定查询模型中的优势，不能据此宣称对随机经典计算也有指数级优势。

7.3 Grover 搜索算法：平方级加速

问题：在 N 个无结构候选项中，找到唯一满足条件的目标，并且有一个可计算的验证函数 f(x)。

• 经典方法：平均约 N/2 次验证，最坏 N 次；
• 理想 Grover 算法：约 (π/4)√N 次 oracle 查询，达到高成功概率。

原理：每轮先给满足 f(x)=1 的候选幅「标负」，再做「关于平均值的翻转」。oracle 是验证器，不需预先知道答案；实际要实现可逆验证线路，并反向计算清理辅助比特，中间步骤也消耗资源。

N=4 手算：按 |00⟩、|01⟩、|10⟩、|11⟩ 排列，初始幅为 (0.5,0.5,0.5,0.5)，假设目标是 |11⟩。标负后为 (0.5,0.5,0.5,-0.5)，平均值 ā=0.25。对每项做 a→2ā-a，得到 (0,0,0,1)，因此一次迭代后理想测量必得目标。这里动的是幅，不是直接把概率「加大」；迭代过多反而可能转过头，成功率下降。

冷静看待：平方级优势在足够大的问题上可能非常重要，也可能被 oracle 构造、容错和数据访问开销抵消。它不是把现成硬盘扫描自动加速，也不等于墙钟时间缩短 √N 倍。对理想无结构密钥搜索，k 位密钥的查询量从约 2ᵏ 变为约 2^(k/2)；AES-256 可为这类搜索提供更大余量，但真实攻击还受电路深度和并行资源限制。增加 AES 密钥长度不能修复 RSA/ECC、协议实现或密钥管理问题。

7.4 Shor 算法：公钥密码的重要挑战

问题：把一个合数分解成质因数。例如 15 = 3 × 5 很简单，但针对通常选取的 RSA-2048 模数，已知经典通用分解方法的成本极高；不能把这一判断推广到任意一个容易分解的 2048 位整数。

RSA 的安全依赖大数分解困难等密码学假设；椭圆曲线密码（ECC）依赖相应群上的离散对数困难性。足够可靠的量子计算机可以用 Shor 类算法解决这两类数学问题。

• 已知经典通用分解算法：相对于输入位数 n 为亚指数时间；
• Shor 算法：相对于 n 为多项式时间。这是相对已知经典方法的超多项式优势，不是已证明所有经典算法都需要指数时间。

原理（极简版）：Shor 将分解归约为寻找特定模幂函数 f(x)=aˣ mod M 的周期。量子周期查找借助量子傅里叶变换，让测量分布携带周期信息，再由经典后处理提取因子；不是任意周期问题都存在同样加速。

现实距离：大整数分解需联合预算物理比特、逻辑门与时间。Craig Gidney 的 2025 年研究 基于特定二维连接、物理错误率、纠错周期和控制响应假设，属于容错架构估算，不是 RSA-2048 实机分解记录或破解日期预测。

为什么防护要提前：「先收集、后解密」指攻击者保存今天的密文，等待未来能力成熟再尝试恢复明文。因此应按数据保密期限、密码资产及迁移周期规划后量子密码（PQC）替换，而不是等到可用攻击机器出现才开始盘点。

7.5 量子模拟：最「本职」的应用

回到费曼的初衷：用量子计算机模拟分子、材料、化学反应。

• 经典通用完整态矢量表示随比特数指数增长，但张量网络、对称性和近似方法能高效处理不少特殊系统；
• 对可有效描述、局域或满足适当稀疏性等条件的 Hamiltonian H，量子算法可在合适输入访问模型下高效近似时间演化 e^(-iHt)，成本还依赖演化时间 t、精度与相互作用强度。

「能模拟演化」不等于「能便宜地准备想要的初态」「能找到任意基态」或「能读出整个波函数」。一般局域 Hamiltonian 基态能量问题可达 QMA 难度，不存在已知通用高效量子解法；蛋白折叠、药物结合还包括构象搜索、溶剂和建模误差，不能视为自动解决。实际任务通常只读出能量、关联函数等少量观测量，精度越高，态制备与重复采样成本可能越大。

典型目标包括：

• 固氮酶中的 FeMoco 分子：理解它能帮助设计更节能的化肥生产方式；
• 药物分子与靶点蛋白的结合；
• 高温超导机理；
• 新型电池和催化材料。

量子化学和材料模拟是重要候选方向，但具体实例是否产生商业收益，仍需与同精度的适用经典算法比较。

7.6 变分算法 VQE 与 QAOA：混合算法的探索

由于今天的量子计算机有噪声、没有大规模纠错，研究者设计了适合 NISQ 时代（第 8 章解释）的混合算法：

• VQE（变分量子本征求解器）：用来求分子的基态能量，服务于量子化学；
• QAOA（量子近似优化算法）：用来求解组合优化问题，如路径规划、排产、投资组合。

流程是第 6 章的「经典优化器 + 量子线路」循环。可选择较浅的参数化线路，但达到目标精度可能需要更深线路，并非天然抗噪声。VQE 在理想、精确期望值下利用变分原理给出基态能量上界，却不保证拟设能表达基态，也不保证优化器找到全局最优；有限采样和器件误差还会影响估计。QAOA 的层数同样影响表达能力与成本。某些线路和损失函数会出现贫瘠高原：梯度随规模变得极小，估计梯度需要大量 shots。最终要核算整个优化循环，而不是只比一次线路。

7.7 量子机器学习：需要特别冷静

「量子 + AI」是热门话题，但目前要非常谨慎：

1. 很多量子机器学习算法假设能高效把海量经典数据「装载」进量子态，而这一步本身可能就很慢，会抵消加速；
2. 有些早期号称指数加速的算法，后来被证明经典算法也能做到类似效果（这叫「去量子化」）；
3. 大模型训练依赖成熟的 GPU 矩阵运算栈，量子方案的端到端普遍优势尚未建立，不能据此规划对 GPU 的直接替换。

更现实的方向是：AI 帮助设计量子线路、优化纠错解码；量子计算在特定子任务上为 AI 提供补充。

7.8 量子计算不擅长什么

7.9 从复杂度到资源预算：先列完整账单

云端任务的账单是：数据编码 → 编译映射 → 排队与校准 → 线路重复运行 → 经典后处理与优化，墙钟时间取决于串行关键路径和批处理能力。

记录逻辑比特数、双比特门数、深度、测量设置数、shots、优化轮数与目标误差。oracle 要展开成可逆门，容错要加入纠错周期和辅助态。假设一次能量评估有 100 个测量设置、每个 1000 shots，就是 10 万次执行；优化 100 轮约 1000 万次，尚未包含梯度额外评估。这是示例而非 VQE 固定用量。经典对照也必须达到相同精度和成功率。

本章小结

• Shor 相对已知经典通用分解方法有超多项式优势，Grover 有平方级查询优势；两者都不是无条件的整机加速承诺。
• AES 更长密钥可提高抵抗无结构量子搜索的余量，不能替代 RSA/ECC 的后量子迁移。
• 「先收集、后解密」要求提前盘点需要长期保密的数据与密码资产。
• 量子模拟的时间演化结果不等于任意基态、折叠或优化问题的通解。
• 算法优势应以相同精度、成功率与端到端资源衡量。