多控门分解

多控门 $C^n(U)$ 指由 $n$ 个控制比特调制目标上幺正 $U$ 的门：当且仅当全部控制比特处于 $|1⟩$ 时执行 $U$。$n=1$ 是普通受控门（CNOT 即 $C^1(X)$）；$n=2$ 的 $C^2(X)$ 是 Toffoli 门（CCNOT），$C^2(\mathrm{SWAP})$ 是 Fredkin 门。多控门是量子算术电路（进位链、模乘的受控加）与 Grover 型 oracle（标记解的相位翻转）的主力原语；而硬件只提供单比特门与一个两比特门，因此任何多控门都必须系统性地分解下去。Barenco 等人 1995 年的论文给出了整套基础构造。

二控门：V 门技巧

受控-受控-$U$ 的标准分解使用平方根门 $V$（满足 $V^2=U$）：目标比特依次经历三个受控 $V/V^{†}$ 门——受控于第二控制比特的 $V$、受控于”两控制比特异或值”的 $V^{†}$、受控于第一控制比特的 $V$——中间用两个 CNOT 在控制比特间来回传递异或信息。仅当两个控制比特同为 $1$ 时，目标净经历 $V^2=U$；其余三种控制取值下 $V$ 与 $V^{†}$ 恰好相消，目标不受影响（Nielsen & Chuang §4.3 的经典构造，共 5 个两比特门）。

$C^2(U):5\text{ 个两比特门}=2\mathrm{CNOT}+3\text{受控 }V/V^{†},V^2=U.$

n 控门：三条路线

（1）v-chain（辅助比特链）。取 $n-2$ 个辅助比特组成链，逐级做 Toffoli 把”控制比特全为 1”与出来：$t_1=c_1\wedge c_2$，$t_2=t_1\wedge c_3$，……直到控制最后一个目标门；随后逆向重放恢复辅助比特。整趟来回是 $\Theta (n)$ 个 Toffoli（约 $2n$ 个），辅助比特用后还原、可复用。这是工程上最常用的构造——算术线路里的进位链本质上就是 v-chain。

（2）无辅助比特的 O(n²) 构造。Barenco 等人证明，完全不借助辅助比特时 $C^n(U)$ 也可以用 $O(n^2)$ 个基本门（单比特门 + CNOT）实现（$n\ge 4$；$n=2$ 即上面的 5 门分解）。另一条教学路线是 Gray 码：沿 Gray 码路径依次翻转，门数随 $n$ 指数增长，实用价值有限，但清楚展示了”控制信息可以编码在相位里”这一思想。

（3）门数与辅助比特的折衷。辅助比特越多门数越省：从无辅助的 $O(n^2)$ 到 $n-2$ 个辅助的 $\Theta (n)$ 之间可以连续折衷；递归二分（把 $C^n$ 拆成两个 $C^{\lceil n/2\rceil }$ 的组合）是常用的中间方案。

相对相位 Toffoli

算术线路里的大多数 Toffoli 只要求计算部分正确，中间允许出现只差一个相位的”脏”结果。相对相位 Toffoli（Margolus 门一系）利用这一宽松条件，用 3 个两比特门加单比特门即可实现，比精确 Toffoli（至少 6 个两比特门）便宜近半。Gidney 进一步指出：把进位加法器里的 Toffoli 全部换成相对相位版本，整个量子加法的 $T$ 成本可减半——这类优化是现代算术线路设计的标配。

在算术与算法中的位置

• Cuccaro 加法器的 MAJ 门串与 v-chain 同构（见量子算术电路）；
• 模乘中每个受控模加展开成受控 Toffoli 网络，是 Shor 算法物理成本估计里最大的一块；
• Grover oracle 用 $C^n$ 相位门标记解，配合相位反冲把多比特判定折叠为单比特相位。

因此多控门分解的常数因子会被整个算法放大，是资源估计中最敏感的参数之一。

参考文献

• A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, H. Weinfurter. Elementary Gates for Quantum Computation. Phys. Rev. A 52, 3457 (1995). arXiv:quant-ph/9503016 —— 多控门分解的原始文献（二控 V 门技巧、无辅助 O(n²) 构造与门数-辅助比特折衷）。
• Nielsen & Chuang.《量子计算与量子信息》§4.3（受控运算与二控门构造）及第 4 章习题（Gray 码与辅助比特链）.
• C. Gidney. Halving the Cost of Quantum Addition. Quantum 2, 74 (2018).