量子算术电路

量子算术电路是在量子线路中实现经典算术运算（加、比较、模加、模乘、模幂）的线路族。它与经典算术单元的根本差别在于可逆性：量子演化必须是幺正的，每一步都要保住全部信息——输入寄存器本身充当工作区，不能像经典电路那样随意丢弃中间进位。

量子算术是 Shor 算法中模幂运算 $a^x\mathrm{mod}N$ 的实现基础，也是 QRAM 地址译码、数据幅值编码与许多块编码构造的核心子程序。本词条按”可逆化 → 加法器 → 比较器 → 模算术 → 模幂”的顺序展开，每一步给出构造推导与精确成本。

历史脉络

• 可逆计算（1970–80 年代）：Landauer（1961）指出信息擦除有 $kT\ln 2$ 的能耗下限，Bennett（1973）证明任意计算都可用可逆机器模拟。Toffoli（1980）与 Fredkin–Toffoli（1982）给出通用可逆逻辑门（Toffoli 门、Fredkin 门），Bennett（1989）建立可逆计算的时间–空间折衷理论——量子算术的线路语汇直接继承自这一支。
• 量子算术网络（1996）：Vedral–Barenco–Ekert（VBE）给出第一批系统的量子算术线路（加法、模加、模乘、模幂），但需要 $O(n)$ 个辅助比特。
• 两条优化主线（1998–2004）：Draper（2000）发明 QFT 域加法器；Beauregard（2003）用它把 Shor 电路压到 $2n+3$ 比特；Cuccaro–Draper–Kutin–Moulton（CDKM，2004）把进位加法器压到单辅助比特；Draper–Kutin–Rains–Svore（2004）给出对数深度的超前进位加法器（代价是 $2n$ 辅助比特）。
• 容错时代（2018 至今）：Gidney 用相对相位 Toffoli 与”临时逻辑与”把加法的 $T$ 成本减半；量子算术的资源估计（如因数分解的千万比特口径）成为算法工程的核心科目。

可逆化：异或写回与成本模型

一个 $n$ 比特经典函数 $f$ 不能”读出写入”地直接作用在叠加态上，正确的可逆化是异或写回：

$|a⟩|b⟩\mapsto |a⟩|b\oplus f(a)⟩,$

即把 $f(a)$ 按位异或进目标寄存器。这保持幺正性（逆映射是把同一电路再跑一遍，当 $f$ 的经典电路可逆时），且允许 $a$ 处于叠加态——这是量子并行在算术子程序里的具体形态。

两个由此而来的结构性约束：

• 清理（uncompute）：任何临时计算的中间量（垃圾比特）都必须被逆运算擦除，否则与目标寄存器纠缠、破坏相干性。 Bennett 的”计算–拷贝–逆计算”三段式是标准解法，代价是线路近似翻倍。
• 成本模型：线路成本的主导项是 Toffoli 门数（其次是 CNOT 数与深度）。Toffoli 还要继续分解成硬件原生门（见基本门分解与多控门分解），其 $T$ 门开销直接牵动容错实现中魔术态蒸馏的成本。

进位的代数：多数投票恒等式

无符号加法 $s=a+b$ 的逐位结构完全由进位递推决定。设 $c_0=0$，则

$c_{i+1}=\mathrm{MAJ}(a_i,b_i,c_i)=a_i{b}_i\oplus a_i{c}_i\oplus b_i{c}_i,s_i=a_i\oplus b_i\oplus c_i,s_n=c_n.$

推导：第 $i$ 位相加的本位和显然是 $a_i\oplus b_i\oplus c_i$；向第 $i+1$ 位进位当且仅当 $a_i,b_i,c_i$ 三者中至少两个为 1，即多数投票 $\mathrm{MAJ}$。把”至少两个为 1”按包含—排斥展开就是 $a_i{b}_i\oplus a_i{c}_i\oplus b_i{c}_i$（三个两两乘积中恰有两个同时为 1 时相互抵消）。

进位加法器的全部设计空间就在于如何在可逆线路里产生并擦除这些 $c_i$。

Cuccaro MAJ–UMA 加法器（单辅助比特）

CDKM 的诀窍是一个原位多数投票门 MAJ：对三根线 $(c_i,b_i,a_i)$ 依次作用

1. $\mathrm{CNOT}{a}_i\to c_i$：得 $c_i\oplus a_i$；
2. $\mathrm{CNOT}{a}_i\to b_i$：得 $b_i\oplus a_i$；
3. $\mathrm{Toffoli}(c_i,b_i\to a_i)$：$a_i\leftarrow a_i\oplus (c_i\oplus a_i)(b_i\oplus a_i)$。

验证第 3 步恰是进位：展开 $(c\oplus a)(b\oplus a)=cb\oplus ca\oplus ab\oplus a$（用 $a\cdot a=a$），于是

$a\oplus (c\oplus a)(b\oplus a)=a\oplus a\oplus ab\oplus ac\oplus bc=\mathrm{MAJ}(a,b,c)=c_{i+1}.$

即三步之后三根线变成 $(c_i\oplus a_i,b_i\oplus a_i,c_{i+1})$：进位 $c_{i+1}$ 被写在 $a_i$ 线上，同时 $a_i,b_i,c_i$ 的信息以两个校子和的形式留在前两根线上。把 MAJ 沿位串接，进位就像经典行波进位一样从低位”流”到高位——每过一个 MAJ，进位就前移一根线。

UMA（Un-Majority and Add） 是收尾的逆过程，从 $(c_i\oplus a_i,b_i\oplus a_i,c_{i+1})$ 恢复出 $(c_i,s_i,a_i)$：

1. $\mathrm{Toffoli}(c_i,b_i\to a_i)$：逆掉第 3 步，恢复 $a_i$；
2. $\mathrm{CNOT}{a}_i\to c_i$：恢复 $c_i$；
3. $\mathrm{CNOT}{c}_i\to b_i$：$b_i\oplus a_i\oplus c_i=s_i$，本位和写入 $b$ 线。

（CDKM 还给出一个等价的 2-CNOT 版 UMA，把两步 CNOT 合并重组以提升并行度。）从高位到低位逐位执行 UMA，就把所有中间量擦干净、留下 $b\leftarrow a+b$。整个加法器只用一个置 $|0⟩$ 的辅助比特充当 $c_0$，外加一根输出线接收最高位 $s_n$。

精确成本（CDKM 原文 Table 1；加法行 $n\ge 2$、mod $2^n$ 行 $n\ge 3$）与 VBE 对照：

线路	Toffoli	CNOT	深度	辅助比特
CDKM 加法 $a+b$	$2n-1$	$5n-3$	$2n+4$	1
CDKM mod $2^n$ 加法	$2n-3$	$5n-7$	$2n+2$	1
CDKM 比较器（高位法）	$2n-1$	$4n-3$	$2n+3$	1
VBE 加法 $a+b$	$4n-2$	$4n-2$	$6n-2$	$n$

若允许 $2n$ 个辅助比特，Draper–Kutin–Rains–Svore 的超前进位版本深度降到 $O(\log n)$；一般地用 $n/k$ 个辅助比特可做到深度 $O(k+\log n)$（此折衷家族系 CDKM 结论段对 DKRS 结果的转述）——门数、深度与辅助比特的三方折衷贯穿整个领域。

Draper QFT 域加法器

Draper 的思路是把加法搬到傅里叶域：先对目标寄存器做量子傅里叶变换，在傅里叶域中加法没有进位传播，只剩相位旋转。

推导：QFT 后的态具有逐比特相位结构（大端约定，第 $j$ 个比特从高位数起，$m=n-j+1$ 为其权重位数）：

$\mathrm{QFT}|x⟩={⨂}_{j=1}^n\frac{|0⟩+e^{2\pi i(x\mathrm{mod}{2}^m)/2^m}|1⟩}{\sqrt{2}}.$

要得到 $x+b$，第 $j$ 个比特的相位需从 $2\pi (x\mathrm{mod}{2}^m)/2^m$ 变为 $2\pi ((x+b)\mathrm{mod}{2}^m)/2^m$。由于模 $2^m$ 只保留低 $m$ 位，增量恰是只依赖 $b$ 的经典相位

${\theta }_j=\frac{2\pi (b\mathrm{mod}{2}^m)}{2^m}={\sum }_{k=0}^{m-1}\frac{2\pi b_k}{2^{m-k}},$

其中 $b_k$ 是 $b$ 的第 $k$ 位。也就是说：在 QFT 域中，加 $b$ = 对第 $j$ 比特施加旋转角 ${\theta }_j$ 的相位门，每个角度又拆成若干 $2\pi /2^{\ell }$ 型基本旋转。若 $b$ 存放在量子寄存器中，这些旋转必须受控于 $b$ 的对应比特——位 $b_k$（权重 $2^k$）要旋转所有 $m>k$ 的比特，即 $n-k$ 个受控相位，总计 ${\sum }_{k=0}^{n-1}(n-k)=\frac{n(n+1)}{2}$ 个两比特门；若 $b$ 是编译期已知的经典常数，则退化为同样数量的单比特固定旋转，一个量子比特都不占。

代价与取舍：门数 $O(n^2)$ 多于进位加法器的 $O(n)$，但每个门都是局域受控相位——不需要 Toffoli、不需要辅助比特，且模算术与受控版本的组合格外方便（见下文 Beauregard 方案）。旋转角都是 $2\pi /2^k$ 型，有限精度下必须截断近似：保留到角度 $2\pi /2^{\ell }\ge \epsilon$ 的项即可把相位误差压到 $O(n^2\epsilon )$ 量级。CDKM 原文的比较结论是：两者深度同为线性，孰优孰劣取决于平台上 Toffoli 与受控旋转的相对成本；而在”加经典常数”这一情形 QFT 加法器明显占优。

减法与比较器

二进制补码把减法化归为加法，关键恒等式是按位取反的对合性：

$a-b=\overline{(\overline{a}+b)},$

推导：$\overline{x}=2^n-1-x$，故 $\overline{(\overline{a}+b)}=2^n-1-(2^n-1-a+b)=a-b$（mod $2^n$）。于是减法器 = 加法器前后各加一排 $X$ 门，只增加两个时间步。

比较器：计算 $a-b$ 并观察最高借位。用 CDKM 的”只算高位”变体（前半 MAJ 链 + 单个 Toffoli 写出 + 后半逆链）即可不破坏 $a,b$ 地拿到 $a\stackrel{?}{<}b$ 的判决：高位为 1 当且仅当 $a<b$。比较结果只能以受控操作或相位写回，不能对叠加态做破坏性测量。

模算术：从模加到模乘

模加 $\mathrm{ADD}(b)\mathrm{mod}N$（$0\le a,b<N<2^n$）：在普通加法器外套一层”溢出折返”——先算 $a+b$，若 $\ge N$ 则减 $N$。可逆实现：用比较器判定 $a+b\stackrel{?}{\ge }N$，把判决作为受控端控制一次减 $N$（等价于加补码 $2^n-N$），再把比较中间量清理掉。每次模加约两三个普通加法器的成本。QFT 域版本（Beauregard）以一次逆向 QFT 域加法读出溢出位、经辅助比特条件加回完成折返，无需完整的受控减法器。

模乘（受控版本）把乘数按二进制展开拆成移位模加：

$ax\mathrm{mod}N=\left({\sum }_j{a}_j\right(2^{j}x\mathrm{mod}N\left)\right)\mathrm{mod}N,$

即 $n$ 次受控模加（加数为经典预计算的常数 $2^{j}x\mathrm{mod}N$），配合移位式模加（“倍乘 $2x\mathrm{mod}N$“）串联。乘完必须把 $x$ 从寄存器里清理（uncompute）回去——受控模乘因此约为 $2n$ 次模加的成本。

模幂 $|x⟩\mapsto |a^x\mathrm{mod}N⟩$ 再套一层平方-乘结构：

$a^x\mathrm{mod}N={\prod }_{j:x_j=1}\left(a^{2^j}\mathrm{mod}N\right),$

即 $x$ 的第 $j$ 位控制一次”乘 $a^{2^j}\mathrm{mod}N$“的受控模乘，常数 $a^{2^j}\mathrm{mod}N$ 全部经典预计算。模幂由相位估计调用，正是 Shor 算法里量子部分体量最大的子程序。

Beauregard 的 $2n+3$ 比特方案：寄存器分四块——1 个可复用的单控制比特、$n$ 比特工作寄存器、$n+1$ 比特 QFT 域累加寄存器（多出的 1 位防溢出）、1 个辅助比特。模乘复用累加寄存器逐位移位模加；半经典相位估计的逐位测量反馈与逆变换穿插在模乘序列执行期间进行，测量反馈属于相位估计一侧，模加本身无需测量。Takahashi–Kunihiro（2006）进一步把总数压到 $2n+2$。更现代的优化（Gidney 把进位链中的 Toffoli 换成相对相位版本，见多控门分解）可把 $T$ 开销再减半。

成本汇总

以 $n$ 比特操作数、CDKM 型进位结构为基准（数量级）：

操作	Toffoli 数	深度	辅助
加法 $a+b$	$2n$	$O(n)$	1
比较器	$2n$	$O(n)$	1
模加 $\mathrm{mod}N$	$\sim 4-6n$	$O(n)$	2
受控模乘（$\sim 2n$ 次模加）	$\sim 8-12n^2$	$O(n^2)$	$O(n)$（可共享）
模幂（$n$ 次受控模乘）	$\Theta (n^3)$	$O(n^3)$	$O(n)$

模幂的 $\Theta (n^2)$ 个模加（合计 $\Theta (n^3)$ 个 Toffoli）分解到 Clifford+$T$ 后（每个 Toffoli 精确分解 7 个 $T$、相对相位版 4 个、测量版摊销约 2 个），就是因数分解资源估算中”魔术态工厂占比最大”的直接原因。

关联词条

• 分解基础：基本门分解、多控门分解
• 应用：Shor 算法、相位估计、量子傅里叶变换、块编码
• 容错成本：魔术态蒸馏

参考文献

• R. Landauer. Irreversibility and Heat Generation in the Computing Process. IBM J. Res. Dev. 5, 183 (1961).
• C. H. Bennett. Logical Reversibility of Computation. IBM J. Res. Dev. 17, 525 (1973); Time/Space Trade-Offs for Reversible Computation. SIAM J. Comput. 18, 766 (1989).
• T. Toffoli. Reversible Computing. MIT LCS Technical Memo 151 (1980).
• E. Fredkin, T. Toffoli. Conservative Logic. Int. J. Theor. Phys. 21, 219 (1982).
• V. Vedral, A. Barenco, A. Ekert. Quantum Networks for Elementary Arithmetic Operations. Phys. Rev. A 54, 147 (1996). arXiv:quant-ph/9511018 —— 首批量子算术网络（VBE）。
• P. Gossett. Quantum Carry-Save Arithmetic. (1998). arXiv:quant-ph/9808061
• C. Zalka. Fast Versions of Shor’s Quantum Factoring Algorithm. (1998). arXiv:quant-ph/9806084
• T. G. Draper. Addition on a Quantum Computer. (2000). arXiv:quant-ph/0008033 —— QFT 域加法器。
• S. Beauregard. Circuit for Shor’s Algorithm Using 2n+3 Qubits. Quant. Inf. Comput. 3, 175 (2003). arXiv:quant-ph/0205095
• S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton. A New Quantum Ripple-Carry Addition Circuit. (2004). arXiv:quant-ph/0410184 —— MAJ–UMA 单辅助比特加法器。
• T. G. Draper, S. A. Kutin, E. M. Rains, K. M. Svore. A Logarithmic-Depth Quantum Carry-Lookahead Adder. Quantum Inf. Comput. 6, 351 (2006). arXiv:quant-ph/0406142
• Y. Takahashi, N. Kunihiro. A Quantum Circuit for Shor’s Factoring Algorithm Using 2n+2 Qubits. Quant. Inf. Comput. 6, 184 (2006).
• C. Gidney. Halving the Cost of Quantum Addition. Quantum 2, 74 (2018). arXiv:1709.06648
• Nielsen & Chuang.《量子计算与量子信息》第 4 章（量子线路与初等算术）.