QFT 的门结构

QFT 线路的门集合小得出奇：H 门、受控相位、交换门，没有第四种东西。全部的工程困难来自两件事——受控相位的角度随线的位置指数变小，以及 H 门之间存在串行依赖。本词条把这个结构逐层写出来，并说明为什么”门数 $O(n^2)$“与”深度可以做到对数”能同时成立：前者是相位数，后者靠的是把这些相位按层错开调度。

一、层结构：一个 H 加一串受控相位

设 $x=(x_{n-1},\dots ,x_0)$，按本站的大端约定 $q=0$ 是最高位 $x_{n-1}$。QFT 可以按 $n$ 层展开，第 $k$ 层作用在 $x_{n-k}$ 上：

$$\begin{array}{rl}\text{第 }k\text{ 层}(k=1,\dots ,n):& H\text{ 作用在 }{x}_{n-k}\\ & \text{随后对 }j=n-k-1,\dots ,0\text{ 依次施加受 }{x}_{n-k}\text{ 控制、}\\ & \text{角度为 }2\pi /2^{n-k-j+1}\text{ 的相位旋转}\end{array}$$

这正是经典快速傅里叶变换的 Cooley–Tukey 分解在量子线路上的样子：$n$ 个单比特子问题，每个后面挂一串把它的比特混进去的受控相位。$k$ 越大（越靠近最低位），控制线越靠下、要混进去的线越少、相位角度越大。全部层做完后再加 $\lfloor n/2\rfloor$ 个交换门把比特序翻回来。

3 比特 QFT 的层结构：每层一个 H 加一段受控相位阶梯

读这张图时注意两点。第一，同一层里的两个受控相位可以并行（图 1 中它们在同一列），因为它们共享控制线但作用在不同目标上。第二，相邻层之间有串行依赖：第 2 层的 H 作用在 $x_1$ 上，而第 1 层刚对 $x_1$ 做过旋转，所以必须等第 1 层走完。

二、门数与深度为什么不是一回事

按上面的层结构数门：$n$ 个 H、$n(n-1)/2$ 个受控相位、$\lfloor n/2\rfloor$ 个交换，总计 $O(n^2)$。

但深度不必是 $O(n^2)$，原因在调度：受控相位彼此只共享控制线而目标不同，同一层内乃至相邻层内的很多门可以重叠执行。真正无法消除的串行链是那 $n$ 个 H，所以朴素线路的深度至少是 $\Omega (n)$。把这条链也拆开是”快速并行线路”这类工作的目标——Cleve–Watrous（2000）给出的正是 QFT 的快速并行线路，其标题本身就是结论。

n 层结构的计数与调度：×n 的层单元，层内 H 加受控相位阶梯

三、架构与调度：动的是哪一项

上面这张图的”层”是一个抽象结构，它要落到具体硬件上还有两个约束：哪些两根线之间允许放门（连接性），以及交换门要走多远。这两件事是本主题里”深度类”论文的全部内容，而它们不改变门计数。

• Takahashi、Kunihiro 与 Ohta（2007）讨论的正是 QFT 在线性最近邻架构上的实现，交换门在这个架构上不再是免费的。
• Maslov（2007）在线性最近邻、二维晶格、有界度图三类架构下把 $n$ 比特 QFT 并行化到线性深度且不使用辅助比特，并给出配套下界。注意这里动的是深度与辅助比特，不是 T 数。
• Kahanamoku-Meyer 等（2025）走的是原位加对数深度的路线：$O(\log (n/\epsilon ))$ 深度、$n$ 总比特、很少需要辅助比特，并且是无测量的。同一篇还给出了乐观版本与还原到全输入近似的归约，见approximate-qft。
• Lopes（2026）是架构—算法协同设计的样本，摘要通篇讲并行度、时延与比特预算的权衡，没有主张降低 T 数。

四、与容错的距离

这一层的结构讲完，还有一个必须点破的事实：角度 $2\pi /2^{n-k-j+1}$ 一般不是 Clifford+T 的元素，因此上面两节描述的都是精确 QFT，它不能直接容错。标准做法是丢掉角度小于阈值的那一部分受控相位，把剩下的合成到 Clifford+T，由此得到 $O(n{\log }^{2}n)$ 的 T 数（QQFT005）。也就是说，截断不是实现细节，而是容错性的前提；这正是近似与截断 QFT的主题，也是本卷全部 T 数讨论的起点。

论文依据

• Cleve–Watrous（2000） —— 给出 QFT 的快速并行线路，证明”QFT 不必串行执行”。本词条”门数与深度”一节关于串行 H 链的讨论以之为对照。
• Maslov（2007） —— 线性最近邻、二维晶格与有界度图三类架构下，$n$ 比特 QFT 与 $n$ 比特稳定子线路的线性深度并行化，不使用辅助比特，并给出配套下界构造。
• Takahashi、Kunihiro 与 Ohta（2007） —— QFT 在线性最近邻架构上的实现与讨论，即交换门在受限连接下的代价。
• Kahanamoku-Meyer 等（2025） —— 原位、对数深度、极少需要辅助比特的无测量 QFT 线路。
• Tucci（2004） —— 把量子快速傅里叶变换统一为余弦–正弦分解（CSD）的递归应用特例；本词条的层结构是自顶向下的写法，Tucci 给的是同一条结构自底向上的分解。
• Marquezino、Portugal 与 Sasse（2010） —— 由经典 FFT 的 QR 分解构造 QFT 的纯代数路径，说明这条结构也可从经典算法侧反推得到。
• Nam–Su–Maslov（2018/2020） —— 明确写出”去掉小角度受控旋转并把其余合成到 Clifford+T”产生 $O(n{\log }^{2}n)$ 的 T 数；本词条第四节的口径来源。
• Lopes（2026） —— 乐观 QFT 的架构—算法协同设计，收益落在并行度、时延与比特预算上，未主张降低 T 数。

延伸阅读

• qft-overview —— 三种实现形态的坐标系
• approximate-qft —— 截断阈值 $\epsilon$ 与完整/截断的线路对照
• qft-synthesis —— 门结构如何换算成 T 数
• qft-in-zx-calculus —— 换一个表示看同一条层结构
• circuit-representation —— 图中各记号的规范写法