第五章 量子傅里叶变换与 Shor 算法 · 人话版

导读

这一章是量子算法里"最赚钱"的一支：先讲清楚量子并行到底快在哪，再造出量子版的傅里叶变换 (QFT)，然后用它搭出相位估计这把"万能扳手"，最后用相位估计把 RSA 赖以生存的大数分解给端了（Shor 算法）。如果你是程序员，可以这样理解整章：QFT 是底层库，相位估计是基于这个库写的通用函数，Shor 是它的一个杀手级应用，HSP 则是把这些算法统一起来的抽象接口/基类。 全程只需要记住一句话：量子能"同时算所有输入"，但你每次只能读出一个结果，所以真正的艺术是"怎么把答案逼到你想读的那个比特上"。

5.1 量子算法预备：为什么量子可能更快

大白话：研究量子算法不是为了炫技，而是想找那些量子机器真的比经典机器快的问题。但要算账要算"端到端"的总成本——从数据装进去、算、读出来、到经典后处理全部加起来，而不是只盯着中间那段量子线路跑得多快。

💡 人话： 别只看 benchmark 里那个量子内核的耗时。装载输入、测量读出、经典后处理（解码答案）都得计入。很多"量子加速"在端到端口径下就缩水了。

本章重点是两大算法家族：

1. QFT 家族（本章）——相位估计、Shor，靠傅里叶变换提取"全局/周期"信息。
2. 量子搜索家族（第六章 Grover）——靠振幅放大在无结构数据里捞针。

理论上最核心的未决问题是：

$$\mathrm{BQP} \overset{?}{\supsetneq} \mathrm{BPP}$$

• $\mathrm{BPP}$：经典概率算法能在多项式时间、有界错误率内解决的问题类（"经典随机算法搞得定的"）。
• $\mathrm{BQP}$：量子版的同一个类（"量子算法搞得定的"）。
• $\supsetneq$：严格包含。整个式子在问：是否存在量子能高效解、而经典随机算法不能高效解的问题？

🧠 类比： $\mathrm{BPP}$ 是"现有 CPU + 随机数能高效跑完的任务集合"，$\mathrm{BQP}$ 是"换上量子协处理器后能高效跑完的集合"。我们强烈怀疑后者更大（分解就被认为在 $\mathrm{BQP}$ 里但不在 $\mathrm{BPP}$ 里），但至今没人证明。

🔑 记住： 衡量量子优势看端到端成本；核心悬案是 BQP 是否严格大于 BPP。

5.2 Deutsch 与 Deutsch-Jozsa：量子并行的范例

大白话：量子并行就是——一个幺正变换能在输入的叠加态上同时算出函数在所有输入处的值。Deutsch 算法是这套思想最小的玩具例子：判断一个一位函数 $f:\{0,1\}\to\{0,1\}$ 是"常数型"（$f(0)=f(1)$）还是"平衡型"（$f(0)\ne f(1)$）。经典做法要把 $f(0)$、$f(1)$ 都查一遍（两次调用）；量子只查一次 $U_f$ 就够。

🧠 类比： 经典上你想知道 f(0) ^ f(1)，得分别 f(0)、f(1) 两次函数调用。量子等于把这俩输入打包成一个叠加，一次 f(superposition) 调用，再用干涉直接把 XOR 结果抖出来。

机制是"相位回踢 (phase kickback)"：把辅助比特预置成 $\ket{-}$，作用 $U_f$ 后，函数值不是写到辅助比特里，而是变成查询比特上的一个 $\pm$ 符号：

$$\ket{x}\ket{-} \xrightarrow{\,U_f\,} (-1)^{f(x)}\ket{x}\ket{-}$$

• $\ket{x}$：查询比特（你关心的输入）。
• $\ket{-}=(\ket{0}-\ket{1})/\sqrt{2}$：辅助比特，专门用来"接住"被踢回来的相位。
• $(-1)^{f(x)}$：函数值变成了挂在 $\ket{x}$ 前面的符号——这就是"回踢"。

接着对查询比特做一次 $H$ 让两个分支干涉，测量就直接读出全局量 $f(0)\oplus f(1)$：0 表示常数型，1 表示平衡型。

Deutsch-Jozsa 是 $n$ 位推广：承诺 $f$ 要么常数、要么平衡（恰好一半输入给 0、一半给 1），判断是哪种。经典最坏要查 $2^{n-1}+1$ 次（查过半数才能确定），量子依旧一次 $U_f$ 确定性搞定。

⚠️ 坑： 量子并行不等于"一次读出所有 $f(x)$"。所有值都算出来了，但都压在概率幅里，测量只塌缩出一个。它能加速的前提是你要的是全局性质（如 XOR、是否平衡），而不是某个具体的 $f(x)$。

🔑 记住： 经典获取的信息量超过答案所需信息量（存在计算冗余）时，量子才有加速空间。Deutsch-Jozsa 就是把"全局性质"用一次查询 + 干涉读出来的典范。

5.3 量子傅里叶变换 (QFT)

大白话：QFT 就是离散傅里叶变换 (DFT) 的量子版。经典 DFT 把一串数 $u_k$ 变成另一串数 $y_j$；QFT 干的是同一件数学，只不过把这串数当作量子态的概率幅来处理。它定义在基态上：

$$\ket{j} \;\longrightarrow\; \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i\, jk/N}\,\ket{k},\qquad N=2^n$$

• $\ket{j}$：输入基态（把整数 $j$ 编码成 $n$ 个比特）。
• $N=2^n$：维度，$n$ 个比特能表示 $0$ 到 $N-1$。
• $e^{2\pi i\, jk/N}$：第 $k$ 个输出分量的复相位（旋转因子），和经典 DFT 里那个 $\omega^{jk}$ 完全一致。
• $\tfrac{1}{\sqrt{N}}$：归一化，保证它是幺正（可逆、保模长）变换。

📐 怎么看： 把 QFT 写成 $N\times N$ 矩阵 $F$，第 $j$ 行第 $k$ 列就是 $F_{jk}=\tfrac{1}{\sqrt N}\omega^{jk}$，其中 $\omega=e^{2\pi i/N}$ 是「$N$ 次单位根」，行列下标都从 0 数起。它和经典 DFT 矩阵长得一模一样：每一列对应一个频率 $k$ 的复指数采样，$\tfrac{1}{\sqrt N}$ 负责归一。它没有特殊的对角结构，关键在于每个矩阵元都是单位圆上的一点，相位随乘积 $jk$ 线性增长。

🔢 算例： $N=2$ 时 $\omega=e^{i\pi}=-1$，$F=\tfrac{1}{\sqrt2}\begin{pmatrix}\omega^{0}&\omega^{0}\\\omega^{0}&\omega^{1}\end{pmatrix}=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H$——单比特 QFT 就是 Hadamard。$N=4$ 时 $\omega=e^{i\pi/2}=i$， $$F=\tfrac12\begin{pmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{pmatrix}$$ 作用到 $\ket1=(0,1,0,0)^{T}$ 就是取出第 1 列（从 0 数）：$\tfrac12(1,\,i,\,-1,\,-i)^{T}=\tfrac12(\ket0+i\ket1-\ket2-i\ket3)$。四个分量模长都是 $1/2$，区别全在相位——这正是「频率 1」的离散波。

🧠 类比： QFT ≈ np.fft.fft 的量子版。区别有三点：(1) 结果不是返回的数组，而是藏在量子态的概率幅里；(2) 它只要 $O(n^2)$ 个门，比经典 FFT 的 $O(N\log N)$ 还指数级地省；(3) 你不能直接 print 出全部系数——只能测量塌缩出一个。

为什么这么省？关键在因式分解：QFT 的输出态可以拆成每个比特上一个单比特态的张量积，根本不用展开那个 $N\times N$ 大矩阵：

$$\ket{j} \;\longrightarrow\; \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}}$$

• $\bigotimes_{l=1}^n$：对 $n$ 个比特做张量积（把它们拼成一个整体态）。
• $0.j_l j_{l+1}\dots j_n$：二进制小数，定义为 $0.a_1a_2\dots a_m := \sum_l a_l 2^{-l}$。比如 $0.101 = 1/2 + 0/4 + 1/8$。
• 每个因子 $(\ket{0}+e^{i\theta}\ket{1})/\sqrt{2}$：就是一个比特上的"相对相位态"，相位 $\theta$ 由原输入的低位比特决定。

💡 人话： 那个吓人的 $N$ 维傅里叶矩阵，其实可以"按比特拆开"，每个比特只跟它自己和后面几位的相位有关。于是构造线路就是：对每比特先 $H$，再补一串受控相位门 $R_k$（相位 $2\pi/2^k$），最后用 SWAP 把比特高低位次序翻回来。

门数清点：$H$ 加受控相位门一共约 $n(n+1)/2$ 个，即

$$\#\text{gates} = O(n^2) = O(\log^2 N)$$

⚠️ 坑： 别想着直接把 QFT 的输出"读出来"当 FFT 用。傅里叶系数全在概率幅里，测一次只塌缩出一个 $\ket{k}$，统计很多次也只能推断幅的模长、丢相位。QFT 单独没用，必须配合相位估计/Shor 这种"把答案逼到可读基"的技巧。

🔑 记住： QFT = DFT 的量子版；靠因式分解用 $H$+受控相位门做到 $O(n^2)$ 门；结果藏在概率幅里不能直接读。

5.4 相位估计

大白话：相位估计是 QFT 最重要的应用，可以理解成一个通用函数：给你一个幺正算符 $U$ 和它的一个本征态 $\ket{u}$，它把对应本征值的相位 $\varphi$ 用二进制"读数"到一个计数寄存器里。

$$U\ket{u}=e^{2\pi i\varphi}\ket{u}$$

• $U$：某个幺正算符（你想了解的"黑盒变换"）。
• $\ket{u}$：$U$ 的本征态，过一遍 $U$ 只会被乘上一个相位、方向不变。
• $e^{2\pi i\varphi}$：本征值，模长恒为 1（幺正性保证），全部信息在相位 $\varphi\in[0,1)$ 里。
• $\varphi$：我们想估计出来的那个数（二进制小数 $0.\varphi_1\varphi_2\dots$）。

🧠 类比： 把 $U$ 当成一个"返回值永远在单位圆上"的函数，$\ket{u}$ 是它的不动方向，唯一的变化就是转了个角度 $\varphi$。相位估计就是个"测角度"的子程序，把这个角度二进制采样到 $t$ 个比特里——本质上是 read_phase(U, u, precision=t)。

算法三步走（计数寄存器 $t$ 比特决定精度，另有寄存器装 $\ket{u}$）：

1. 计数比特全置 $\ket{+}$（即 $H^{\otimes t}\ket{0}$）。
2. 施一串受控-$U^{2^k}$：第 $k$ 个计数比特控制 $U^{2^k}$。靠相位回踢，把 $\varphi$ 编码进计数比特：

$$\frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1} e^{2\pi i\varphi j}\,\ket{j}\,\ket{u}$$

• $U^{2^k}$：把 $U$ 重复作用 $2^k$ 次，相位被放大 $2^k$ 倍，正好对应二进制第 $k$ 位。
• 求和里的 $e^{2\pi i\varphi j}$：注意这个态和 5.3 里 QFT 的输出长得一模一样——它就是 $\varphi$ 的"傅里叶编码"。

1. 对计数比特做逆 QFT ($\mathrm{QFT}^\dagger$)，把藏在相位里的 $\varphi$ 解码成一个二进制整数，测量读出。

💡 人话： 第 2 步用受控-$U$ 把相位"写成傅里叶形式"，第 3 步用逆 QFT 把傅里叶形式"反解"回普通整数。QFT 编码、逆 QFT 解码，正好一对逆操作。

精度分两种情况：

• $\varphi$ 恰好是 $t$ 位二进制小数：估计值就是精确值，确定性读出。
• $\varphi$ 不是：读出的是最接近的 $t$ 位近似，且以高概率命中；想更准、更稳，就加大 $t$。

🔢 算例： 设真实相位 $\varphi=0.101_2=\tfrac12+\tfrac{0}{4}+\tfrac18=0.625$，用 $t=3$ 个计数比特。第 2 步后计数寄存器变成 $\tfrac{1}{\sqrt8}\sum_{j=0}^{7}e^{2\pi i(0.625)j}\ket j$——这恰好就是基态 $\ket{101}=\ket5$ 的逆 QFT 像。于是第 3 步做逆 QFT 后，态精确塌缩成 $\ket{101}$，测量读出二进制 $101$，再当成小数 $0.101_2=0.625$ 还原 $\varphi$。因为 $\varphi$ 恰好是 3 位二进制小数，结果确定且精确；若 $\varphi$ 不是整 3 位（如 $0.6$），就会以高概率读到最接近的 $\ket{101}$ 或 $\ket{100}$。

⚠️ 坑： 相位估计要求你能制备本征态 $\ket{u}$。很多时候这本身很难——下一节 Shor 的精妙之处恰恰是绕过了这一点。另外书上线路与 Mathematica 笔记里的线路"作用顺序看似相反"，但因为各受控-$U^{2^k}$ 彼此对易、末端 SWAP 可被初态吸收，二者作为幺正算符完全等价。

🔑 记住： 相位估计 = 受控-$U^{2^k}$（相位回踢编码）+ 逆 QFT（解码读出）；前提是能造出 $U$ 的本征态；精度随计数比特数 $t$ 增长。

5.5 Shor 算法（大数分解）

大白话：Shor 的核心套路是规约——把"分解大数 $N$"这个难题，转换成"求阶 (order finding)"，再把求阶交给上一节的相位估计去做。所谓求阶：取一个与 $N$ 互质的 $y$，找最小的正整数 $r$（叫 $y$ 的"阶"）使得

$$y^r \equiv 1 \pmod{N}$$

• $y$：随机挑的、与 $N$ 互质的底数。
• $r$：阶，也就是 $y$ 在模 $N$ 乘法群里的周期。
• $\equiv \cdots \pmod N$：模 $N$ 同余，即两边除以 $N$ 余数相同。

🧠 类比： 求阶 = 求函数 $g(a)=y^a \bmod N$ 的周期。这个序列 $y^0, y^1, y^2,\dots$ 一定会循环，循环的长度就是 $r$。分解难题被翻译成"求一个周期"，而求周期正是傅里叶变换的拿手好戏。

拿到 $r$ 后，经典数论给出因子：若 $r$ 是偶数且 $y^{r/2}\not\equiv -1\pmod N$，则

$$\gcd\!\left(y^{r/2}-1,\ N\right)\ \text{和}\ \gcd\!\left(y^{r/2}+1,\ N\right)$$

至少有一个是 $N$ 的非平凡因子（$\gcd$ 用辗转相除，飞快）。

量子部分怎么求阶？ 定义模乘算符：

$$U\ket{x} \equiv \ket{yx \bmod N}$$

• 它把状态 $\ket{x}$ 映到 $\ket{yx \bmod N}$——就是"乘一次 $y$"。
• 连续作用 $r$ 次会回到原点（因为 $y^r\equiv 1$），所以 $U$ 的本征值都是 $e^{2\pi i s/r}$ 形式，相位里直接带着 $r$！

它的一族本征态记作 $\ket{u_s}$：

$$U\ket{u_s}=e^{2\pi i s/r}\ket{u_s},\qquad s=0,1,\dots,r-1$$

如果直接对某个 $\ket{u_s}$ 做相位估计，就能读出 $s/r$。但问题来了：你根本不知道 $r$，怎么制备 $\ket{u_s}$？

最妙的技巧在这里——这些本征态的均匀叠加恰好等于一个你随手就能造的态：

$$\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\ket{u_s} = \ket{1}$$

• 左边：所有 $r$ 个本征态等权叠加。
• 右边：就是计算基里的 $\ket{1}$（数字 1 的编码），制备成本几乎为零。

💡 人话： 你不用费劲去造某个特定本征态。直接拿 $\ket{1}$ 当输入，它本身就是全体本征态的"大杂烩"。做一次相位估计，线性叠加会让你等概率地塌缩到某一个 $s/r$ 上——相当于免费随机抽一个本征态来量。

🔢 算例（$N=15,\ y=7$ 求阶）： 逐次算模幂：$7^1=7$，$7^2=49\equiv 4$，$7^3\equiv 7\cdot4=28\equiv 13$，$7^4\equiv 7\cdot13=91\equiv 1\pmod{15}$。所以阶 $r=4$（最小使 $y^r\equiv 1$ 的正整数）。$r$ 是偶数，且 $7^{r/2}=7^2=49\equiv 4\not\equiv -1\pmod{15}$，满足导出因子的条件。于是 $\gcd(7^{2}-1,\,15)=\gcd(48,15)=3$、$\gcd(7^{2}+1,\,15)=\gcd(50,15)=5$，直接得到 $15=3\times 5$。量子部分的全部价值，就是对大 $N$ 也能高效地找出这个周期 $r=4$。

量子线路吐出一个测量值 $s/r$（分母带着我们要的 $r$，但 $s$ 是随机的、还约分了），接下来全是经典后处理：

• 连分数展开：把测得的近似分数 $s/r$ 展开成连分数，逼出最简分数，从而恢复 $r$。
• GCD：用上面的 $\gcd(y^{r/2}\pm 1, N)$ 拿到因子。

⚠️ 坑： Shor 不是一锤定音。可能抽到的 $r$ 是奇数，或者 $y^{r/2}\equiv -1$，这两种情况无法导出因子——换个 $y$ 重试即可（成功概率每次都不低）。还有：模乘 $U$ 不唯一，它只需在相关子空间上有定义，你能造出一个可用的就行，不必追求标准形式。

🔑 记住： 分解 → 求阶 → 对模乘 $U$ 做相位估计；输入 $\ket{1}$ 免去制备本征态；量子出 $s/r$，连分数 + GCD 经典还原因子。这套组合拳直接威胁 RSA（RSA 的安全性就押在"分解很难"上）。

5.6 隐藏子群问题 (HSP)

大白话：HSP 是把本章（乃至更多）量子算法统一起来的抽象框架——你可以把它当成一个基类/接口，Deutsch-Jozsa、Simon、求阶 (Shor)、离散对数都是它的具体实现 (subclass)。

问题定义：已知一个函数 $f:G\to X$ 隐藏了群 $G$ 的某个子群 $H$，意思是 $f$ 在 $H$ 的每个陪集上取同一个值、不同陪集取不同值。目标：找出 $H$（的生成元）。

🧠 类比： $f$ 像一个"按某种隐藏周期性分组"的哈希函数：落在同一个陪集（同一组）里的输入哈希值相同，不同组的不同。HSP 就是反推出"分组规则"——也就是隐藏的子群 $H$。求阶就是 $G=\mathbb{Z}$（整数加法群）、隐藏周期为 $r$ 的特例。

经典朴素做法要遍历，复杂度 $O(\lvert G\rvert)$（$\lvert G\rvert$ 是群的大小）。量子做法的统一套路是：

1. 在群寄存器上制备均匀叠加；
2. 查询 $f$，把陪集信息编码进态；
3. 对 $G$ 做（群上的）量子傅里叶变换；
4. 测量，得到关于 $H$ 的"对偶"信息；多采几次就能拼出 $H$ 的一组生成元。

💡 人话： 注意第 3 步——所有这些算法的"魔法核心"都是同一个：在合适的群上做傅里叶变换。换群、换 $f$，框架不变。这就是为什么 QFT 是本章的底层基石。

阿贝尔 vs 非阿贝尔：

• 阿贝尔群（交换群）：已有高效（多项式时间）量子算法，QFT 在其上结构清晰。
• 非阿贝尔群：一般情况仍是开放问题。比如二面体群的 HSP 关联到格问题，对称群的 HSP 关联到图同构——都是量子算法的前沿。

⚠️ 坑： 别以为"套进 HSP 就一定有量子加速"。只有阿贝尔 $G$ 才有现成的高效算法；非阿贝尔情形目前没有通用高效解法。

🔑 记住： HSP = "给定隐藏子群的 oracle $f$，求子群生成元"，是 QFT 类算法的统一接口；阿贝尔 HSP 已解决，非阿贝尔 HSP 仍开放。

🧠 全章类比收尾： QFT 是底层库 → 相位估计是基于它的通用函数 read_phase → Shor 是把"分解"规约成"求周期"后调用 read_phase 的杀手级应用 → HSP 是把这一切抽象出来的基类。理解了这条调用链，第五章就通了。