Quantum Circuit Synthesis Using an Exact T Library

本文提出了一种精确的 T 合成方法，该方法在 Clifford 等价下对布尔函数进行规范化，并利用预计算的最优实现，显著降低了容错量子电路中的 T 门数量，在加密模块上比传统的与门最小化方法最多提升了 40% 的性能。

要点

想象一下，你正试图用两种类型的砖块来建造一台复杂的机器：标准砖（Clifford 门）和金砖（T 门）。

在容错量子计算的世界里，标准砖便宜、易用，且能耗很低。然而，金砖却极其昂贵。仅仅生产一块金砖，就需要一座庞大而复杂的工厂。如果你想建造一台可靠运行的量子计算机，就必须尽可能少地使用金砖。

旧方法：数错了东西

长期以来，试图设计这些量子电路的工程师们使用了一种捷径。他们查看蓝图，计算"AND"操作（一种特定类型的逻辑步骤）的数量。他们假设每一个"AND"操作都会自动消耗固定数量的金砖。

类比：
想象你在打包行李箱。旧方法假设每打包一件衬衫，都会恰好占用 10 英寸的空间。因此，他们试图通过减少衬衫的数量来节省空间。

但问题在于：有些衬衫轻薄且可折叠，而另一些则厚重且硬挺。有时，如果你将两件特定的衬衫打包在一起，它们实际占用的空间会比预期的更小。旧方法没有考虑到这种“折叠”效应，它只是简单地数衬衫的数量。结果，他们最终得到的行李箱往往比必要的要大得多，因为他们错过了将金砖“折叠”在一起的机会。

新方法：“精确 T"库

这篇论文的作者是 Hanyu Wang 及其团队，他们决定停止猜测。他们不再计算"AND"操作，而是建立了一个金砖库。

1. 库：他们预先计算出了使用确切最小数量的金砖来构建每一种可能的小逻辑函数的绝对最佳、最高效的方法。他们针对最多七个输入的逻辑函数完成了这项工作。这就像拥有一份目录，上面写着：“如果你需要构建这个特定形状，这就是使用金砖进行构建的确切且最廉价的方法。”
2. “折叠”技巧：他们意识到，在量子电路中，有时可以“抵消”金砖，或者以在纸面上看起来不同但在量子世界中实际相同的方式将它们组合。他们利用一个名为"Clifford 等价性”的数学概念来寻找这些隐藏的捷径。这就像意识到两种看起来不同的衬衫折叠技术，实际上会产生完全相同的紧凑包裹。
3. 自定义映射器：他们不仅使用了这个库，还构建了一个新的“打包器”（一种映射算法）。这个打包器足够智能，能够查看蓝图，找到与其库中匹配的具体形状，并利用“折叠”技巧来节省空间。它避免了旧方法中盲目计算"AND"门的错误。

结果

当他们在标准数学问题和复杂的加密任务（如用于加密的那些任务）上测试这个新系统时：

• 在标准数学基准测试中：他们将所需的金砖数量减少了高达14.3%。
• 在加密模块中：他们将金砖数量减少了高达40%。

为什么这很重要

该论文解释说，通过从“粗略估算”（计算 AND 门）转向“精确计数”（使用库），他们可以构建出效率显著提高的量子电路。

他们还指出，虽然他们的新方法在规划阶段需要多花一点点时间（设计期间的计算机时间增加了约 11%），但回报是巨大的：最终机器使用的昂贵金砖要少得多。由于这些设计通常会在不同的实验中被重复使用多次，因此少量的规划时间换取实际建造成本的大幅降低是值得的。

简而言之：他们不再猜测需要多少昂贵的砖块，而是开始使用精确的、预先计算好的目录来构建更精简、更高效的量子电路。

技术摘要

技术摘要：基于精确 T 库的量子电路综合

问题陈述
在容错量子计算（FTQC）中，非 Clifford 门（特别是 T 门）的执行因魔法态蒸馏和注入的开销而主导了时空成本。虽然 Clifford 门可以通过横截执行以可忽略的开销完成，但 T 门需要昂贵的态制备。因此，最小化 T 门数量对于实际应用至关重要。

现有的综合流程通常将布尔函数映射到 $\{XOR, AND, NOT\}$ 基（XAG），并将 AND 门的数量最小化作为 T 门数量的代理。这种方法依赖于乘法复杂度（MC），它衡量经典非线性。然而，本文指出 MC 是 T 门成本的不准确代理，因为它未能考虑量子电路特有的相位抵消和结构简化（例如，Hadamard 门会阻碍 T 门优化）。因此，传统流程往往产生次优电路，其中错失的结构机会无法通过映射后优化来恢复。

方法论
作者提出了一种直接针对精确 T 门数量进行优化的综合框架，而非使用 MC 作为代理。该方法论包含三个主要组成部分：

1. Clifford 等价规范形式化：
   本文引入了双线性函数在 Clifford 等价下的规范形式。与使用乘法张量表示输入 - 输出耦合的经典 MC 不同，作者利用相位多项式张量。该张量捕获了可逆设置中所有导线（输入和输出）之间的三重奇偶耦合。这一表述揭示了量子操作可以使输入和输出纠缠，产生三阶相互作用，从而允许在分解中使用“捷径”，导致比经典 MC 估计更低的 T 门成本。

2. 精确 T 库综合：
   作者将精确 T 门综合问题表述为约束整数规划问题。

   • 输入： 具有 $n$ 个输入和 $m$ 个输出的双线性函数 $f$，映射到 $N = n+m$ 个量子比特。
   • 约束： 问题寻求 T 候选项（奇偶项）的选择向量 $s$，使得它们的组合相位多项式在模 2 下等于目标函数的相位多项式。
   • 优化： 目标是最小化 $s$ 的基数（即 T 门数量）。
   • 无关条件： 该表述利用“干净辅助”量子比特（初始化为 $|0\rangle$）作为无关条件。这些辅助态上的相位是不可观测的，允许进行零成本的 Clifford 重写（例如，用免费的 S 门替换特定的 T 门组合），以进一步减少 T 门数量。
   • 算法： 一种高效的库综合算法预先计算映射矩阵和零空间基。它使用 CUDA 加速搜索来寻找多达七个变量（$N \le 7$）的函数的精确解，并为更大的输入提供次优解。

3. 定制库映射：
   为了充分利用精确 T 库，作者开发了一个与 XAG 流程集成的定制映射器。

   • 双线性割枚举： 该映射器优先选择能揭示双线性结构（代数规范形式中的 2 次项）的割。它剪枝那些会引入 3 次或更高次单项的割，因为这些单项不受库支持。
   • 成本模型： 映射器不再通过 AND 门数量估算成本，而是查询预先计算的精确 T 库，以获取每个有效割的精确 T 门成本。
   • 动态规划： 映射器在割上执行标准的面向面积的动态规划，但使用精确的 T 门评分来选择实现方案，从而保留底层逻辑网络结构。

主要贡献

• 精确 T 表述： 通过利用相位多项式张量在 Clifford 等价下规范化布尔函数，从最小化 AND 门数量（MC）转向最小化精确 T 门数量。
• 预计算库： 一个包含多达七个变量的双线性函数的 T 最优实现库，该库使用考虑了干净辅助无关条件的整数规划方法综合而成。
• 定制映射器： 一种在割枚举和排序过程中显式保留双线性结构的映射算法，利用精确 T 库指导优化决策。

实验结果
作者在多个基准测试族上评估了他们的方法，包括 EPFL 算术基准、随机 QLUT 预言机、模幂运算（Shor 算法）以及用于 AES 的 GF($2^n$) 乘法器。

• EPFL 基准测试： 与由精确 MC 驱动的先前的 XAG 映射流程相比，所提出的方法在算术基准测试（例如乘法器）上实现了高达 14.3% 的 T 门数量减少。各基准测试的几何平均减少率为 5.3%。
• 加密模块： 当集成到完整的综合流程（包括重综合）中时，该方法将几个加密模块的最佳已知 T 门数量减少了高达 40%。
• 与最先进方法的比较： 该方法优于独立的 T 门优化（如 AlphaTensor 和 FastTODD）以及现有的 QROM 和 SelectSwap 实现，特别是在具有高双线性结构的场景中。
• 运行时开销： 由精确 T 库查找和定制映射引入的额外计算最多占总运行时间的 11.7%，作者指出这是一次性成本，可在量子模块设计的重复使用中摊销。

意义
本文声称，假设将 AND 门统一转换为固定数量的 T 门会导致最优性的不可逆损失。通过在保留 XAG 结构的同时基于精确 T 门成本进行推理，所提出的方法在电路质量上产生了切实的改进。这项工作表明，通过 Clifford 等价规范形式和定制映射器促进的 T 门数量直接优化，可以显著降低容错量子应用的资源开销，从而超越经典非线性代理的局限性。