QFT 算术

QFT 在算术里的作用不是”把数变过去”，而是换一个基来表达算术。在工作寄存器的傅里叶基上，加一个常量是一串对角相位门，进位因此没有对应的线，辅助比特可以降到零。本词条讲清这条链上的三段（变换、相位累加、逆变换），补上条件干净辅助比特这一新的资源类型，再给出两条本主题里最硬的证据：QFT 加法器与进位加法器可被证明是门级同源的，以及分带在噪声下的非直觉权衡。

一、变换域上的加法：进位没有线

设累加器在计算基上存 $x$，其傅里叶展开把 $|x⟩$ 写成系数 $k$ 的叠加：

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

在这个展开上，让 $x$ 增加常量 $b$，只需要让每个系数 $k$ 乘上一个相位 $e^{2\pi ikb/N}$。按 $b$ 的二进制位展开，$e^{2\pi ikb/N}$ 分解为一串条件是”$k$ 的高位全为 1”的受控相位门：$b$ 的第 $i$ 位为 1，就对条件满足的部分旋转角度 $2\pi /2^{i+1}$。

这就是全部机制。进位不是一个需要被搬运的中间量，它只存在于相位累加的结果里。 代价是 $O(n^2)$ 个角度随 $2^{-i}$ 变小的受控旋转——在容错模型里，这正是截断问题的来源。

变换域算术的三段：变换 → 相位累加 → 逆变换

Takahashi–Kunihiro（2005）在这条链上的贡献是把②里的串行相位校正重新排布，使线路规模线性且完全不需要辅助比特。要注意这句话的读法：省下的是辅助比特，规模是线性的，标题与摘要都没有主张降低 T 数（见qft-synthesis）。更细的构造与资源对比在Takahashi–Kunihiro QFT 加法器一词条。

二、乘法与变换域的其它读出

Ruiz-Perez 与 Garcia-Escartin（2014，期刊 2017）是本主题唯一一篇可核实的综述，标题就是”用 QFT 做量子算术”。它覆盖了 QFT 加法器与 QFT 乘法器并提出扩展，新线路里包含一类值得单独记住的构造：在变换域上直接计算输入序列的加权平均。这类”把统计量放进变换域”的做法与逐元素算术不同，它关心的是把一整段序列的某个泛函求出来。

需要如实说明一处空白：QFT 型的乘法、除法、减法与模算术线路，本轮未定位到可核实的定义性文献。 因此本词条只给出综述层面的事实，不复述未经核实的具体线路；本站乘法卷的乘法线路是教科书式逐行累加的，与 QFT 型的关系尚未见可核实的对比。

三、条件干净辅助比特

Khattar 与 Gidney（2025）引入条件干净辅助比特（conditionally clean ancillae），一种介于洁净与污损之间的新资源：像污损辅助比特一样，它们起始与终止都处于未知态，可以从系统里现有的比特借用，从而免去显式分配的空间开销；又像洁净辅助比特一样，在特定计算里可以当作已知态处理，因此省掉污损辅助比特所需的翻转检测开销。论文给出的构造覆盖 $n$ 控制 NOT、$n$ 比特递增器、量子—经典比较器与一元迭代等原语，并给出把洁净辅助换成污损辅助的阶梯式翻转检测（代价为 2 倍 Toffoli 开销）。各条的具体门数与深度见下文的论文依据。

它对本卷的意义在于：辅助比特可以是”有条件的”，因此”这个加法器需要几个辅助比特”必须先问”什么样的辅助比特”。这一类工作改善的是比特与门计数口径，引用时仍要按合成与成本的三栏归类。

四、qudit 与分带

把变换域算术推广到任意维是 Pavlidis 与 Floratos（2021）的工作，Dong、Lu 与 Sun（2022）则给出对称三进制 QFT 及其应用。在 $d$ 进制下”小角度”的阈值与 $d$ 的幂次直接挂钩，于是分带（banding）成为一个可解析处理的对象。

Agrawal 等（2023/2025）给出了这条线上最反直觉的结果：为达到任意保真度缺陷所需的受控旋转门数量存在解析上界；并且证明在噪声下采用分带时，常深度的近似线路优于受控旋转更多的近似线路。它的含义是，“更浅但带噪声”与”更深更高保真”之间不是简单的优劣关系——这也是本站加法卷里分带结论的同源表述。

五、两种范式同源

QFT 加法器与进位加法器：门级转译是等价性，不是成本比较

Schober–Wesley（2026）在 QFT 加法器与基于经典可逆逻辑的进位加法器之间做显式的门级转译，同时给出一个无辅助位、可解释为进位先行的加法器。这条结果的正确读法是等价性：把一条翻译成另一条之后门计数天然相同，因此不能把它当成”QFT 范式更省”或”进位范式更省”的证据；它证明的是两种范式同源，并且顺带给出了新的加法器构造。

另一条同源性的旁证来自 Kaltehei 等（2025）：他们用 QFT 加法器（复现数字半加器的 sum/carry 功能）构造 AND、OR、XOR、NOR、NAND 的量子可逆对应。论文自己报告的取舍是：输入数少时初等门数量上升、乍看 inefficient，但随输入数增加，总比特数优于非 QFT 设计。这是一条”用门换比特”的具体样本，与第一节”进位没有线”的动机是同一个。

论文依据

• Ruiz-Perez 与 Garcia-Escartin（2014，期刊 2017） —— 本主题唯一一篇可核实的综述：覆盖 QFT 加法器与乘法器并提出扩展，新线路包含在变换域计算输入序列加权平均的量子方法。
• Takahashi–Kunihiro（2005） —— 线性规模、无需辅助比特的 QFT 加法器；省下的是辅助比特而非 T 数。
• Khattar 与 Gidney（2025） —— 条件干净辅助比特这一新资源：可借用、可在特定计算中当作已知态。给出 $n$ 控制 NOT（$2n$ 个 Toffoli、$O(\log n)$ 深度、2 个洁净辅助）、$n$ 比特递增器与量子—经典比较器（各 $3n$ 个 Toffoli、${\log }_2^{\ast }n$ 个洁净辅助）、一元迭代的两种排布（$2.5N$ 与 $1.25N$ 个 Toffoli，后者只需 $n$ 个污损辅助），以及阶梯式翻转检测的 2 倍 Toffoli 代价。
• Pavlidis 与 Floratos（2021） —— 基于 QFT 的 qudit 量子算术，把变换域算术推广到任意维。
• Dong、Lu 与 Sun（2022） —— 对称三进制 QFT 及其应用。
• Agrawal 等（2023/2025） —— qudit 情形下分带的受控旋转数解析上界，以及噪声下常深度近似线路更优的互补结论。
• Schober–Wesley（2026） —— QFT 加法器与进位加法器之间的显式门级转译，以及无辅助位的进位先行型新加法器；结论是等价性。
• Kaltehei 等（2025） —— 用 QFT 加法器构造 AND/OR/XOR/NOR/NAND 的可逆对应；小输入时门数上升，输入数增加后总比特数优于非 QFT 设计。

延伸阅读

• takahashi-qft-adder —— 同一条路线的门级细节与资源对比
• hybrid-adders —— QFT 结构与 Toffoli 进位结构的融合
• approximate-qft —— 变换域的 $O(n^2)$ 个小角度门怎么处理
• qft-synthesis —— 上面各条分别属于三类改进中的哪一类