近似与截断 QFT

QFT 里最贵的门是角度最小的那些，而角度最小的门恰好是对结果影响最弱的门。丢掉它们是容错性的前提，不是可以随意做的工程近似。本词条先给出这个”丢掉”的误差账怎么算，再给出完整与截断两条线路的逐门对照，最后说明截断阈值 $\epsilon$ 为什么是本主题全部 T 数讨论的真正杠杆，以及为什么最新的进展反而走了”不砍门”的路子。

一、误差从哪来，以及怎么算

把第 $k$ 个受控相位 $R_{{\theta }_k}$ 换成恒等，得到 $\tilde{U}=U{\prod }_k{R}_{{\theta }_k}^{-1}$。算子范数上的偏差由三角不等式直接给出：

$$U-\tilde{U}\subseteq \sum _k(1-e^{i{\theta }_k}),\Vert U-\tilde{U}\Vert \le \sum _k|1-e^{i{\theta }_k}|\le \sum _k|{\theta }_k|$$

最后一不等式是关键：误差由被丢掉的角度的绝对值之和控制，而 QFT 的角度沿阶梯按 $2^{-k}$ 衰减，所以后面的门可以整段整段地扔掉而不引起误差爆发。删掉 $k$ 个最小的门时，丢掉的角度之和仍然是一个几何级数的小量——这就是”截断阈值 $\epsilon$“能起作用的原因：把 ${\sum }_k|{\theta }_k|\le \epsilon$ 作为停止条件，保留的门数由此确定，而保留下来的每一个门都还要合成到 Clifford+T。

这个做法不是新发明。Coppersmith（2002）是”丢掉小角度受控相位以得到适用于因式分解的近似 QFT”这一做法的单作者独立来源，也是本词的奠基条目。

二、完整与截断的线路对照

下图把一条 4 比特 QFT 画成两段：上半是精确展开（6 个受控相位），中间是被删掉的那一整块，下半是截断后的结果。示例阈值取 $\epsilon =\pi /4$，即所有角度不超过 $\pi /4$ 的受控相位全部删除。

完整 QFT 与截断 QFT：被丢掉的是整块小角度受控相位

图里要读出三件事。第一，H 门与交换门完全保留——截断只删相位门，不动结构。第二，被删掉的门集中在”控制线比特位高、目标线比特位低”的角落，也就是角度最小的那些。第三，剩下的门在容错模型里仍然要合成，这一步才是 $O(n{\log }^{2}n)$ 的来源（QQFT005）。

三、截断为什么站得住：三条独立的支撑线

“小角度旋转贡献低于阈值即可丢弃”不是一句口号，本主题有三条各自独立的支撑：

• Woolfe、Hill 与 Hollenberg（2017）给出近似 QFT 的标度行为与高效经典模拟。后者还有一个反直觉的推论：QFT 的输出在若干场景里可以被经典采样，因此”QFT 本身”在这些场景里并不是指数加速的来源。
• Nam 与 Blume（2015）研究旋转门实现有缺陷时 QFT 的性能标度，说明 QFT 对相位误差的容忍度。注意这是”门造得不准”，与”干脆不造某些门”是不同的误差来源。
• Agrawal 等（2023/2025）在 qudit 情形下解析证明为达到任意保真度所需的受控旋转数量存在上界（分带），并进一步证明在噪声下使用分带时，常深度的近似线路优于受控旋转更多的近似线路。这个反直觉的互补关系直接连到算术侧的同一族问题。

四、截断不是唯一的近似：乐观 QFT

Kahanamoku-Meyer 等（2025）提供了一条方向相反的思路：不砍门，而是放宽误差的定义。它提出的”乐观线路”只要求在绝大部分输入上近似正确，具体给的是：深度 $O(\log (n/\epsilon ))$、总比特 $n$（无辅助）、对排成 1D 的输入线是局部的、并且不含测量；误差在全输入上不超过 $\epsilon$，除了希尔伯特空间中一个 $O(\epsilon )$ 比例的例外部分。它同时给出一条归约，把乐观线路还原成对所有输入都近似的线路，这条归约使用长程门但不用测量。

两条路线的取舍很清楚：

	逐门截断	乐观 QFT
误差定义	所有输入	除 $O(\epsilon )$ 比例外的所有输入
需要归约还原吗	不需要	需要，且归约要用长程门
测量	纯酉版本不需要；$O(n\log n)$ T 数版本需要测量与前馈	乐观版本不含测量

把 QFT 变便宜的两条正交路径

五、阈值与应用的账

$\epsilon$ 是唯一的总杠杆，因为保留下来的每个受控相位都要付一次 Clifford+T 合成的代价。围绕它，本主题有两类工作：

• 改合成方法：Park–Ahn（2022）把近似 QFT 的 T 数从约 $8n{\log }_2(n/\epsilon )$ 降到约 $4n{\log }_2(n/\epsilon )$、T 深度减半，关键动作是彻底去掉 Toffoli 门（此前一半 T 数来自 Toffoli）。
• 改算法接口：Oonishi 与 Kunihiro（2023）用高效近似 QFT 改造 Shor 算法本身，说明”换一个更好的近似 QFT”能在算法层产生可观的传导。
• 改实现载体：Bäumer–Sutter–Woerner（2025）用动态线路让近似 QFT 在一条线上维持对数深度，代价全在比特数与连接性上（$8n$ 全连接降到 $4n$ 线上），不主张降低 T 数。

论文依据

• Coppersmith（2002） —— 本词条方法的奠基来源：单作者给出丢掉小角度受控相位的近似 QFT，并面向量子因式分解说明其可用性。
• Nam–Su–Maslov（2018/2020） —— 给出截断之后剩余门的合成代价口径：标准容错实现 $O(n{\log }^{2}n)$ T 数来自截断加合成两步；本文降到 $O(n\log n)$，代价是测量与前馈。
• Woolfe、Hill 与 Hollenberg（2017） —— 近似 QFT 的标度行为与高效经典模拟，是”低于阈值即可丢弃”这条说法的数值支撑。
• Nam 与 Blume（2015） —— 旋转门有缺陷时 QFT 的性能标度，说明 QFT 对相位误差的容忍度（误差来源是门实现不精确，而非缺门）。
• Agrawal 等（2023/2025） —— qudit 情形下分带的解析上界，以及噪声下常深度近似线路优于受控旋转更多的近似线路这一互补结论。
• Kahanamoku-Meyer 等（2025） —— 乐观 QFT：$O(\log (n/\epsilon ))$ 深度、$n$ 总比特、无测量、1D 局域，误差在全输入上界 $\epsilon$ 之外另有 $O(\epsilon )$ 比例的例外；并给出使用长程门但不含测量的归约。
• Park–Ahn（2022） —— 近似 QFT 的 T 数与 T 深度优化，含完整常数对照与”去掉 Toffoli”这一关键动作。
• Oonishi 与 Kunihiro（2023） —— 用高效近似 QFT 改造 Shor 算法。
• Bäumer–Sutter–Woerner（2025） —— 动态线路版近似 QFT 的对数深度实现；收益在比特数与连接性。
• Pavlidis 与 Floratos（2021） —— 基于 QFT 的 qudit 量子算术，把变换域算术推广到任意维。

延伸阅读

• qft-synthesis —— 截断之后的合成账，以及”重排 ≠ 变便宜”的判据表
• qft-gates —— 被截断的正是那些层结构里的相位门
• semiclassical-qft —— 第三条路：改变实现形态而不是门集合
• qft-based-arithmetic —— 分带在算术侧的同一族问题