Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

技术摘要：基于三进制 Clifford+P9 门的高效多控制 Toffoli 门合成

问题陈述
多控制 Toffoli (MCT) 门是量子电路设计中的基础原语，对于可逆算术、算子构建和振幅放大至 آن 至关重要。然而，随着控制量子比特数量的增加，其分解过程变得愈发耗费资源。在容错架构中，非 Clifford 操作（如 Toffoli 门）需要昂贵的资源态准备与注入。传统的仅限二进制的方法通常将 MCT 分解为较小的 Toffoli 门，进而分解为 Clifford+T 集合，这会在 T 门成本、辅助量子比特需求以及电路深度之间产生权衡。虽然最近的基于条件清洁辅助比特（conditionally clean ancillae）的二进制构造实现了对数深度，但它们依赖于测量辅助的去计算（uncomputation）和经典前馈，这引入了与测量延迟和相干调度相关的开销。此外，虽然存在近似合成方法，但它们无法提供精确构造。本文旨在解决对一种精确且资源高效的 MCT 合成方案的需求，该方案应能在容错设置下避免测量开销，并优化深度与辅助资源需求。

方法论
作者提出了一种利用三进制 Clifford+P9 框架对具有二进制子空间输入和输出的 MCT 门进行精确分解的方法。该方法利用非计算三进制能级 $|2\rangle$ 作为临时工作空间，同时将逻辑状态编码在二进制子空间 $H_{bin} = \text{span}\{|0\rangle, |1\rangle\}$ 中。

核心方法论涉及一个分层树状分解：

1. 原语： 该构造利用三种基本操作：三进制 SUM 门（Clifford）、状态选择控制增量门 $C_2(\text{INC})$（非 Clifford）以及严格控制的二进制目标翻转门 $C_2(X_{01})$（非 Clifford）。资源成本通过实现这些非 Clifford 门所需的逻辑 P9 注入数量来衡量。
2. 树状结构： 控制位不是通过顺序递归扩展进行评估的，而是通过一个平衡树进行评估。
   • 叶节点块（Leaf Blocks）： 并行检查三组二进制控制位。一个叶节点块使用一个 SUM 门和一个 $C_2(\text{INC})$，当且仅当三个输入均为 $|1\rangle$ 时，临时将一个控制三进制比特标记为状态 $|2\rangle$。
   • 合并块（Merge Blocks）： 内部节点结合两个子树的结果以及一个额外的控制位。这使用了一个干净的辅助三进制比特（初始化为 $|0\rangle$）和三个 $C_2(\text{INC})$ 门。如果两个子树的标记均为 $|2\rangle$ 且中间的控制位为 $|1\rangle$，则辅助比特达到 $|2\rangle$，进而触发中间控制位达到 $|2\rangle$。
   • 根操作（Root Operation）： 一旦根标记达到 $|2\rangle$（表示所有控制位均处于激活状态），单个严格翻转门 $C_2(X_{01})$ 将翻转目标量子比特。
   • 去计算（Uncomputation）： 通过逆转电路将所有临时标记和辅助三进制比特恢复为 $|0\rangle$。

主要贡献与结果
本文针对平衡控制宽度 $n = 2^h - 1$ 提供了精确的资源分析，并将该构造扩展到了任意宽度。

• 平衡宽度下的资源效率 ($n = 2^h - 1$)：

  • P9 计数： 该构造需要 $6n + 3$ 个逻辑 P9 注入。这与 Bocharov 等人 [16] 推导出的最先进的递归扩展无辅助基准（Baseline B）的精确 P9 计数一致。
  • 辅助三进制比特： 该构造需要 $\frac{n-3}{4}$ 个干净的辅助三进制比特。这在渐近意义上仅为 Baseline B 所需辅助比特数（$n-2$）的四分之一。
  • 电路深度： 通过并行评估独立的子树，深度从线性 $\Theta(n)$ 降低到了对数级 $\Theta(\log n)$。

• 权衡前沿（Trade-off Frontier）：
  本文确定了辅助工作空间与非 Clifford 成本之间的构造性权衡。通过复用辅助三进制比特（减少同时活跃的辅助比特数 $A$），P9 计数会增加。具体而言，使用仅一个复用辅助比特（$A=1$）会导致 P9 计数为 $9n - 18$ 且深度为 $\Theta(n)$，而保留 $I(n)$ 个辅助比特则能使 P9 计数最小化为 $6n+3$。

• 任意控制宽度：
  对于任意 $n$，作者通过选择一个宽度为 $m = 2^h - 1 \leq n$ 的平衡核心，并顺序附加剩余的 $n-m$ 个控制位来扩展该构造。这保持了 $6n+3$ 的 P9 计数，但会导致深度变为 $O(\log m + n - m)$。在最坏情况下（例如 $n = 2^{h+1}-2$），深度随 $n$ 线性缩放。

意义与主张
本文声称，所提出的分解方案为在容错范式下设计和编译更高效的量子算法提供了实用的构建模块。其主要意义在于：

1. 深度降低： 在不依赖测量或前馈的情况下，将递归三进制基准的线性深度降低为平衡输入的对数深度。
2. 辅助减少： 在保持相同的非 Clifford (P9) 成本的同时，将干净辅助三进制比特的渐近需求降低到现有最佳精确递归基准的四分之一。
3. 精确合成： 提供了一种将二进制信息嵌入多级系统中的精确构造策略，这与近似合成领域截然不同。

作者指出，虽然平衡情况提供了对数深度，但任意宽度的最坏情况深度仍为线性。他们建议未来的工作可以探索更详细的容错成本模型（包括魔态蒸馏和路由）、替代的中间三进制设置，以及将其集成到更大的可逆子程序（如算术电路）中。