多控门分解

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

Barenco 等人 1995 年的论文给出了整套基础构造；此后 Margolus（1989/1990）的相对相位门与 Gidney（2018）的测量辅助技巧把常数因子压到实用水平。本词条逐个推导这些构造并核对成本。

为什么不能硬造：控制信息是高阶关联

$C^n(X)$ 的”控制”是 $n$ 个比特的与（AND）——一个 $n$ 阶经典非线性函数。幺正线路中信息只能通过两比特纠缠逐步累积，且每一步必须可逆。因此多控门分解的本质是：用可逆的两比特交互把 AND 逐级”算出来、用掉、擦回去”。所有构造都是这句话的不同实例化，区别只在于把中间的 AND 存在哪里（辅助比特链、相对相位里、还是测量后验里）。

二控门：V 门技巧的完整验证

受控-受控-$U$（$U$ 任意单比特幺正）的标准分解取平方根门 $V$（$V^2=U$，由 Euler 分解恒可写出），线路为 5 个两比特门：

$C^2(U):{\mathrm{CNOT}}_{1\to 2}\to C_2(V^{†})\to {\mathrm{CNOT}}_{1\to 2}\to C_2(V)\to C_1(V),$

即：CNOT（$c_1\to c_2$）、受控 $V^{†}$（控制 $c_2$）、CNOT（$c_1\to c_2$）、受控 $V$（控制 $c_2$）、受控 $V$（控制 $c_1$），目标比特依次经历这些门。

正确性验证（四种控制取值逐一核算，目标上累计作用 = 各门作用之积）：

$(c_1,c_2)$	中间线 $c_1\oplus c_2$	目标累计作用	化简
$(0,0)$	$0$	$I$	$I$ ✓
$(0,1)$	$1$	$V^{†}\cdot V$	$I$ ✓
$(1,0)$	$1$	$V^{†}\cdot V$	$I$ ✓
$(1,1)$	$0$	$V\cdot V$	$U$ ✓

关键在第二根受控线接的是 $c_1\oplus c_2$ 而非 $c_2$：恰好只在 $(1,0)$、$(0,1)$ 这两个”半激活”取值下放行一个 $V^{†}$，随后被 $c_1$ 或 $c_2$ 上的 $V$ 抵消；而 $(1,1)$ 时中间线为 0，$V^{†}$ 被跳过，两个 $V$ 相乘恰为 $U$。$■$（这就是 Nielsen & Chuang §4.3 的经典构造。）

取 $U=X$、$V=(1-i)(I+iX)/2$（平方根 of NOT）即得 5 个两比特门的 Toffoli。

n 控门：三条路线

（1）v-chain：辅助比特链

取 $n-2$ 个辅助比特组成链，逐级做 Toffoli 把”控制全为 1”与出来：

$t_1=c_1\wedge c_2,t_2=t_1\wedge c_3,\dots ,t_{n-2}=c_1\wedge \cdots \wedge c_{n-1},$

用 $t_{n-2}$ 控制最后一个 $C(X)$ 或 $C(U)$（配合 $c_n$），随后逆向重放整条链把辅助比特恢复为 $|0⟩$。

正确性（归纳）：第 $j$ 级 Toffoli 把 $t_j$ 翻转当且仅当 $t_{j-1}=c_{j+1}=1$，归纳得 $t_j=c_1\wedge \cdots \wedge c_{j+1}$；逆链是正链的逆线路，把中间量逐一擦除——Bennett 清理的直接应用。

成本：正链 $n-2$ 个 Toffoli、逆链 $n-2$ 个，外加收尾 1 个，合计 $\Theta (n)$ 个 Toffoli（约 $2n$），深度 $O(n)$。辅助比特用后还原、可复用。Cuccaro 加法器的 MAJ 门串与 v-chain 同构——进位链本来就是一条 AND 链。

（2）无辅助比特的 O(n²) 构造

完全不借助辅助比特时，Barenco 等证明 $C^n(U)$ 仍可用 $O(n^2)$ 个基本门（单比特门 + CNOT）实现（Corollary 7.6，对任意 $n$；$n=2$ 即上面的 5 门分解）。构造是逐控制递归：借一个”工作”控制比特承载中间的半激活信息，$C^n$ 型门每剥掉一个控制付出 $\Theta (n)$ 个两比特门的代价，层层递归到二控门为止，总计 $O(n^2)$（原文精确计数约 $48n^2+O(n)$ 个基本门）。

另一条教学路线是 Gray 码：沿 Gray 码路径逐门翻转目标旁的多重受控相位，走到路径终点时恰只在全 1 控制取值留下净作用 $U$；门数随 $n$ 指数增长，实用价值有限，但清楚展示了”控制信息可以编码在相位里”这一思想。

（3）门数与辅助比特的折衷

辅助比特越多门数越省：Barenco 等刻画了两个端点——无辅助比特的 $\Theta (n^2)$ 与恰有一个额外可用比特时的 $\Theta (n)$，中间取值可由混合构造取得。工程默认取 v-chain（辅助换线性门数），辅助比特稀缺时退到折衷点。

相对相位与测量辅助：常数因子的战场

算术线路里的大多数 Toffoli 只要求计算部分正确：中间结果允许差一个不依赖数据的相对相位（后面会被逆运算乘回去）。这一宽松条件带来两档优化：

Margolus 门（相对相位 Toffoli）

Margolus 门 $M$ 与 Toffoli 只差一个非激活基矢上的相对相位——等价表示如 $\mathrm{diag}(1,1,1,1,1,-1,X)$：仅在 $|101⟩$ 上差一个 $-1$，控制全 1 时如实交换 $|110⟩\leftrightarrow |111⟩$。实现只需 3 个 CNOT 与若干单比特旋转（$R_y(\pm \pi /4)$、相位门等），比精确 Toffoli 的 5 个两比特门便宜近半。正逆成对使用时相对相位自动抵消，净作用精确等于 Toffoli。

Gidney 的临时逻辑与（测量辅助）

Gidney 的临时逻辑与（temporary logical AND）把”辅助比特必须擦回去”改成”测量擦除”：

1. 辅助比特制备于 $|0⟩$，经少量受控门与控制比特耦合（与相对相位结构同族，制备成本 4 个 $T$）；
2. 用它控制一次 $C(X)$ 完成计算；
3. 测量辅助比特到 $X$ 基，按测量结果（0/1）对控制比特补一个 $S$ 或 $S^{†}$ 修正。

正确性论证：测量把辅助比特与数据解纠缠，后验相位修正恰好补偿测量带来的相位分支——等价于逆运算的效果，但用测量代替了逆线路（测量擦除本身不再花 $T$ 门）。$T$ 账本：制备 4 个 $T$、擦除 0 个，净 4 个 $T$/个 AND；由于一个 AND 可替代一对 Toffoli（先 AND、用完再擦），折算到每个被替代的 Toffoli 约 2 个 $T$（相对相位 Toffoli 则固定 4 个 $T$）。Gidney 用它把加法器的 $T$ 总成本减半，是现代算术线路设计的标配。

在算术与算法中的位置

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

因此多控门分解的常数因子（5 个两比特门、7 个 $T$、相对相位 4 个 $T$、测量版摊销约 2 个 $T$）会被整个算法放大数千倍，是资源估计中最敏感的参数之一。

关联词条

• 上游：基本门分解、量子线路
• 下游：量子算术电路、Shor 算法、量子 oracle

参考文献

• T. Toffoli. Reversible Computing. MIT LCS Technical Memo 151 (1980). —— Toffoli 门之源。
• E. Fredkin, T. Toffoli. Conservative Logic. Int. J. Theor. Phys. 21, 219 (1982). —— Fredkin 门（$C^1(\mathrm{SWAP})$）。
• D. P. DiVincenzo. Two-Bit Gates Are Universal for Quantum Computation. Phys. Rev. A 51, 1015 (1995). arXiv:cond-mat/9407022
• 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²) 构造与门数-辅助比特折衷）。
• R. Margolus. Parallel Quantum Computation. 收于 Complexity, Entropy, and the Physics of Information（ed. W. H. Zurek; Santa Fe Institute Studies in the Sciences of Complexity VIII）, Addison-Wesley, 1990, p. 273. —— 相对相位 Toffoli。
• V. Vedral, A. Barenco, A. Ekert. Quantum Networks for Elementary Arithmetic Operations. Phys. Rev. A 54, 147 (1996). arXiv:quant-ph/9511018 —— 模乘中的受控门网络。
• C. Gidney. Halving the Cost of Quantum Addition. Quantum 2, 74 (2018). arXiv:1709.06648 —— 临时逻辑与与测量辅助。
• Nielsen & Chuang.《量子计算与量子信息》§4.3（受控运算与二控门构造）及第 4 章习题（Gray 码与辅助比特链）.