本卷是整个量子算术的语法基础。几乎所有有实用意义的量子算法——Shor 的模幂、格密码学的模归约、哈密顿量模拟里的指数算子——最终都把成本压到”两个 比特寄存器相加”这一件事上。加法器因此是全站唯一值得从 1995 年一路追到今天的线路族:它的结构变化不是渐进改良,而是几次范式切换。

本卷的编排按”结构性分歧”而不是按时间排序。进位链(ripple-carry) 把进位串行搬运,靠 MAJ/UMA 结构把辅助比特从 压到 1;QFT 加法器 干脆没有进位比特,改为在傅里叶基里做相位累加;进位先行(carry-lookahead) 用平衡树一次算出全部进位,深度 但辅助比特回到 。三者无法互相换算,代价落在不同资源上。

一条贯穿全卷的结论是:加法器之间没有全局最优,只有在不同资源约束下的不同最优。比特极贵时进位链赢(QA009 给出了这个方向的系统证据),魔法态工厂不足时低 Toffoli 数的进位链赢(QA014),二维最近邻架构上则必须换成脉动式结构(QA029)。本卷最后的资源对比把这一判断量化。

另有一条值得单独说的观察:文献里没有独立的”量子减法线路”。减法在所有已发表方案中都是 negadd(先取负再加),这是一个实现约定而非独立线路族——减法与 negadd一词条如实记录了这个空白,并说明文献实际上是怎么做的。

词条读完能回答
加法器谱系三条主路线(进位链 / QFT / 进位先行)在辅助比特、深度、门集上分别付出什么代价;为什么”哪种加法器最好”这个问题没有唯一答案。
VBE 进位链第一个显式量子加法网络长什么样;为什么它需要 辅助比特;这个缺陷如何催生了之后的三十年。
CDKM 精简加法器2 比特 MAJ/UMA 如何把进位”藏”进加数寄存器;为什么只需 1 个辅助比特还能保持线性深度。
MAJ/UMA 与反计算MAJ 把什么送到哪根线上、UMA 怎么把它变回和比特;为什么这一对结构能省掉整条进位比特链。
Takahashi–Kunihiro QFT 加法器不需要辅助比特的线性规模 QFT 加法器如何工作;相位旋转重排解决了什么、又留下了什么。
Kutin 并行前缀加法器并行前缀扫描在量子线路里为什么必须另找实现;“decide-to-make”思路如何绕开辅助比特。
进位先行加法器generate/propagate 平衡树如何一次算出全部进位;测量基、高基数、Kronecker 前缀和等变体各自的取舍。
减法与 negadd为什么文献里找不到独立的量子减法论文;negadd 具体在做什么;两’s 补码与借位的关系。
量子全加器器件级 1 比特全加器(QFA)与寄存器级加法器有什么本质不同;保输入全加器为什么是加法器的模块。
常数与递增加法器加数是编译期常数时能省多少;预先算出常数进位位置如何缩短进位链;比较器与递增器的最优界。
混合加法器QFT 结构与 Toffoli 进位结构如何互相改写;截断/分带把相位加法器拉进 Clifford+T 计账。
加法器资源对比面对具体资源约束(比特、深度、T 数、魔法态、连接性)该选哪个加法器;这张表怎么用。

阅读顺序建议

  • 第一次接触:加法器谱系 → CDKM 精简加法器 → 资源对比。其余按需。
  • 要读懂线路图:先看统一量子线路表示与比特序与寄存器约定,再进本卷。
  • 要做 Shor 资源估算:negadd → 常数与递增加法器 → 资源对比。
  • 要做编译或硬件映射:VBE 进位链 → Kutin 并行前缀 → 进位先行(含测量基变体)→ 混合加法器。