大学生版第五章 · QFT 与 Shor
🎯 用来干嘛⚛️ 物理上是啥📖 补基础🧮 一步步算💭 直觉⚠️ 常见错误✅ 小结

第五章 量子傅里叶变换与 Shor 算法 · 大学生版

导读

这一章是量子算法里「最赚钱」的一支：先讲清楚量子并行快在哪，再造出量子版的傅里叶变换（QFT），然后用它搭出相位估计这把「万能扳手」，最后用相位估计把 RSA 赖以生存的大数分解给端了（Shor 算法）。

整章的调用链是：QFT 是底层工具 → 相位估计是用它写的通用子程序 → Shor 是相位估计的杀手级应用 → HSP 是把这一切统一起来的抽象框架。 全程记住一句话：量子能「同时算所有输入」，但你每次只能测出一个结果，所以真正的艺术是「怎么把想要的答案逼到你能读出的那个基态上」。

本章数学密度比第四章高一点，但每个新工具（复指数与欧拉公式、单位根、DFT 矩阵、二进制小数、模运算与 gcd、本征值相位）都会在第一次用到时用 📖 补基础 补清楚，并配小数字例子。

📖 补基础（复指数与欧拉公式）： 本章满屏的 $e^{i\theta}$ 都来自欧拉公式 $$e^{i\theta}=\cos\theta+i\sin\theta.$$ 它是复平面单位圆上、与正实轴夹角为 $\theta$ 的点，模长恒为 1（$\lvert e^{i\theta}\rvert=1$）。几个要记的值：$e^{i\cdot0}=1$、$e^{i\pi/2}=i$、$e^{i\pi}=-1$、$e^{i\cdot2\pi}=1$（转一整圈回到原点）。乘 $e^{i\theta}$ 的几何意义就是「逆时针转 $\theta$ 角」，不改变长度——这就是「相位」的本质。

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

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

本章重点是两大算法家族：QFT 家族（相位估计、Shor，靠傅里叶变换提取「周期/全局」信息）和量子搜索家族（第六章 Grover，靠振幅放大在无结构数据里捞针）。

理论上最核心的未决问题是 $\mathrm{BQP}\overset{?}{\supsetneq}\mathrm{BPP}$：是否存在「量子能高效解、经典随机算法不能高效解」的问题？大家强烈怀疑分解就属于这一类，但至今没人证明。

✅ 小结： 衡量量子优势要看端到端成本（装载 + 计算 + 读出 + 后处理）；核心悬案是 BQP 是否严格大于 BPP。

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

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

🎯 用来干嘛： 这是「量子为什么可能更快」的最干净证据。它告诉你量子加速的正确打开方式：不是想一次读出所有 $f(x)$（做不到），而是当你只关心一个全局性质（如 $f(0)\oplus f(1)$、函数是否平衡）时，用一次查询 + 干涉就能抖出答案。后面 Shor 找周期走的就是同一条路。

机制叫「相位回踢」：把辅助比特预置成 $\ket-=(\ket0-\ket1)/\sqrt2$，作用 $U_f$ 后，函数值不写进辅助比特，而是变成查询比特前面的一个 $\pm$ 符号：

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

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

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

⚠️ 常见错误： 量子并行不等于「一次读出所有 $f(x)$」。所有值确实都算出来了，但都压在概率幅里，测量只塌缩出一个。它能加速的前提是你要的是全局性质（如 XOR、是否平衡），而不是某个具体的 $f(x)$。
✅ 小结： 当经典获取的信息量超过答案所需（有计算冗余）时量子才有加速空间；Deutsch-Jozsa 用一次查询 + 干涉读出全局性质，是量子并行的范典。

5.3 量子傅里叶变换 (QFT)

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

🎯 用来干嘛： 用来把「藏在数据里的周期 / 频率」转换成「相位结构」，好让后续操作能高概率把它测出来。它是相位估计和 Shor 算法的引擎——Shor 破解 RSA 的关键一步就是用 QFT 找出周期。注意：QFT 本身只是个内部零件，傅里叶系数全在概率幅里、不能直接读出来当 FFT 用，必须配相位估计这类技巧才有意义。
⚛️ 物理上是啥： QFT 本质上是一次换基——把量子态从「位置 / 计算基」表象换到「频率 / 动量」表象，就像物理里在时域和频域之间切换。所以原本藏在数据里的周期性，过完 QFT 就变成了频率轴上一个明显的结构。
🔬 想多了解一点：傅里叶变换到底在干嘛？"时域 / 频域""换基"又是什么？

这段话里 傅里叶变换、时域 / 频域、换基 都是大学才讲的词，但它的核心思想其实非常生活化。

1）傅里叶变换 = 把一段复杂的波"拆成一堆纯音"。 想象你同时按下钢琴的好几个键，耳朵听到的是一团混在一起的声音（这叫时域——按时间记录"此刻空气振动有多强"）。傅里叶变换干的事，就是把这团声音拆开，告诉你"里面其实是 Do、Mi、Sol 这几个音、各占多大比重"（这叫频域——按频率记录"每个音有多强"）。同一段声音，两种记法：一种盯着"每一时刻"，一种盯着"含哪些频率"。

2）另一个画面：棱镜分光。 一束白光看着没什么结构，可让它穿过三棱镜，就"散"成红橙黄绿蓝靛紫一条彩带——每种颜色就是一个频率。傅里叶变换就是数学上的棱镜：把混在一起的信号，摊开成"各个频率各有多少"。

3）"换基"和"找周期"。 把信号从时域写法换成频域写法，数学上叫换基（换一套坐标来描述同一个东西，就像同一个地点既能用"经纬度"也能用"街道门牌"来说）。换基的妙处是：原本看不出来的周期性，一到频域就变成一根扎眼的尖峰。比如一段每隔 3 秒重复一次的信号，时域上看是一团乱，频域里却会在"频率 = 1/3"那个位置冒出一个明显的高峰。Shor 算法要找的"周期"，正是靠这一招从一堆数据里逼出来的。

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

📖 补基础（单位根 $\omega$）： 记 $\omega=e^{2\pi i/N}$，叫「$N$ 次单位根」。它是单位圆上把整圈 $2\pi$ 均分成 $N$ 份的第一个点；它的幂 $\omega^0,\omega^1,\dots,\omega^{N-1}$ 是圆上均匀分布的 $N$ 个点，且 $\omega^N=1$（转满一圈回到 1）。例如 $N=4$ 时 $\omega=e^{2\pi i/4}=e^{i\pi/2}=i$，四个幂是 $1,i,-1,-i$。
📖 补基础（DFT 矩阵长什么样）： 把 QFT 写成 $N\times N$ 矩阵 $F$，第 $j$ 行第 $k$ 列就是 $F_{jk}=\frac{1}{\sqrt N}\omega^{jk}$（行列下标都从 0 数起）。它和经典 DFT 矩阵一模一样：每一列对应一个频率，是一串复指数的采样，$\frac{1}{\sqrt N}$ 负责归一化让它幺正。关键点：每个矩阵元都是单位圆上的一点，相位随乘积 $jk$ 线性增长。
🧮 一步步算（$N=2$ 时 QFT $=H$）： $N=2$ 时 $\omega=e^{2\pi i/2}=e^{i\pi}=-1$。矩阵元 $F_{jk}=\frac{1}{\sqrt2}\omega^{jk}$： $$F=\frac{1}{\sqrt2}\begin{pmatrix}\omega^{0}&\omega^{0}\\\omega^{0}&\omega^{1}\end{pmatrix}=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}=H.$$ 单比特 QFT 就是 Hadamard 门！
🧮 一步步算（$N=4$ 的 QFT 矩阵）： $N=4$ 时 $\omega=i$，$F_{jk}=\frac12 i^{\,jk}$（指数 $jk$ 可对 4 取余，因为 $i^4=1$）。例如 $j=k=1$ 处是 $\frac12 i^1=\frac{i}{2}$；$j=k=2$ 处 $i^4=1$，是 $\frac12$；$j=2,k=3$ 处 $i^6=i^2=-1$。逐格填好得： $$F=\frac12\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 数起）：$\frac12(1,\,i,\,-1,\,-i)^{T}=\frac12(\ket0+i\ket1-\ket2-i\ket3)$。四个分量模长都是 $1/2$，区别全在相位——这正是「频率 1」的离散波。

为什么 QFT 只要 $O(n^2)$ 个门、比经典 FFT 的 $O(N\log 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}}.$$

📖 补基础（二进制小数）： 二进制小数定义为 $0.a_1a_2\dots a_m:=\sum_l a_l\,2^{-l}$，即第 1 位权重 $\frac12$、第 2 位 $\frac14$、第 3 位 $\frac18$……例如 $$0.101_2=1\cdot\tfrac12+0\cdot\tfrac14+1\cdot\tfrac18=0.5+0+0.125=0.625.$$ 上式中每个比特上的相位 $e^{2\pi i\cdot 0.j_lj_{l+1}\dots}$ 就由原输入的这些低位比特决定。

构造线路的办法：对每个比特先做一个 $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 的量子版，矩阵元 $\frac{1}{\sqrt N}\omega^{jk}$（$\omega=e^{2\pi i/N}$）；$N=2$ 时就是 $H$；靠张量积分解用 $H$ + 受控相位门做到 $O(n^2)$ 门；结果藏在概率幅里不能直接读。

5.4 相位估计

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

🎯 用来干嘛： 它是一台通用读数器——给个幺正算符 $U$，把它本征值的相位用二进制读到寄存器里。很多量子算法（Shor 求阶、量子化学里估计分子能量、各种 HSP 类算法）最后都归结为「调用一次相位估计」。把它当成 read_phase(U, u, 精度=t) 这个被反复复用的标准函数就对了。

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

📖 补基础（本征值的相位）： 幺正算符的本征值模长都是 1，所以一定能写成 $e^{2\pi i\varphi}$ 的形式，全部信息就在相位 $\varphi\in[0,1)$ 里。把 $U$ 想成一个「返回值永远落在单位圆上」的操作，$\ket u$ 是它的不动方向，唯一发生的事就是转了个角度 $2\pi\varphi$。相位估计就是个「测这个角度」的子程序，把 $\varphi$ 二进制采样到 $t$ 个比特上。
⚛️ 物理上是啥： 相位估计在物理上，就是把一个幺正算符（或哈密顿量）本征态的本征相位——这相位往往对应着能量或频率——读进寄存器里，很像干涉仪靠干涉条纹去测一个相位。注意它读的只是本征相位这一个量，并不能直接读出本征态里藏的任意信息。
🔬 想多了解一点：什么是"干涉仪"？为什么"相位"能代表"能量或频率"？

1）相位先回顾一句。 把一支量子振幅想成一根不停旋转的小时针，它此刻指向哪个方向就是"相位"。单独看一根时针看不出方向有什么用，可一旦两支波合到一起，方向一致就相加变亮（相长）、方向相反就抵消变暗（相消）——这就是"干涉"。

2）干涉仪 = 用明暗来反推相位的尺子。 干涉仪是一种真实仪器：它把一支波分成两路，让其中一路多走一点、积累一点相位差，再把两路合回来，看合起来是变亮还是变暗。因为"亮多少 / 暗多少"完全由两路的相位差决定，于是反过来——只要量一下最后的明暗，就能精确算出那段相位差是多少。相位估计干的就是这件事的量子版：靠干涉把藏起来的相位 $\varphi$ 一位一位读出来。

3）为什么相位能代表能量 / 频率？ 关键在一条规律：一个能量越高的量子态，它那根"相位时针"转得越快。所以"这根时针转得多快"（频率）和"它带多少能量"是绑定的。让态演化一段固定时间，能量高的多转、能量低的少转，最后停在的相位角度就把它的能量"记"了下来。于是测这个相位 $\varphi$，等于在间接测这个态的能量或频率——这正是量子化学里用相位估计去算分子能量的道理。

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

  1. 计数比特全置 $\ket+$（即 $H^{\otimes t}\ket0$）。
  2. 施一串受控-$U^{2^k}$：第 $k$ 个计数比特控制 $U^{2^k}$（把 $U$ 重复作用 $2^k$ 次，相位被放大 $2^k$ 倍，正好对应二进制第 $k$ 位）。靠相位回踢，把 $\varphi$ 编码进计数比特，得到

$$\frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1} e^{2\pi i\varphi j}\,\ket{j}\,\ket{u}.$$ 注意这个态和 5.3 里 QFT 的输出长得一模一样——它就是 $\varphi$ 的「傅里叶编码」。

  1. 对计数比特做逆 QFT（$\mathrm{QFT}^\dagger$），把藏在相位里的 $\varphi$ 解码成一个二进制整数，测量读出。
💭 直觉： 第 2 步用受控-$U$ 把相位「写成傅里叶形式」，第 3 步用逆 QFT 把它「反解」回普通整数。QFT 编码、逆 QFT 解码，正好是一对互逆操作。
🧮 一步步算（$\varphi=0.101_2$ 的确定性读出）： 设真实相位 $\varphi=0.101_2=\frac12+\frac{0}{4}+\frac18=0.625$，用 $t=3$ 个计数比特。第 2 步后计数寄存器变成 $$\frac{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}$，想更准就加大 $t$。
⚠️ 常见错误： 相位估计要求你能制备本征态 $\ket u$——很多时候这本身很难。下一节 Shor 的精妙之处恰恰是绕过了这一点。
✅ 小结： 相位估计 = 受控-$U^{2^k}$（相位回踢编码）+ 逆 QFT（解码读出）；前提是能造出 $U$ 的本征态；精度随计数比特数 $t$ 增长，$\varphi$ 恰好是 $t$ 位二进制小数时确定读出。

5.5 Shor 算法（大数分解）

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

🎯 用来干嘛： 这是量子计算最有名的「杀手级应用」——高效分解大整数。RSA 加密的安全性全押在「分解大数很难」上，而 Shor 把分解规约成求周期、再用相位估计高效求出周期，等于直接威胁了今天大半互联网的公钥加密。这也是各国砸钱造量子计算机、推「后量子密码」的直接动因。

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

📖 补基础（模运算、gcd 与辗转相除）： $a\equiv b\pmod N$ 读作「$a$ 和 $b$ 模 $N$ 同余」，意思是 $a-b$ 能被 $N$ 整除，即两者除以 $N$ 余数相同。例如 $49\equiv4\pmod{15}$（因为 $49=3\times15+4$）。$\gcd(a,b)$ 是最大公约数，用辗转相除法飞快算出：反复用「大数除以小数取余」替换，直到余数为 0。例如 $\gcd(48,15)$：$48=3\times15+3$，再 $\gcd(15,3)$：$15=5\times3+0$，余 0，于是 $\gcd(48,15)=3$。

拿到 $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$ 的非平凡因子。

量子部分怎么求阶？ 定义模乘算符 $U\ket{x}\equiv\ket{yx \bmod N}$（把 $\ket x$ 映到「乘一次 $y$」）。连续作用 $r$ 次会回到原点（因为 $y^r\equiv1$），所以 $U$ 的本征值都是 $e^{2\pi i s/r}$ 形式——相位里直接带着我们要的 $r$！它的一族本征态 $\ket{u_s}$ 满足 $U\ket{u_s}=e^{2\pi i s/r}\ket{u_s}$（$s=0,1,\dots,r-1$）。

问题是：你根本不知道 $r$，怎么制备 $\ket{u_s}$？最妙的技巧是这些本征态的均匀叠加恰好等于一个随手就能造的态：

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

💭 直觉： 你不用费劲去造某个特定本征态。直接拿计算基里的 $\ket1$（数字 1 的编码，几乎零成本）当输入，它本身就是全体本征态的「大杂烩」。做一次相位估计，叠加会让你等概率地塌缩到某个 $s/r$ 上——相当于免费随机抽一个本征态来量。
⚛️ 物理上是啥： 求阶的物理图像是一个周期性的叠加态：模乘 $U$ 每作用一次就往前转一格，转 $r$ 次回到原点。这种周期信号经傅里叶变换后，会在对应「频率」$s/r$ 处发生相长干涉、其它地方相消，于是测量就大概率落到带着周期 $r$ 的那些点上。
🔬 想多了解一点：为什么"周期性的叠加态"一做傅里叶变换，就会在频率 $s/r$ 处"亮"起来？

1）先想一个荡秋千的画面。 你推一个秋千，如果每次都在同一个节拍上推（跟秋千的固有周期合上拍），每一下都"加"在前一下上，秋千越荡越高——这叫相长。要是你乱推、节拍对不上，这一下推、那一下拽，互相抵消，秋千就荡不起来——这叫相消。傅里叶变换里发生的是一模一样的事，只不过"推"换成了"一支支量子振幅（小时针）相加"。

2）周期 $r$ 怎么变成频率轴上的尖峰。 模乘算符 $U$ 每作用一次就把态往前"转一格"，转满 $r$ 次正好回到原点——这就是一个周期为 $r$ 的信号。把所有这些振幅（小时针）按傅里叶的方式加起来时：在那些"节拍刚好对上周期"的频率位置（也就是 $s/r$ 这些点），所有小时针指向一致、相加变得很亮（相长）；在其它频率位置，小时针方向各异、彼此抵消、几乎归零（相消）。

3）所以测量"大概率"落在带着周期的点上。 经过这一轮相长 / 相消，态的"亮度"（也就是测量概率）几乎全堆在 $s/r$ 这几个位置。你一测量，就大概率读到这些点之一，于是分母里就带出了我们朝思暮想的周期 $r$。这就是 Shor 算法能把"藏在模乘里的周期"逼到你能读出来的基态上的根本原因——它不是把所有答案一次读光，而是让对的答案"亮"、错的答案"灭"。

🧮 一步步算（$N=15,\ y=7$ 求阶并分解）： 逐次算模幂（每步乘 7 再对 15 取余）： $$7^1=7,\quad 7^2=49\equiv4,\quad 7^3\equiv7\cdot4=28\equiv13,\quad 7^4\equiv7\cdot13=91\equiv1\pmod{15}.$$ 最小使 $y^r\equiv1$ 的是 $r=4$。$r$ 是偶数，且 $7^{r/2}=7^2=49\equiv4\not\equiv-1\pmod{15}$，满足导出因子的条件。于是 $$\gcd(7^2-1,\,15)=\gcd(48,15)=3,\qquad \gcd(7^2+1,\,15)=\gcd(50,15)=5,$$ 直接得到 $15=3\times5$。（$\gcd(50,15)$：$50=3\times15+5$，再 $\gcd(15,5)=5$。）量子部分的全部价值，就是对大 $N$ 也能高效地找出这个周期 $r$。

量子线路吐出一个测量值 $s/r$（分母带着我们要的 $r$，但 $s$ 是随机的、还可能约分了），接下来全是经典后处理：连分数展开把测得的近似分数逼成最简分数恢复 $r$，再用 $\gcd(y^{r/2}\pm1,N)$ 拿到因子。

⚠️ 常见错误： Shor 不是一锤定音。可能抽到的 $r$ 是奇数，或者 $y^{r/2}\equiv-1$，这两种情况无法导出因子——换个 $y$ 重试即可（每次成功概率都不低）。
✅ 小结： 分解 → 求阶 → 对模乘 $U$ 做相位估计；输入 $\ket1$ 免去制备本征态；量子出 $s/r$，连分数 + gcd 经典还原因子。例子 $N=15,y=7,r=4$，$\gcd(48,15)=3$、$\gcd(50,15)=5$。这套组合拳直接威胁 RSA。

5.6 隐藏子群问题 (HSP)

大白话：HSP 是把本章（乃至更多）量子算法统一起来的抽象框架——Deutsch-Jozsa、Simon、求阶（Shor）、离散对数都是它的具体特例。

🎯 用来干嘛： 它把一堆看似无关的量子算法装进同一个模板：只要你的问题能写成「找隐藏子群」，就照「制备叠加 → 查询 → 群上做傅里叶 → 测量」这套流程套。理解它的价值在于：想发明新量子算法时，先问「能不能化成 HSP」；同时它也圈出了量子加速的边界——阿贝尔群已解决，非阿贝尔群（关联格密码、图同构）仍是开放前沿。

问题定义：已知函数 $f:G\to X$ 隐藏了群 $G$ 的某个子群 $H$，意思是 $f$ 在 $H$ 的每个陪集上取同一个值、不同陪集取不同值。目标：找出 $H$ 的生成元。求阶就是 $G=\mathbb{Z}$（整数加法群）、隐藏周期为 $r$ 的特例。

量子统一套路：① 在群寄存器上制备均匀叠加；② 查询 $f$ 把陪集信息编码进态；③ 对 $G$ 做（群上的）量子傅里叶变换；④ 测量，得到关于 $H$ 的「对偶」信息，多采几次拼出 $H$ 的生成元。经典朴素做法要遍历，复杂度 $O(\lvert G\rvert)$。

💭 直觉： 注意第 ③ 步——所有这些算法的「魔法核心」都是同一个：在合适的群上做傅里叶变换。换群、换 $f$，框架不变。这就是为什么 QFT 是本章的底层基石。
⚠️ 常见错误： 别以为「套进 HSP 就一定有量子加速」。只有阿贝尔群（交换群）$G$ 才有现成的高效算法；非阿贝尔情形（如二面体群关联格问题、对称群关联图同构）目前仍是开放问题，没有通用高效解法。
✅ 小结： HSP = 「给定隐藏子群的 oracle $f$，求子群生成元」，是 QFT 类算法的统一接口；阿贝尔 HSP 已解决，非阿贝尔 HSP 仍开放。整章调用链：QFT（底层工具）→ 相位估计（通用子程序）→ Shor（杀手级应用）→ HSP（统一框架）。

💬 答疑（不同背景的人都在问）

❓【大一学生】QFT 比经典 FFT 快指数级，那我能不能拿它当超快 FFT 来算信号？为啥说"算出来读不出来"？

不能当普通 FFT 用，这是最常见的误会。FFT 的价值在于它把全部 $N$ 个频率系数明明白白交到你手里，你能一个个读出来、画频谱。QFT 算完后这 $N$ 个系数确实"都在"，但它们藏在量子态的概率幅里——你测一次只能塌缩出一个下标，还测不到相位。所以"算得快"和"用得上"是两码事：QFT 只是个内部零件，必须配合相位估计、Shor 这类技巧，把你真正想要的那一个答案"逼"成大概率能测到的基态，才有意义。单拎出来当 FFT 库函数调，纯属误解。

❓【程序员】QFT 只要 $O(n^2)$ 门、比 FFT 的 $O(N\log N)$ 指数级省，可系数又读不出来。这个加速能替代我代码里的 FFT 吗？当成一个比 FFT 快的库函数来调是不是彻底误解？

是彻头彻尾的误解。两者的"输出规格"根本不一样：经典 FFT 把 $N$ 个复系数全部写进内存，$O(N)$ 个数随便访问；QFT 把这些系数编码进 $N$ 维叠加态的振幅里，一次测量只塌缩出一个 $O(\log N)$ 比特的下标、且丢相位。换句话说 QFT 没有"返回 $N$ 个系数"这个 API。所以那个"指数加速"不能被外部调用方当 FFT 加速器利用——它只在你最终关心的是某个全局量（周期、本征相位）、能用干涉把它放大到可测时才兑现。把它 import 进来替你的 np.fft 是行不通的。

❓【数学】QFT 矩阵 $F_{jk}=\frac{1}{\sqrt N}\omega^{jk}$ 的酉性，是不是完全归结为"单位根几何级数求和：公比非 1 时和为 0"这一条代数事实？

是的，正是这一条。验证酉性即验证各列标准正交：第 $j$ 列与第 $j'$ 列的内积为 $\frac1N\sum_{k=0}^{N-1}\overline{\omega^{jk}}\,\omega^{j'k}=\frac1N\sum_k\omega^{(j'-j)k}$。记 $m=j'-j$，这是公比 $\omega^m$ 的几何级数：当 $m\equiv0\pmod N$ 时每项为 1、和为 $N$；否则 $\omega^m\neq1$ 而 $(\omega^m)^N=1$，由 $\sum_{k=0}^{N-1}q^k=\frac{q^N-1}{q-1}$ 得和为 0。于是内积 $=\delta_{jj'}$，列正交归一 $\iff$ 酉。所以 QFT 酉性的全部根据，确实就是"非平凡单位根的整圈求和为零"。

❓【大一学生】Shor 里说"输入 $\ket1$ 就免去制备本征态"，可你又不知道周期 $r$，凭什么 $\ket1$ 正好等于所有本征态的均匀叠加？

这一步确实像变魔术，但有道理。模乘算符 $U$ 有 $r$ 个本征态 $\ket{u_s}$，它们是一组"正交方向"，张成同一个空间。关键的代数恒等式是：把这 $r$ 个本征态等权重平均加起来，那些乱七八糟的相位会互相抵消，最后干干净净地等于 $\ket1$（这是能严格算出来的，不是凑的）。所以你根本不用知道 $r$、也不用费劲制备某个特定 $\ket{u_s}$——直接拿现成的 $\ket1$ 当输入，它本身就是这一大锅本征态的均匀混合，做一次相位估计就等概率随机抽中其中一个 $s/r$ 来读。

❓【数学】$\ket{1}=\frac{1}{\sqrt r}\sum_s\ket{u_s}$ 是不是就等价于"计算基与傅里叶基互为一个酉变换、且 $\ket1$ 在傅里叶基下的展开系数模长全相等"这一线性代数事实？

正是如此。把 $U$ 限制在它生成的循环不变子空间 $\mathrm{span}\{\ket{y^t\bmod N}\}\cong\mathbb{C}^r$ 上，$U$ 就是 $\mathbb{Z}_r$ 上的循环移位算子。移位算子在该 $r$ 维空间的本征基恰是群 $\mathbb{Z}_r$ 的特征标 $\ket{u_s}=\frac{1}{\sqrt r}\sum_t\omega_r^{-st}\ket{y^t}$（$\omega_r=e^{2\pi i/r}$），即离散傅里叶基。于是 $\frac{1}{\sqrt r}\sum_{s=0}^{r-1}\ket{u_s}=\sum_t\big(\frac1r\sum_s\omega_r^{-st}\big)\ket{y^t}=\ket{y^0}=\ket1$，最后一步又用到单位根求和 $\frac1r\sum_s\omega_r^{-st}=\delta_{t,0}$。所以这就是"计算基 $\leftrightarrow$ 傅里叶基互为酉、$\ket1$ 在傅里叶基下各系数模长均为 $1/\sqrt r$"的直接体现。

❓【程序员】Shor 对 RSA 的真实威胁，瓶颈到底在量子那段（受控模幂要多少门、多少 qubit）还是别处？破解 2048 位 RSA 现实里大概要多少 qubit，离现在差几个数量级？

瓶颈死死卡在量子那段，尤其是受控模幂 $U^{2^k}$（可逆地算 $a^x\bmod N$）——它占掉电路绝大部分门和深度，连分数 + gcd 那点经典后处理几乎免费。逻辑层面：约几千个逻辑 qubit（$\sim$ 几倍 $n$，$n=2048$），模幂门数 $\tilde O(n^2{\sim}n^3)$。真正的鸿沟在纠错开销：每个逻辑 qubit 要成千上万个物理 qubit。主流估计（Gidney–Ekerå, 2019）破 2048 位 RSA 约需 2000 万个物理 qubit、跑数小时。今天的设备在 $10^2$–$10^3$ 物理 qubit 量级，所以差大约 4 个数量级，且必须是高质量可纠错的——这正是"现在赶紧迁后量子密码、但 RSA 还没当场死"的原因。