量子计算与量子信息 · 第五章 量子傅里叶变换与 Shor 算法

原著: M. Nielsen & I. Chuang《Quantum Computation and Quantum Information》| 来源: 中文学习笔记 (.nb) | 生成: 2026-06-19

如何使用本 skill

• 不带参数 — 加载第五章的核心算法框架
• 带主题 — 问 QFT、相位估计、Shor、求阶、Deutsch-Jozsa、隐藏子群 等，我会读对应小节文件再回答
• 带小节号 — 问 5.5 或 sec5.5，加载该小节
• 浏览 — 问"有哪些小节？"查看完整索引

当你问的主题不在下面的核心框架里，我会先读相关小节文件再回答。

核心概念框架

量子算法的两大家族：① 基于量子傅里叶变换 (QFT) 的算法（本章：相位估计、Shor）；② 量子搜索算法（第六章 Grover）。"端到端"复杂度指解决用户整个问题的成本，而非仅运行某段量子线路的成本。核心开放问题：BQP 是否严格大于 BPP。

Deutsch / Deutsch-Jozsa（量子并行的范例）：用一次 $U_f$ 调用判断 $f$ 是常数型还是平衡型，经典需两次（$n$ 位时经典最坏需 $2^{n-1}+1$ 次）。启发：当经典计算获取的信息量超过问题答案所需信息量（存在计算冗余）时，量子有加速潜力。

量子傅里叶变换 (QFT)：把基态 $\ket{j}$ 映到 $\tfrac{1}{\sqrt{N}}\sum_k e^{2\pi i jk/N}\ket{k}$。关键在于因式分解：QFT 输出态是各比特上单比特态的张量积 $\otimes(\ket{0}+e^{2\pi i\cdot 0.j_l\dots}\ket{1})$，因而可用 $H$ + 受控相位门高效实现（$n$ 比特 $O(n^2)$ 门，对比经典 FFT 的 $O(N\log N)$）。Fourier 结果存在概率幅中，无法直接读，需巧妙利用。

相位估计：若能制备 $U$ 的本征态 $\ket{u}$（$U\ket{u}=e^{2\pi i\varphi}\ket{u}$），用受控-$U^{2^k}$ + 逆 QFT 把相位 $\varphi$ 读进计数寄存器。$\varphi$ 是完美二进制小数时估计精确，否则给出高概率的最佳近似。

Shor 算法（大数分解）：把分解 $N$ 归约为求阶——找最小 $r$ 使 $y^r\equiv 1\pmod N$。用量子相位估计对模乘算符 $U\ket{x}=\ket{yx \bmod N}$ 求阶（输入态是各本征值本征态的均匀叠加 $\ket{1}$）。经典后处理（连分数 + GCD）得到因子。威胁 RSA 加密。

隐藏子群问题 (HSP)：已知 $f:G\to X$ 隐藏了 $G$ 的子群 $H$，求 $H$ 的生成元。Deutsch-Jozsa、Simon、求阶、离散对数都是 HSP 的特例。阿贝尔群已有高效量子算法；非阿贝尔情况开放。

小节索引

主题索引

• BQP / BPP → 5.1
• Deutsch / Deutsch-Jozsa / 量子并行 → 5.2
• QFT / 因式分解 / 线路 → 5.3
• RSA / 大数分解 → 5.5
• Shor 算法 / 求阶 → 5.5
• 相位估计 / 受控-$U^{2^k}$ → 5.4
• 端到端复杂度 → 5.1
• 连分数 / GCD / 经典后处理 → 5.5
• 隐藏子群问题 (HSP) → 5.6
• 逆 QFT vs 正 QFT → 5.4, 5.5

辅助文件

• glossary.md — 关键术语表（中英对照）
• patterns.md — QFT 类算法构件与技巧
• cheatsheet.md — 算法流程与复杂度速查

范围与限制

本 skill 仅覆盖 QCQI 第五章（QFT 及其应用）的概念框架，源自一份中文 Mathematica 笔记。公式以纯文本/Unicode 近似表示。笔记中分解 21/35 的具体数值算例、Qiskit 求阶代码、概率分布图未完整转录，精确实现请参阅原书与原笔记。

5.1 量子算法预备

核心思想

为什么研究量子算法？因为某些问题量子计算机可能比经典快得多。但要看"端到端"成本——解决用户感兴趣的整个问题，而非仅运行某段量子线路。

重点与家族

• 重点介绍的两类算法：① 基于量子傅里叶变换 (QFT) 的算法（本章）；② 量子搜索算法（第六章）。
• 端到端复杂度：指完整解决方案的总成本（含数据载入、读出、经典后处理），不只是量子子程序的门数。

其他量子算法（概览）

• 1985 Deutsch 黑箱 (oracle) 算法。
• 量子通信协议：1984 Bennett & Brassard 提出 QKD（量子密钥分发）增强信息安全。
• 量子模拟算法。
• 连续优化：纳什均衡、线性规划。
• 变分量子求解器 (VQE)。
• 量子随机游走。
• 后量子（抗量子）加密 post-quantum cryptography。

量子计算的威力（核心开放问题）

• BQP 是否严格大于 BPP？ 是否存在某些问题，量子概率算法能高效解决而经典概率图灵机不能？
• 大规模的容错量子计算能否实现？

关键要点

1. 衡量量子优势要看端到端成本，不只是量子线路本身。
2. 两大算法家族：QFT 类（本章）与搜索类（第六章）。
3. $\mathrm{BQP} \supsetneq \mathrm{BPP}$? 是量子计算理论的核心未决问题。

关联

• 5.2–5.5：QFT 家族的具体算法。
• 第六章：搜索家族 (Grover)。

5.2 Deutsch 与 Deutsch-Jozsa 算法

核心思想

量子并行：量子计算机能在同一个幺正变换中同时计算 $f(x)$ 在许多 $x$ 处的值。Deutsch 算法是这一思想最简单的范例。

Deutsch 算法

• 问题：$f:\{0,1\}\to\{0,1\}$，判断 $f$ 是常数型（$f(0)=f(1)$）还是平衡型（$f(0)\ne f(1)$）。
• 常数型例子：$f(x)=0$ 或 $f(x)=1$；平衡型：$f(x)=x$ 或 $f(x)=1-x$。
• 关键：每个量子线路只用一次 $U_f$，即一次计算就完成经典需要两次计算才能完成的任务（判断 $f(0)\oplus f(1)$）。
• 机制：辅助比特置 $\ket{-}$，相位回踢使 $\ket{x}\to(-1)^{f(x)}\ket{x}$；对查询比特做 $H$ 干涉，末端测量直接读出 $f(0)\oplus f(1)$。

启发

• 对那些经典计算获得的信息量超过问题答案所需信息量的问题（即经典存在计算冗余），量子计算具有潜在加速可能。
• 判断"全局性质"（如 $f(0)\oplus f(1)$）特别适合量子并行 + 干涉。

Deutsch-Jozsa 算法

• 推广：$f$ 有 $n$ 个输入位，承诺 $f$ 要么常数要么平衡，判断属于哪种。
• 经典：最坏需 $2^{n-1}+1$ 次查询确定；量子：一次 $U_f$ 即可（确定性）。
• 对应 Nielsen Sec.1.4.4。

关键要点

1. 量子并行 = 一个幺正变换同时算多个 $f(x)$；但读出受测量限制。
2. Deutsch：一次 $U_f$ 判常数/平衡，经典需两次。
3. 计算冗余 $\Rightarrow$ 量子加速潜力；全局性质问题适合 QFT/干涉类算法。

关联

• 5.1：属于 QFT/oracle 家族的开端。
• 5.3：Deutsch-Jozsa 的干涉是 QFT 的特例（在 $\mathbb{Z}_2^n$ 上）。
• 第一章 1.4：量子并行的直觉来源。

5.3 量子傅里叶变换 (QFT)

核心思想

QFT 是经典离散傅里叶变换 (DFT) 的量子版本。它能在 $O(n^2)$ 个门内完成 $N=2^n$ 维的傅里叶变换（经典 FFT 需 $O(N\log N)$），关键在于输出态的因式分解。

经典 DFT 与 QFT 定义

• DFT/傅里叶分析：用基本波的叠加表示其他函数或信号。
• QFT：$y_j=\tfrac{1}{\sqrt{N}}\sum_k e^{2\pi i jk/N} u_k$；作用在基态上 $\ket{j} \to \tfrac{1}{\sqrt{N}}\sum_k e^{2\pi i jk/N}\ket{k}$，$j=0,\dots,N-1$。
• 可写成 bracket 算符形式与矩阵形式。

因式分解（高效实现的关键）

• 用二进制小数记号 $0.a_1 a_2\dots a_m := \sum_l a_l 2^{-l}$。
• QFT 的输出态可因式分解为各比特上单比特态的张量积：

$$\ket{j} \to \bigotimes_{l=1}^n \frac{\ket{0} + e^{2\pi i\cdot 0.j_l j_{l+1}\dots j_n}\ket{1}}{\sqrt{2}}.$$

• 每个因子是一个 qubit 上的相对相位态 $\Rightarrow$ 用 $H$ + 受控相位门逐位构造，无需展开 $N$ 维矩阵。这就是量子版的"快速傅里叶变换"。

量子线路

• 构造：对每个比特施 $H$，再施一串受控相位门 $R_k$（相位 $2\pi/2^k$），最后用 SWAP 翻转比特高低位次序。
• $n$ 比特：$H$ 与受控相位门共约 $n(n+1)/2$ 个 $\Rightarrow$ $O(n^2)$ 门。
• 验证：可检验 QFT 的幺正性；线路除高低位相反外实现了傅里叶变换（末端 SWAP 修正位序）。

关键限制

• Fourier 变换的结果储存在概率幅中，无法直接读取，只能用统计方法推断——需要更巧妙的方法加以利用（见相位估计、Shor）。

关键要点

1. QFT：$\ket{j}\to\tfrac{1}{\sqrt{N}}\sum_k e^{2\pi i jk/N}\ket{k}$。
2. 输出态可因式分解为单比特态张量积 $\Rightarrow$ $H$ + 受控相位门，$O(n^2)$ 门。
3. 结果藏在概率幅里，不能直接读，需配合相位估计等技巧。

关联

• 5.4：相位估计 = QFT 的核心应用（逆 QFT 读相位）。
• 5.5：Shor 用 QFT 求阶。
• 4.2：受控相位门是 QFT 线路构件。

5.4 相位估计

核心思想

相位估计是 QFT 最重要的应用：若能制备幺正算符 $U$ 的本征态 $\ket{u}$（$U\ket{u}=e^{2\pi i\varphi}\ket{u}$），就能用逆 QFT 把相位 $\varphi$ 读进一个计数寄存器。

算法结构

• 寄存器：$t$ 个计数比特（决定精度）+ 存放本征态 $\ket{u}$ 的比特。
• 步骤：
1. 计数比特全置 $\ket{+}$（即 $H^{\otimes t}\ket{0}$）。
2. 施一串受控-$U^{2^k}$（第 $k$ 个计数比特控制 $U^{2^k}$），相位回踢把 $\varphi$ 编码进计数比特：得到 $\sum_j e^{2\pi i\varphi j}\ket{j}$。
3. 对计数比特做逆 QFT，把相位读出为二进制整数。
4. 测量计数比特，得到 $\varphi$ 的估计。

完美 vs 不完美二进制相位

• $\varphi$ 是完美 $t$ 位二进制小数：相位估计产生的估计值就是精确值（确定性读出）。
• $\varphi$ 不完美：估计值不等于精确值，但以高概率给出最接近的 $t$ 位近似；精度与成功率随 $t$ 增大而提升。

等价线路与对易性（笔记中的要点）

• 相位估计中"作用顺序相反但等价"的线路：因为不同的受控-$U^{2^k}$ 之间相互对易，且末端 SWAP 可被移到线路最左端被初态吸收，所以 Mathematica 线路与书上黑盒的作用顺序看似相反却完全等价（作为幺正算符相等）。
• 回顾正 Fourier 变换：$\ket{j}\to\bigotimes(\ket{0}+e^{2\pi i\cdot 0.j_l\dots}\ket{1})/\sqrt{2}$，与逆 QFT 读相位互为逆过程。

关键要点

1. 相位估计 = 受控-$U^{2^k}$（相位回踢） + 逆 QFT（读相位）。
2. 需要能制备 $U$ 的本征态 $\ket{u}$。
3. 相位为完美二进制小数时精确；否则高概率给最佳近似，精度随计数比特数 $t$ 增长。

关联

• 5.3：逆 QFT 是核心子程序。
• 5.5：Shor 的求阶 = 对模乘 $U$ 做相位估计。
• 4.2/4.3：受控-$U$ 与对算符的测量。

5.5 Shor 算法（大数分解）

核心思想

Shor 算法把大数分解高效归约为求阶，再用量子相位估计求阶。它能在多项式时间分解整数，威胁基于"分解困难"的 RSA 加密。

背景：分解与 RSA

• 问题：$N$ 是奇数且至少有两个质因子，找到 $N$ 的一个非平凡因子。
• 经典最好算法（数域筛）：约 $\exp((64/9)^{1/3}(\ln n)^{1/3}(\ln\ln n)^{2/3})$，超多项式。
• RSA：安全性依赖大数分解困难；量子计算机实用化的标志性目标是分解 RSA 数（预期约 2045）。
• 工具：GCD（最大公约数）、同余基本性质。

分解 → 求阶

• 取与 $N$ 互质的 $y$，求最小 $r$（阶） 使 $y^r\equiv 1\pmod N$。
• 若 $r$ 为偶数且 $y^{r/2}\not\equiv -1\pmod N$，则 $\gcd(y^{r/2}\pm 1, N)$ 给出 $N$ 的非平凡因子（关于 $y$ 的性质与作用，及该等价性步骤的说明）。
• 例：分解 21。

用量子算法求阶

• 模乘算符：$U\ket{x} \equiv \ket{yx \bmod N}$。通常以 $x=1$（计算基第二个）为出发点；$U$ 一般只在某子空间上有定义，因此不唯一，只要能造出一个即可。
• 本征态：取 $y=3, x=1, N=35$，作用 $r$ 次回到原态。$U$ 的本征态？通用方法是矩阵对角化——loop 中各态均匀叠加即得一个本征态，乘 $e^{2\pi i/r}$ 得下一项。
• 一族本征态 $\ket{u_s}$（$s=0,1,\dots,r-1$）：满足 $U\ket{u_s}=e^{2\pi i s/r}\ket{u_s}$；这是 loop 张成子空间上全部 $r$ 个本征态。
• 关键技巧：求阶输入的态不是 $U$ 的本征态，而是若干不同本征值本征态的均匀叠加——恰好 $\tfrac{1}{\sqrt{r}}\sum_s\ket{u_s}=\ket{1}$。因此对 $\ket{1}$ 做相位估计，等概率得到某个 $s/r$。
• 经典后处理：对测得的 $s/r$ 用连分数展开恢复 $r$，再用 GCD 得因子。

正/逆 QFT 的细节

• 线路中的 $\text{QFT}^\dagger$ 改为 QFT（逆变换改为正变换）能得到完全相同的概率分布 $\Pr(k)$（两个概率分布分别给出，对称）。

关键要点

1. 分解 $\to$ 求阶 $\to$ 对模乘 $U$ 做相位估计。
2. 输入 $\ket{1}$ = 全部本征态 $\ket{u_s}$ 的均匀叠加，免去制备单个本征态。
3. 量子部分输出 $s/r$，经连分数 + GCD 经典恢复因子。
4. $U$ 不唯一，只需能实现一个即可完成 Shor。

关联

• 5.4：求阶 = 相位估计的应用。
• 5.3：QFT 是核心子程序。
• 5.6：求阶是隐藏子群问题（阿贝尔群 $\mathbb{Z}$）的特例。

5.6 隐藏子群问题 (Hidden Subgroup Problem, HSP)

核心思想

HSP 是 QFT 类量子算法的统一框架：Deutsch-Jozsa、Simon、求阶（Shor）、离散对数都是它的特例。

问题定义

• 已知函数 $f:G\to X$ 隐藏了群 $G$ 的一个子群 $H$：$f$ 在 $H$ 的每个陪集上取常值，且不同陪集取值不同。
• 目标：确定 $H$（的生成元）。
• 经典复杂度：朴素地计算 $f(G)$，复杂度 $O(\lvert G\rvert)$。

用量子算法解决

• 在群寄存器上制备均匀叠加，查询 $f$ 把陪集信息编码进态，对 $G$ 做（群上的）量子傅里叶变换，测量得到 $H$ 的"对偶"信息。
• 重复采样，得到 $H$ 的生成集 $K$ 的一组生成元。
• 图 5-5 给出框架流程。

阿贝尔 vs 非阿贝尔

• 阿贝尔群：已有高效（多项式）量子算法（QFT 在阿贝尔群上结构清晰）。
• 非阿贝尔群：一般情况仍是开放问题（如二面体群 HSP 关联格问题、对称群 HSP 关联图同构）。

关键要点

1. HSP = "给定隐藏子群的 oracle $f$，求子群生成元"，统一了多个量子算法。
2. 求阶/Shor、Deutsch-Jozsa、Simon、离散对数都是 HSP 特例。
3. 阿贝尔 HSP 已解决；非阿贝尔 HSP 开放，是量子算法前沿。

关联

• 5.5：求阶 = $G=\mathbb{Z}$ 上的 HSP。
• 5.2：Deutsch-Jozsa = $G=\mathbb{Z}_2^n$ 上的 HSP。
• 5.3：群上的 QFT 是 HSP 算法的核心。

术语表 · QCQI 第五章

BPP — 经典有界误差概率多项式时间类 (5.1) BQP — 量子有界误差多项式时间类；分解 $\in$ BQP (5.1) DFT（离散傅里叶变换） — 经典傅里叶变换，QFT 的经典对应 (5.3) Deutsch 算法 — 一次 $U_f$ 判 $f$ 常数/平衡，经典需两次 (5.2) Deutsch-Jozsa 算法 — Deutsch 推广到 $n$ 位，确定性一次解决 (5.2) GCD — 最大公约数，Shor 经典后处理用 (5.5) HSP（隐藏子群问题） — 求隐藏子群 $H$ 的生成元，统一框架 (5.6) QFT（量子傅里叶变换） — $\ket{j}\to\tfrac{1}{\sqrt{N}}\sum_k e^{2\pi i jk/N}\ket{k}$ (5.3) QKD — 量子密钥分发 (Bennett-Brassard 1984) (5.1) RSA — 基于大数分解困难的公钥加密 (5.5) Shor 算法 — 多项式时间分解，归约为求阶 (5.5) VQE — 变分量子求解器 (5.1) 二进制小数 $0.a_1 a_2\dots$ — $\sum_l a_l 2^{-l}$，QFT 因式分解记号 (5.3) 受控-$U^{2^k}$ — 相位估计中编码相位的门 (5.4) 因式分解（QFT） — 输出态 = 单比特态张量积，高效实现关键 (5.3) 奇偶/平衡型函数 — $f(0)\ne f(1)$ 或各半，Deutsch 判定对象 (5.2) model 端到端复杂度 — 解决整个问题的成本，非仅量子线路 (5.1) 模乘算符 $U$ — $U\ket{x}=\ket{yx \bmod N}$，Shor 求阶对象 (5.5) 相位回踢 — $U_f$/受控-$U$ 把信息编码到控制位相位 (5.2,5.4) 相位估计 — 受控-$U^{2^k}$+逆 QFT 读 $U$ 本征相位 (5.4) 求阶 (order finding) — 找最小 $r$ 使 $y^r\equiv 1\pmod N$ (5.5) 连分数展开 — 从 $s/r$ 恢复 $r$ 的经典算法 (5.5) 逆 QFT ($\text{QFT}^\dagger$) — 相位估计读出步骤 (5.4) 量子并行 — 一个幺正变换同时算多个 $f(x)$ (5.2) 隐藏子群（阿贝尔/非阿贝尔） — 阿贝尔已解，非阿贝尔开放 (5.6)

QFT 类算法构件与技巧 · QCQI 第五章

相位回踢读全局性质（Deutsch 范式）

何时用：问 $f$ 的全局性质（如 $f(0)\oplus f(1)$、是否平衡）。 怎么做：辅助比特置 $\ket{-}$，作用 $U_f$ 得 $(-1)^{f(x)}\ket{x}$；查询比特过 $H$ 干涉后测量。 权衡：只在"经典有计算冗余"的问题上有加速。

用因式分解高效实现 QFT

何时用：构造 QFT 线路。 怎么做：对每比特 $H$ + 一串受控相位门 $R_k$（相位 $2\pi/2^k$），末端 SWAP 修正位序；共 $O(n^2)$ 门。 权衡：结果在概率幅里，不能直接读，需配相位估计。

相位估计读 U 的本征相位

何时用：已知/能制备 $U$ 的本征态 $\ket{u}$，要其相位 $\varphi$。 怎么做：计数比特 $\ket{+}$ → 受控-$U^{2^k}$ → 逆 QFT → 测量。 权衡：$\varphi$ 非完美二进制时只得高概率近似，精度随计数比特 $t$ 增长。

Shor：分解归约为求阶

何时用：分解奇合数 $N$。 怎么做：取互质 $y$，量子求阶得 $r$；若 $r$ 偶且 $y^{r/2}\not\equiv -1$，则 $\gcd(y^{r/2}\pm 1,N)$ 是因子。 权衡：有概率 $r$ 为奇或 $y^{r/2}\equiv -1$，需换 $y$ 重试。

用本征态均匀叠加免去制备本征态

何时用：求阶时无法单独制备 $\ket{u_s}$。 怎么做：注意 $\tfrac{1}{\sqrt{r}}\sum_s\ket{u_s}=\ket{1}$，直接用 $\ket{1}$ 输入相位估计，等概率得某 $s/r$。 权衡：得到的是随机 $s/r$，需连分数 + 多次重试恢复 $r$。

把问题套进 HSP 框架

何时用：判断一个新问题是否有 QFT 类加速。 怎么做：找群 $G$ 与隐藏子群 $H$，使 $f$ 在 $H$ 陪集上取常值；阿贝尔 $G$ 有高效算法。 权衡：非阿贝尔 HSP 一般无已知高效算法。

反模式

• 试图直接读 QFT 输出幅：信息藏在幅里，必须靠干涉/相位估计提取。
• 以为 $U$ 唯一：Shor 的模乘 $U$ 只需在子空间定义，造出一个即可。
• 忘记经典后处理成本：端到端复杂度含连分数/GCD，不只量子线路。
• 正逆 QFT 混淆：求阶里 QFT 与 $\text{QFT}^\dagger$ 给相同 $\Pr(k)$，但要清楚各自语义。

速查表 · QCQI 第五章

QFT 核心公式

• QFT：$\ket{j} \to \tfrac{1}{\sqrt{N}} \sum_k e^{2\pi i jk/N} \ket{k}$，$N=2^n$。
• 因式分解：$\ket{j} \to \bigotimes_{l=1}^n (\ket{0} + e^{2\pi i\cdot 0.j_l\dots j_n}\ket{1})/\sqrt{2}$。
• 线路：每比特 $H$ + 受控相位门 $R_k$ + 末端 SWAP；门数 $O(n^2)$。
• 二进制小数：$0.a_1 a_2\dots = \sum a_l 2^{-l}$。

算法流程速记

相位估计精度

• $\varphi$ 是完美 $t$ 位二进制小数 → 估计精确。
• 否则 → 高概率给最佳 $t$ 位近似；$t\uparrow \Rightarrow$ 精度↑、成功率↑。

Shor 决策流程

1. $N$ 偶？→ 直接除 2。
2. $N=a^b$？→ 取根。
3. 取随机 $y$，$\gcd(y,N)>1$？→ 直接得因子。
4. 量子求阶得 $r$。
5. $r$ 奇 或 $y^{r/2}\equiv -1\pmod N$？→ 换 $y$ 重试。
6. 否则 $\gcd(y^{r/2}\pm 1, N)$ = 非平凡因子。

复杂度对比

HSP 速记

• 框架：$f:G\to X$ 隐藏子群 $H$，求 $H$ 生成元。
• 特例：Deutsch-Jozsa($\mathbb{Z}_2^n$)、Simon、求阶/Shor($\mathbb{Z}$)、离散对数。
• 阿贝尔：高效解决；非阿贝尔：开放。

核心提醒

• Fourier 结果藏在概率幅，不可直接读。
• 求阶输入 $\ket{1}$ = 所有本征态均匀叠加（免制备）。
• 端到端成本含经典后处理（连分数、GCD）。