QFT 总览

量子傅里叶变换是全站唯一一个”既不消耗算术原语、又单独决定算法成败”的部件。它在 Shor 的四段顶层结构里占一段，在相位估计里占读出那一步，在 QFT 加法器里则是把进位从”线”换成”相位”的工具。本词条给出全卷的坐标系：变换本身、成本的落点、三种实现形态，以及本卷最重要的一条阅读纪律——论文报告的是 T 数、比特数还是深度，这三件事经常被混着写。

一、变换本身，以及它为什么绕不开

QFT 是经典离散傅里叶变换在 $N=2^n$ 维上的量子版本：它把一个基态送到所有基态的等幅叠加上，相位是输入的二次型。

$$|x⟩⟼\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{e}^{2\pi ijx/N}|j⟩,N=2^n.$$

它的三个用途在本站分属不同的卷，但源头是同一个结构：

• 从叠加里读出周期。 在 Shor 的因数分解里，模幂把”周期”编码进叠加的相位，逆 QFT 把这个周期性变成傅里叶谱上的尖峰，测量再配连分数法就能读出周期。这是 QFT 最著名的用途，Shor（1994/1997/1999）是这一用途的原始出处。
• 读出特征值。 相位估计的读出步骤本质上就是一次（半经典的）QFT。振幅放大与振幅估计的经典文献是 Brassard–Høyer–Mosca–Tapp（2002）。
• 把加法换成相位累加。 在傅里叶基上，加一个常量对应一串对角相位门，进位没有对应的线，辅助比特可以是零。这是 QFT 加法器的出发点，也是本卷算术侧的内容。

二、成本落在哪里

一个 $n$ 比特 QFT 展开后只有三类门：$n$ 个 H 门、一串角度为 $2\pi /2^k$ 的受控相位、以及最后把比特次序翻过来的交换门。门数因此是

$$n+\frac{n(n-1)}{2}+O(n)=O(n^2).$$

真正的问题不在这条式子，而在下一句：这些受控相位的角度 $2\pi /2^k$ 一般不是 Clifford+T 的元素，所以”精确 QFT”根本不是一条容错线路。Nam–Su–Maslov把标准容错实现写成两步：先去掉小角度的受控旋转，再把剩余的合成到 Clifford+T——这两步合起来产生 $O(n{\log }^{2}n)$ 的 T 数。这是全卷所有后续数字的比较基线，合成与成本一词条把它拆开逐项算。

由此可以区分三个经常被混为一谈的量：

量	由什么决定	谁在动它
门数 $O(n^2)$	变换本身	基本没人能动，除非换成半经典形态
深度	受控相位的调度与架构	[[sources/QQFT010
T 数 $O(n{\log }^{2}n)$	截断阈值 + 合成方法	QQFT005、[[sources/QQFT003

三、三种实现形态

同一个变换在文献里有三种落地形态，它们不是精度档位，而是架构档位：

形态	门集合	量子比特	什么时候选它
精确 QFT	任意角受控相位	$n$	只在理论分析、或小规模演示里用；不可容错
近似（截断）QFT	Clifford+T + 可容错测量前馈	$n+O(\log n)$	测量昂贵或不可用时的主线，见 approximate-qft
半经典 QFT	单比特门 + 测量 + 经典前馈	$1$（加经典寄存器）	测量便宜、连线受限时，见 semiclassical-qft

近似的”近似”和半经典的”半经典”是两个独立旋钮：前者调精度，后者调架构。Kahanamoku-Meyer 等 2025还提供了第三种思路——乐观 QFT，不砍门而是放宽误差定义（只在绝大部分输入上正确），再给出一条把乐观线路还原成全输入近似的归约。这条路线与逐门截断不是一回事，approximate-qft一词条专门对照。

四、一条贯穿全卷的判据

同一批 QFT 论文里，有的真的把 T 数砍掉了一个对数因子，有的只是把门换个顺序排好。二者在摘要里的措辞几乎一样，因此必须按下表分类：

类别	判据	本卷实例
真正降低 T 数	来源明示了 T 数的下降幅度	[[qft-synthesis
只降低比特数 / 连接代价	省的是空间或 SWAP，门计数不变	[[sources/QQFT006
只是重新排列	门集合与门计数都不变，改的是顺序或并行度	QQFT010、QQFT004、QQFT022、[[sources/QQFT015

这条区分不是吹毛求疵：它决定了一篇论文的数字能不能进你的资源估算表。

3 比特精确 QFT：H 门阶梯 + 受控相位阶梯 + 比特序翻转

图中三层的结构是”一次 H + 一串受控相位”，每层作用在一根新线上并对所有更低位做旋转。$n$ 层的一般形式见QFT 的门结构。

论文依据

• Nam–Su–Maslov（2018/2020） —— 给出本卷的基线口径：标准容错 QFT 是”去掉小角度受控旋转并把其余合成到 Clifford+T”，T 数 $O(n{\log }^{2}n)$。本词条”成本落在哪里”一节直接依据此句。
• Cleve–Watrous（2000） —— QFT 的快速并行线路；深度类改进的奠基条目。
• Maslov（2007） —— 线性最近邻等有限邻接架构下 QFT 与稳定子线路的线性深度并行化，且不使用辅助比特；同文亦给出配套下界。
• Kahanamoku-Meyer 等（2025） —— 乐观 QFT：$O(\log (n/\epsilon ))$ 深度、$n$ 总比特、无测量，并给出还原到全输入近似的归约。本词条用它说明”近似”不等于”截断”。
• Bäumer–Sutter–Woerner（2025） —— 全部收益落在比特数与连接性上（经典全连接结果需 $8n$ 比特，线上版本降到 $4n$，特定结构 $2n$），深度维持对数。本词条用它作为”只降比特数”的样本。
• Takahashi–Kunihiro（2005） —— QFT 加法器省下的是辅助比特（降到 0），规模线性；标题未主张降低 T 数。
• Bäumer 等（2024） —— 用动态线路实现 QFT；改变的是中途测量与前馈的编排方式。
• Brassard–Høyer–Mosca–Tapp（2002） —— 振幅放大与振幅估计的经典出处；QFT 在其中承担读出特征值的角色。
• Shor（1994/1997/1999） —— QFT 用于读出周期的原始出处。

延伸阅读

• qft-gates —— $n$ 比特 QFT 的递归层结构
• qft-synthesis —— T 数账目与”重排 ≠ 变便宜”的完整判据表
• approximate-qft —— 截断的线路对照图
• semiclassical-qft —— 1 根量子线的实现
• Shor 线路路线图 —— QFT 在顶层结构里的位置