计数与寄存器

大算术是由小算术拼起来的：加法器是计数器加比较器，模幂是重复的模乘，模乘是重复的模加。而这些”零件”本身也不是免费的——加一在可逆设定下要用 $O(n)$ 个门、比较器要用 $O(n)$ 个辅助比特。理解这些零件的代价，才能解释为什么把大线路做”薄”往往比把它做”少”更划算。

加一：最小的算术

给 $n$ 比特寄存器加 1，在经典里是一条指令；在可逆设定下它是一条 $O(n)$ 门、$O(n)$ 深度、零辅助比特的线路：一条受控翻转链，进位从最低位向最高位传播，遇到第一个 0 就停。

加一：进位链从 x₀ 向上传播，最高位溢出到单独的进位出线

注意 cout 上那个 CNOT：溢出必须显式落到一根单独的线上。经典里这一步被整数溢出规则吞掉了，量子里不行——要么加一根线接住它，要么用它做溢出检测。这一根线的去留，是”寄存器宽度选 $n$ 还是 $n+1$“这类问题的全部内容。

加一的深度是 $O(n)$，这是串行进位的固有代价。想压深度就得用进位先行（见进位先行加法器），代价是 $O(n)$ 辅助比特。

比较：比加法贵

判断 $a\ge b$，最直接的做法是算 $a-b$ 看借位出。但要让借位出可读而不是被丢掉，就需要一根独立的借位线——这已经比加法多一根线了。比较器因此成为模归约的主要成本项（见比较器与相等判定）。

相等判定更微妙。朴素做法”算差、归约到 0、测最高位”需要 $O(n)$ 辅助比特来存差值。由于量子上不能靠销毁信息来求和（无界 fan-out 门能常数深度做到，但那是另一套门集，见 MOD007），实际的相等判定通常也是 $O(n)$ 空间。

溢出检测与条件寄存

溢出检测是加一的副产品：进位出为 1 即溢出。模 $2^n$ 加法的”免费午餐”就建立在这上面——$a+b\mathrm{mod}{2}^n$ 恰好等于丢弃进位出的结果（见进位与借位）。

条件寄存（把 $a$ 暂存到 $b$ 指定的位）是窗口化模幂的基本件：它本质上是一个多路选择器，在量子里要用受控交换链实现，代价 $O(n)$ 门且需要先把目标位清零。窗口化方案之所以用比特换比特数，就是因为每一块窗口都要这样一个条件寄存器（见窗口化指数化）。

零件的代价汇总

零件	门数	深度	辅助比特	备注
加一 / 减一	$O(n)$	$O(n)$	0	需显式处理进位出
比较（借位链）	$O(n)$	$O(n)$	1	借位线必须独立
相等判定	$O(n)$	$O(n)$	$O(n)$	量子无破坏性求和
条件寄存	$O(n)$	$O(n)$	0	目标位需先清零
计数器清零	$O(n)$	$O(1)$	0	全部 $X$ 门，可完全并行

最后一行值得注意：清零与加一的门数相同，但深度差一个数量级——清零就是给每根线各放一个 $X$，全部并行。这提示了一个通用优化思路：当某段工作区的生命周期是”用完就扔”时，把它清成 $|0{⟩}^{\otimes n}$ 往往比让它自然回零更便宜，因为后者要么加门要么加测量。

为什么零件决定全局

把这些代价代进大线路，立刻得到几条实用的判断：

• 模幂里的辅助位主要由”工作寄存器 + 条件寄存器 + 工厂”三块构成，其中条件寄存器随窗口数增长（见门代价模型）；
• 进位先行省深度但吃比特，在比特昂贵的架构上是负优化；
• 比较器是模归约的瓶颈，而比较器又依赖”求和不销毁信息”这条量子特有的约束——这是模算术比线性算术贵的根本原因。

延伸阅读

• 进位与借位 —— 计数器的进位结构
• 门代价模型 —— 辅助比特为何是主要成本
• 比较器与相等判定
• 窗口化指数化 —— 条件寄存器的主要用户