量子傅里叶变换

QFT 之所以值得单独成卷，而不是作为”加法器的一个零件”附在别处，原因是它的成本结构与其它卷完全不同。加法器的成本落在辅助比特与深度上，T 数只是副产品；QFT 的成本几乎全部落在 T 数上——具体地说，落在”把任意角度的受控旋转合成到 Clifford+T”这一步上。Nam–Su–Maslov 2020在摘要里把这件事讲得毫不含糊：标准的 $n$ 比特容错 QFT 是”去掉小角度受控旋转，再把剩余的合成到 Clifford+T”，由此得到 $O(n{\log }^{2}n)$ 的 T 数。这句话同时定义了本卷的两条主线：截断（丢掉小角度门）与合成（把剩下的门变便宜）。

因此本卷的第一原则是：读任何 QFT 论文的摘要，先看它报告的是 T 数、比特数，还是深度与并行度。这三者经常被混着写。合成与成本一词条给出一张三栏的判据表，把本卷所有可核实的构造按”真正降低了 T 数 / 只降低了比特与连接 / 只是重新排列”分好。

第二条主线是同一件事的三种实现形态。精确 QFT 用 $O(n^2)$ 个门，代价是不可容错的任意角旋转；近似 QFT 砍掉小角度门换取容错可行性；半经典 QFT 则干脆把双比特门换成”测量 + 受经典信号控制的单比特门”，用 1 根量子线换掉 $n$ 根。三者不是精度档位，而是架构档位——在测量昂贵的平台上选近似，在测量便宜且连线受限时选半经典。

第三条主线是QFT 不只用于读相位。QFT 加法器把进位从”线”变成”相位”，是比特数最低的加法器；QFT 型快速算术与乐观 QFT 结合，甚至能得到近线性深度的因数分解线路。这些是QFT 算术的内容。

阅读顺序建议

• 第一次接触：QFT 总览 → QFT 的门结构 → 合成与成本。前三篇读懂”这个变换为什么难实现”。
• 要做实现：近似与截断 QFT → 半经典 QFT，这两篇是同一个变换在两种架构上的取舍。
• 要做算术：QFT 算术，并与Takahashi–Kunihiro QFT 加法器对照读。
• 要读懂线路图：先看统一量子线路表示与比特序与寄存器约定。
• 要做 Shor 资源估算：本卷只回答第③段，第①②④段见Shor 线路路线图。

论文依据

• Nam–Su–Maslov（2018/2020） —— 提供本卷的核心基线数字：标准容错 QFT 的 $O(n{\log }^{2}n)$ T 数来自”去掉小角度受控旋转并把其余合成到 Clifford+T”，本文降到 $O(n\log n)$。本卷全部成本讨论以此为尺。
• Cleve–Watrous（2000） —— QFT 的快速并行线路，证明”QFT 不必串行执行”；本卷”重排一类”的奠基条目。
• Coppersmith（2002） —— “丢掉小角度受控相位以得到适用于因式分解的近似 QFT”这一做法的单作者独立来源。
• Griffiths–Niu（1995/1996） —— 半经典 QFT 的奠基来源：把双比特门换成受经典信号控制的一比特门。
• Takahashi–Kunihiro（2005） —— 无辅助比特、线性规模的 QFT 加法器；本卷算术侧的代表构造。
• Shor（1994/1997/1999） —— QFT 在因数分解里的原始用途，即在周期查找中读出周期。
• Rodriguez（2013），伽罗瓦域上的 QFT —— 备查：说明”QFT”是可以脱离 ${\mathbb{Z}}_{2^n}$ 讨论的概念族。本卷未展开专节；出处页只核实了书目信息（SPIE，无摘要）。