量子算术电路

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

量子算术是 Shor 算法中模幂运算 $a^x\mathrm{mod}N$ 的实现基础，也是 QRAM 地址译码、数据幅值编码与许多块编码构造的核心子程序。

可逆化：受控写回

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

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

即把 $f(a)$ 按位异或进目标寄存器。这保持了幺正性，且允许 $a$ 处于叠加态——这是量子并行在算术子程序里的具体形态。

线路成本的主导项通常是 Toffoli 门数（其次是 CNOT 数与深度）。Toffoli 还要继续分解成硬件原生门（见基本门分解与多控门分解），其 $T$ 门开销直接牵动容错实现中魔术态蒸馏的成本。

进位加法器

行波进位加法器（ripple-carry adder）直接翻译经典逐位相加。Vedral–Barenco–Ekert 给出最早的系统构造；最常用的精简版本是 Cuccaro 等人的 MAJ–UMA 结构：

• MAJ（多数投票）门从低位到高位依次计算进位 $c_{i+1}=\mathrm{maj}(a_i,b_i,c_i)$，每个 MAJ 由 1 个 Toffoli 与 2 个 CNOT 组成；
• 最高位的和直接读出后，用 UMA（MAJ 的逆）从高位到低位逐位恢复，同时产出各位的和。

对 $n$ 比特操作数，MAJ 前向链与 UMA 恢复链合计约 $2n$ 个 Toffoli、约 $4n$ 个 CNOT，深度 $O(n)$，且只需一个置 $|0⟩$ 的进位辅助比特（相比早期需要线性数目辅助比特的构造已大幅精简）。

QFT 域加法器

Draper 加法器走另一条路：先对目标寄存器做量子傅里叶变换，在傅里叶域中加法没有进位传播，只剩受控相位：加上 $b$ 时，$b$ 的第 $j$ 位对（已变换的）第 $i\le j$ 个比特施加角度 $2\pi b_j/2^{j-i+1}$ 的受控旋转，全部旋转完成后再逆变换回计算基（这里采用从最高位起编号的约定）。$n$ 比特加法共需 $\frac{n(n+1)}{2}$ 个两比特受控相位门。

旋转角都是 $2\pi /2^k$ 型，有限精度下必须截断近似。这是 QFT 加法器的固有 trade-off：门数 $O(n^2)$ 多于进位加法器的 $O(n)$，但每个门都是局域受控相位——不需要 Toffoli、不需要辅助比特，且模算术与受控版本的组合格外方便（见下文 Beauregard 方案）。

比较器与减法

二进制补码下减法与加法同构：计算 $a-b$ 并观察最高借位即可判定 $a\stackrel{?}{\ge }b$。可逆比较器通常实现为”做减法、把借位以受控/相位方式写回、再减回去还原”，或等价地用加法器加 $\bar{b}+1$（补码）读出进位标志。注意：比较结果只能以受控操作或相位写回，不能对叠加态做破坏性测量。

模算术与 Shor 的模幂电路

模加 $\mathrm{ADD}\mathrm{mod}N$：在普通加法器外套”减 $N$、按比较结果条件加回 $N$“即可。

模乘（受控版本）把乘数按二进制展开 $a={\sum }_j{a}_j{2}^j$ 拆开：

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

即 $n$ 次受控模加（加数为经典预计算的常数 $2^{j}x\mathrm{mod}N$），配合移位式模加（“倍乘 $2x\mathrm{mod}N$“）串联。

模幂 $|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 基于 QFT 加法器的方案把整套 Shor 电路压到 $2n+3$ 个量子比特：模乘复用单个 $n$ 比特累加寄存器，模加只需一个辅助比特完成条件减 $N$。更现代的优化（如 Gidney 把进位链中的 Toffoli 换成相对相位版本）可把 $T$ 开销再减半。

参考文献

• V. Vedral, A. Barenco, A. Ekert. Quantum Networks for Elementary Arithmetic Operations. Phys. Rev. A 54, 147 (1996). arXiv:quant-ph/9511018
• T. G. Draper. Addition on a Quantum Computer. (2000). arXiv:quant-ph/0008033
• S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton. A New Quantum Ripple-Carry Addition Circuit. (2004). arXiv:quant-ph/0410184
• S. Beauregard. Circuit for Shor’s Algorithm Using 2n+3 Qubits. Quant. Inf. Comput. 3, 175 (2003). arXiv:quant-ph/0205095
• C. Gidney. Halving the Cost of Quantum Addition. Quantum 2, 74 (2018).
• Nielsen & Chuang.《量子计算与量子信息》第 4 章（量子线路）.