Optimal Toffoli-Depth Multi-Controlled Toffoli Decomposition in 2D Qubit Layout

技术摘要：二维量子比特布局中最优 Toffoli 深度多控制 Toffoli 分解

问题陈述
多控制 Toffoli (MCT) 门是量子算术、算谕构建和密码分析中的基本原语。虽然近期的理论进展已经确立了在理想的全连接（all-to-all）量子比特连接下，MCT 门的优化 Toffoli 深度分解方案，但在近期的量子硬件上实现这些方案仍然具有挑战性。当代的量子处理器（例如超导量子比特、离子阱）主要具有受限的二维 (2D) 量子比特连接性。通用的量子映射器往往无法利用 MCT 分解中固有的特定重复交互模式，从而导致显著的路由开销（SWAP 门）和深度膨胀。本文旨在解决逻辑最优的 MCT 分解与受限 2D 连接约束下的物理实现之间的差距。

方法论
作者提出了一种架构感知映射框架，用于连接逻辑 MCT 分解与物理 2D 布局。该方法分为三个阶段进行：

1. 无限网格上的无 SWAP 映射： 本文首先分析了在无限 2D 拓扑结构（三角形、正方形网格、带对角线的正方形、H-tree）上，最先进的 MCT 分解（特别是来自文献 [6] 的分解）。通过将量子比特放置与特定 Toffoli 分解的交互图进行结构化对齐（例如，使用三角形晶格处理 T-深度为 3 的分解，或使用正方形网格处理 T-深度为 1 的分解），作者证明了只要拓扑规模足够大，就可以在不产生任何 SWAP 开销的情况下实现 MCT 门。

2. 基于基元（Motif）的填充框架： 对于量子比特数量有限的受限拓扑结构，作者引入了一种基于基元的填充方法。他们将 MCT 分解的交互层建模为图基元（具体为由基础 Toffoli 门衍生的 $P_3$ 路径和 $C_4$ 循环）。随后，将问题转化为将这些基元顶点不相交地嵌入到硬件图中。

   • 作者根据拓扑结构的路由复杂度 ($D_\pi(T)$) 和最大顶点不相交基元嵌入数 ($P_M(T)$)，推导出了产生的深度开销 ($D_M(T)$) 的上界。
   • 针对正方形网格和超立方体建立了解析界限。例如，在正方形网格上，$P_3$ 基元填充受限于 $\lfloor |V|/3 \rfloor$，而 $C_4$ 基元填充受限于 $\lfloor p/2 \rfloor \cdot \lfloor q/2 \rfloor$。

3. 启发式评估与验证： 为了验证理论界限，作者采用了路由感知的放置启发式算法。他们利用基于冲突图上的最小独立集 (MIS) 公式构成的贪心策略，将基元填充到各种硬件拓扑（包括 IBM 的 Heavy-Hex 和 Tokyo Q-20 布局）中。这些启发式算法与穷举的分支定界解以及标准布局工具（如 IBM 的 SABRE）进行了对比。

核心贡献

• 架构感知分解： 本文提供了将最优 Toffoli 深度 MCT 分解映射到各种 2D 布局（三角形、正方形、H-tree）的显式映射方案，在拓扑规模允许的情况下，能够保持逻辑并行性而不增加额外的深度开销。
• 深度开销界限： 作者推导出了将 MCT 门映射到受限拓扑时所产生的深度开销的显式数学界限。这些界限量化了量子比特预算与路由成本之间的权衡，表明对于足够大的拓扑结构，开销可以被最小化或消除。
• 基于基元的填充策略： 引入了一个新颖的框架，其中分解层被表示为交互基元。这使得能够表征支持特定量子比特资源所需的最小规模拓扑，并推导出在紧凑量子比特预算下的深度界限。
• 经验验证： 研究通过在多种硬件拓扑上嵌入不同基元，对提出的填充启发式算法进行了经验性评估。结果表明，所提出的填充启发式算法始终符合推导出的理论上界，并且在深度开销方面通常优于标准的启发式映射器（如 SABRE）。

结果

• 资源估算： 本文提供了不同 2D 布局下 $n$-MCT 门的综合资源估算（T-计数、T-深度、量子比特数）。例如，在利用 Jaques 等人 [3] 的 T-深度为 1 的分解方案的无限正方形网格上，T-深度保持为 $\lceil \log_2 n \rceil$，T-计数为 $4(n-1)$，需要 $3n-2$ 个量子比特。
• 开销分析： 研究表明，在受限拓扑结构下的深度开销是路由数和基元填充密度的函数。实验结果表明，测得的深度开销始终低于第四节中推导出的理论上界。
• 启发式性能： 所提出的基于 MIS 的填充启发式算法（特别是 Min-degree MIS 和 Min-degree MIS + 局部搜索）在各种拓扑结构上实现了接近最优的填充率（通常与最优解的匹配率 >95%），显著优于 Max-degree removal 启发式算法。
• 与 SABRE 的比较： 与 IBM 的 SABRE 布局和 Dense 布局相比，所提出的基于基元的填充策略在处理较大数量的控制位时，表现出更低的 SWAP 深度开销。

意义
本文声称推进了架构受限的 Toffoli 和 MCT 分解的最前沿技术。通过显式利用 MCT 分解的结构对称性和交互模式，所提出的方法为通用的映射启发式算法提供了一个更具预测性且更高效的替代方案。这项工作有助于实现为物理可实现的硬件模型优化量子电路的更广泛目标，为界定资源成本和提供布局感知合成的实践框架提供了理论基础。作者指出，虽然目前的研究重点是 2D 布局，但该方法论也为未来的可扩展架构（如循环蝴蝶网络）提供了见解，尽管这些架构目前仍超出了物理硬件的能力范围。