本卷是整个量子算术的语法基础。几乎所有有实用意义的量子算法——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 数、魔法态、连接性)该选哪个加法器;这张表怎么用。 |