Takahashi–Kunihiro QFT 加法器｜量子算术运算线路知识库

这是唯一一条把进位从”线”变成”相位”的路线。Draper 提出把加数按累加器的傅里叶系数展开成一列受控相位门，加法于是退化成相位累加——不需要任何进位线，也不需要辅助比特，是所有加法器里比特数最低的。代价同样明确： $O (n^{2})$ 个角度随 $2^{- i}$ 变小的受控旋转，在容错模型里合成代价高昂。Takahashi–Kunihiro 的贡献是重新排布这些相位校正，使线路规模线性且完全不需要辅助比特，只用 Toffoli 与 CNOT。

Draper 加法器的构造

设累加器在计算基上存 $x$ ，其傅里叶基展开为

∣ x ⟩ = \frac{1}{N} k = 0 \sum N - 1 e^{2 π ik x / N} ∣ k ⟩, N = 2^{n} .

要让 $x$ 增加常量 $b$ ，在这个展开上作用一串对角相位门：

∣ k ⟩ ⟼ e^{2 π ik b / N} ∣ k ⟩ .

按 $b$ 的二进制位展开， $e^{2 π ik b / N}$ 分解为一串作用在 $∣ k ⟩$ 上的受控 $Z$ 旋转：若 $b$ 的第 $i$ 位为 1，就对 $k$ 的前 $i$ 位为全 1 的部分旋转角度 $2 π / 2^{i + 1}$ 。这些”受 $2^{i}$ 整除”的条件正是量子线路能直接表达的受控条件。

于是加法器变成一列旋转门，进位没有对应的线——它隐含在相位累加的结果里。这是全部相位加法器的祖先（QA004）。

Draper QFT 加法器：加数按傅里叶系数展开为受控相位

（图中旋转角取 $π / 2^{i + 1}$ 量级示意；最低位对应最小角度。）

三个结构性优点

QA004 在摘要里明确点出了三项能力，值得逐条展开：

比特数最低。 因为不需要临时进位比特， $n$ 比特加法只需 $n$ 比特累加器。QA018 确认了这一点——Draper 傅里叶加法器提供任何加法器中最低的比特数。

能把经典数加到量子叠加态上。 更重要的是，加数 $b$ 可以是经典常量，而不必编码进量子寄存器。QA033 指出这个特性让该加法器天然适配”最近邻机器上实现 Shor”这类约束：把 Draper 的变换加法器与近似思想结合，可以得到线性宽度、二次深度的线路——尽管该文也坦承两条路线（用小角度受控旋转的版本、只用可逆经典门的版本）哪个更便宜当时还不确定。

执行可大规模并行。 相位门之间的依赖极弱，理论上可以在全连通架构上同时施加。

为什么容错模型下这条路线难

三篇文献从不同角度给出同一判断。

小角度受控旋转是软肋。 QA018 的原话：Draper 傅里叶加法器比特数最低，但需要大量门与极精细的旋转。在容错模型里，一个非 Clifford 旋转要靠魔法态分解合成，角度越小所需级数越高。 $2^{- n}$ 量级的角度在实用上是不可合成的。

分带（banding）是缓解，但会带来误差。 QA018 给出对策并量化了代价：把极小角度旋转截断到很粗的级别（RSA-2048 的 Shor 场景下，每次 QFT 可截断到 $π /64$ ，加性旋转只留略细一点的），配以策略性修正，从而在不牺牲比特节省的前提下降低硬件要求。代价是保真度损失，而损失直接由计算中的进位与借位率给出——论文给出了预测公式，并用门级矩阵乘积态模拟补全。

噪声与分带存在互补关系。 QA019 在任意维 qudit 上给出解析上界：在局域噪声下采用分带时，常数深度的近似线路反而优于旋转数更多的线路。这个结论相当反直觉——它意味着”更深度、更高保真”与”更浅、带噪声”之间不是简单的优劣关系。

Takahashi–Kunihiro：重排相位校正

Takahashi 与 Kunihiro 的改动可以概括为：把 Draper 加法器中串行的相位校正重排，使线路规模线性且不需要辅助比特，门集只用经典可逆门。QA006 在这条线上继续推进，给出三个具体数字：无辅助位、 $O (n)$ 深度、 $O (n)$ 规模，精确规模为 $7 n - 6$ ——论文称这是当时任何无辅助位加法器中规模最小的。由此还能推出更一般的构造：对任意 $d (n) = Ω (lo g n)$ ，用 $O (n / d (n))$ 个辅助位换 $O (d (n))$ 深度。

而一旦允许无界 fan-out 门（fan-out 长度 $O (n^{c})$ ， $c$ 为任意小的正常数），深度可以压到 $O (e (n))$ ，其中 $e (n) = Ω (lo g^{*} n)$ ，辅助位降到 $o (n)$ 。QA006 把这些线路用于 Shor 离散对数算法。

这里必须加一个限定：无界 fan-out 不是标准门集。允许这类门会改变经典模拟的复杂度性质，所以”对数深度加法”这个结论在实用语境下要打折扣。QA034 也从另一侧说明了原因——不存在对未知量子态做加法的酉，无辅助系统时对已知正交基的加法同样被禁止。辅助比特承担的是原理上不可省的角色。

融合：QFT 结构 × Toffoli 计账

近年的进展是把 QFT 结构与 Clifford+T 计账合并起来，这构成hybrid-adders的主题。三条可核验的路径：

系统性翻译。 QA007 给出 QFT 加法器到 Toffoli 加法器的第一次系统翻译，方法是为多控门构造新的线路恒等式并算法化地应用它们。结论相当重要：QFT 加法与最省 Toffoli 加法具有根本相同的容错成本（如 T 数），因此与其对 QFT 线路的各个门做近似分解，不如直接合并门。该文还指出这套技术可用于自动化量子线路优化启发式。

门级互变换。 QA025 用一种新的受控线路操作技术，在基于 QFT 的加法器与基于经典可逆逻辑进位技术的加法器之间做显式的门级转译；同一篇还给出一种自然解释为进位先行、且不使用任何辅助比特的新加法器。

架构匹配。 QA016 提出的高基数进位先行加法器在 T 数上仍优于 Draper 的 out-of-place 加法器——说明”比特最省”与”T 数最省”是两回事。QA033 则把 Draper 加法器用在小宽度最近邻的 Shor 实现上，但需要引入近似。

什么时候该用 QFT 加法器

给一条可操作的判断：

比特是最紧的资源（如要在一个很小的 QPU 上跑），QFT 加法器是唯一比特数低于 $2 n$ 的选择。
需要把经典常量加进量子寄存器（如模归约的偏移量、窗口化模幂里的常量），相位加法器天然支持，见constant-and-increment-adders。
在做 Shor 且愿意接受近似，QA018 的分带结论（截断到 $π /64$ ）与 QA033 的最近邻版本都是可核验的选项。
在做资源对比的基线，QA016 的原文就是拿自己的高基数 QCLA 与 Draper out-of-place 加法器对 T 数——说明这个对比是文献里的标准动作。

论文依据

Draper 2000 —— 相位加法器的祖先。用量子傅里叶变换实现求和，去掉了临时进位比特的需要，并允许把经典数加到量子叠加态上而无需把经典数编码进量子寄存器。
Takahashi–Kunihiro 2005 —— 给出线性规模的 QFT 加法器且不需要辅助比特，只用经典可逆门；本词条标题路线的主体来源。
Takahashi–Tani–Kunihiro 2009 —— 无辅助位 $O (n)$ 深度 $O (n)$ 规模（精确 $7 n - 6$ ）的构造，以及用 $O (n / d (n))$ 辅助位换 $O (d (n))$ 深度、在无界 fan-out 下达到 $O (lo g^{*} n)$ 深度的结果。
White–Hill–Hollenberg 2021 —— 确认 Draper 加法器比特数最低但需要大量门与极精细旋转；给出截断到粗角度并以进位/借位率预测保真度损失的方案，RSA-2048 下每次 QFT 可截断到 $π /64$ 。
Agrawal 等 2023 —— 任意维 qudit 的 QFT 加法器，分带下受控旋转数的解析上界，以及”有噪声时分带的常数深度近似线路优于高旋转数线路”的互补关系。
Paler 2022 —— QFT 加法器到 Toffoli 加法器的第一次系统翻译，论证两者容错成本（如 T 数）根本相同。
Schober–Wesley 2026 —— QFT 加法器与进位链加法器之间的显式门级转译，并给出无辅助位的进位先行型新加法器。
Wang–Baksi–Chattopadhyay 2023 —— 高基数进位先行加法器，在 T 数上仍优于 Draper 的 out-of-place 加法器。
Kutin 2006 —— 用 Draper 变换加法器结合近似思想，在最近邻机器上给出线性宽度、二次深度的 Shor 实现；同文坦承两个版本哪个更便宜尚不确定。
Alvarez-Rodriguez 等 2014 —— 无辅助系统加法的禁止性结果，用于说明”零辅助位”这条路的原理边界。
Gidney 2025 —— 经典–量子加法器达到 3 个洁净辅助位 + $4 n \pm O (1)$ 个 Toffoli，为”经典常量加进量子寄存器”提供了进位路线的对照方案。

量子算术线路百科

探索

Takahashi–Kunihiro QFT 加法器