合成与成本

QFT 是本主题里最容易被夸大的一处。同一个研究方向里既有”把 T 数砍掉一个对数因子”的真结果，也有”把同样的门换个顺序排好”的调度工作，两者在摘要里的措辞几乎一样。本词条把全主题可核实的构造按它到底改变了哪一项资源分成三栏，并说明为什么判据只能是门计数本身：深度下降不等于变便宜，省下比特也不等于省下 T。

一、基线数字：$O(n{\log }^{2}n)$ 是怎么来的

Nam–Su–Maslov（2018/2020）在摘要里把标准的 $n$ 比特容错 QFT 写成两个动作：去掉小角度的受控旋转，再把剩余的受控旋转合成到 Clifford+T，结果是 $O(n{\log }^{2}n)$ 的 T 数。这句话必须逐字读，因为它划出了本主题唯一的成本杠杆：

• 去掉的那部分门本来就没有成本，它们是免费的精度。
• 成本几乎全部产生在第二步——把角度为 $2\pi /2^k$ 的受控相位变成 Clifford+T 门。一个角度越小的旋转，精确合成它需要的级数越高，而 QFT 里恰恰是角度最小的门最多。

所以任何”我们把 QFT 做得更便宜”的断言，都必须回答两个问题：改的是截断阈值，还是合成方法？ 两者都能动 $O(n{\log }^{2}n)$ 这个数字，但机制完全不同。

二、真正降低了 T 数

按”来源明示了 T 数下降”筛选，本主题只有三条：

构造	降幅	代价	出处
Nam–Su–Maslov 近似 QFT	$O(n{\log }^{2}n)\to O(n\log n)$	引入测量与前馈，不再是纯酉线路；依赖复用一个能实现相位梯度变换的特殊量子态	QQFT005
Park–Ahn 近似 QFT	T 数约 $8n{\log }_2(n/\epsilon )\to 4n{\log }_2(n/\epsilon )$；T 深度约 $2n{\log }_2(n/\epsilon )\to n{\log }_2(n/\epsilon )$	关键动作是彻底去掉 Toffoli 门——此前一半 T 数来自 Toffoli；并把主导 T 深度的加法器并行排布	[[sources/QQFT003
Gidney 临时逻辑 AND	$n$ 比特加法器 $8n+O(1)\to 4n+O(1)$ 个 T；受控加法器同量级	适用于加法器，论文明示该技术可用于 QFT 与 Shor	[[sources/QQFT025

三条的共同点是门集合本身变了：要么换了合成路径（第一个），要么从线路里删掉了一整类门（第二个），要么换掉了产生 T 的那个子线路（第三个）。判据就在这里——如果把新线路合成回 Clifford+T 之后的门计数没有下降，那它就不是 T 数改进。

三、只降低了比特数与连接代价

这一类工作同样有价值，但改善的是另一种资源，引用时不能混进 T 数表：

• Bäumer–Sutter–Woerner（2025）用动态线路让近似 QFT 在一条线上保持对数深度，经典的全连接结果需要 $8n$ 比特（该结果引自 Hales 2002 年的伯克利博士论文），本文降到 $4n$ 比特加最近邻，对特定结构的状态可再降到 $2n$ 比特。深度维持对数不变，全部收益在比特数与连接性上。
• Takahashi–Kunihiro（2005）的 QFT 加法器省下的是辅助比特（降到 0），规模线性。标题与摘要都没有主张降低 T 数。

四、只是重新排列门

这一类改的是顺序与并行度，门集合和门计数都不变：

• Cleve–Watrous（2000）、Maslov（2007）、Kahanamoku-Meyer 等（2025）——分别是并行线路、有限邻接架构下的线性深度、原位对数深度。
• Bäumer 等（2024）——用动态线路（中途测量 + 前馈）实现 QFT。
• Schober–Wesley（2026）——在 QFT 加法器与进位加法器之间做显式门级转译。注意这一条是等价性结论，不是”某一种范式更省”：转换是双向门级对应，翻译过去之后门计数天然相同。它证明的是两种范式同源。
• Lopes（2026）——乐观 QFT 的 hot-zone 协同设计，摘要通篇是并行度与时延的权衡。

五、怎么读下一张 QFT 论文的成本声明

读 QFT 论文的成本声明：先问它动的是哪一项资源

三个常见的误读，以及对应的自查方法：

1. “深度降到 $O(\log n)$“被当成”线路变便宜了”。 深度降但门计数不变时，总工作量不变，只是墙钟时间变短。在测量与前馈有固定开销的架构上，深度甚至可能因为多了测量而变差。
2. “不需要辅助比特”被当成”T 数更低”。 辅助比特决定空间，T 数决定容错开销，两者是正交的账。
3. 只给渐近式不给常数。 本主题里唯一带完整常数对照的是 Park–Ahn：它同时给出改进前后的 T 数与 T 深度常数倍，并说明常数差别来自哪里。读到只有 $O(\cdot )$ 的声明时，应默认它对工程估算帮助有限。

论文依据

• Nam–Su–Maslov（2018/2020） —— 本词条的基线口径与第一条真改进。摘要明示标准容错 QFT 的 $O(n{\log }^{2}n)$ 来自”去掉小角度受控旋转并把其余合成到 Clifford+T”，本文用测量与前馈加相位梯度态复用降到 $O(n\log n)$，并给出渐近分析与具体线路。
• Park–Ahn（2022） —— 第二条真改进。给出改进前后的 T 数与 T 深度（约 $8n{\log }_2(n/\epsilon )$ → 约 $4n{\log }_2(n/\epsilon )$，约 $2n{\log }_2(n/\epsilon )$ → 约 $n{\log }_2(n/\epsilon )$），并指出此前一半 T 数来自 Toffoli 门、新构造完全不需要 Toffoli。
• Gidney（2017/2018） —— 第三条真改进，但对象是加法器：以”临时逻辑 AND”把 $n$ 比特加法器 T 数从 $8n+O(1)$ 降到 $4n+O(1)$，受控加法器同量级；论文明示该技术适用于 QFT 与 Shor。
• Bäumer–Sutter–Woerner（2025） —— “只降比特数”的样本：$8n$ 比特全连接结果降到 $4n$ 比特线上、特定结构 $2n$，深度仍是对数，未主张降低 T 数。
• Takahashi–Kunihiro（2005） —— “只降辅助比特”的样本：线性规模、无需辅助比特。
• Cleve–Watrous（2000） —— “重排”一类的奠基条目：快速并行线路。
• Maslov（2007） —— 有限邻接架构下 QFT 与稳定子线路的线性深度并行化，且不使用辅助比特；主张的是并行度而非门数或 T 数。
• Kahanamoku-Meyer 等（2025） —— 原位、对数深度、极少需要辅助比特的 QFT；深度与辅助比特的改进，不涉及 T 数口径。
• Bäumer 等（2024） —— 动态线路 QFT，改变的是中途测量与前馈的编排。
• Schober–Wesley（2026） —— QFT 加法器与进位加法器的显式门级转译；等价性证明，不是成本比较。
• Lopes（2026） —— 架构—算法协同设计，明确是并行度与时延的权衡。
• Coppersmith（2002） —— 截断阈值这一杠杆的最早独立来源：丢掉小角度受控相位以得到适用于因式分解的近似 QFT。

延伸阅读

• qft-overview —— 三种形态与本判据的上下文
• approximate-qft —— 截断阈值 $\epsilon$ 怎么定
• semiclassical-qft —— 用测量换门集合的第三条路
• gate-cost-models —— T 数、深度、比特为什么是三种不同的账