面向高效量子综合的因式分解布尔表示

Factorized Boolean representations for efficient quantum synthesis

arXiv: 2608.27430v1

论文信息

标题: Factorized Boolean representations for efficient quantum synthesis

作者: Mehul Shah, Robert Fiszer, Marek Perkowski

发布日期: 2026-08-27

arXiv ID: 2608.27430v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：论文要解决布尔表达式最小化没有捕捉量子实现成本关键结构的问题，尤其是宽多控门带来的超线性成本。
  • 核心方法：在逻辑最小化之后、可逆映射之前插入因子化层，提取乘积项间的包含关系与互补极性关系，将共享因子计算到辅助量子位，降低门宽。
  • 关键结果：在 64 个函数中，56 个量子成本下降、8 个不变、0 个上升；中位量子成本下降 42.7%，T 计数中位下降 28.6%（图 2a,b）。
  • 主要局限：表示层优势在导出为可执行电路并作反计算后大约减半；随机宽函数几乎没有可提取结构；组合生成电路中按小单元因子化仅得到约 6.7% 的 T 计数下降。
  • 适合读者：从事量子编译、可逆逻辑综合、容错量子计算资源估计的研究者，以及量子算法工程化团队。

论文背景和研究动机

量子算法在容错硬件上运行前，需要把布尔描述转换成可逆电路。容错计算的主要成本来自非 Clifford 操作，尤其是 T 门，每个 T 门消耗一个蒸馏魔法态。论文引用 Gidney 和 Ekerå的估计：分解一个 2048 位 RSA 模数需要约 26 亿个 Toffoli 门，因此算术原语的资源成本直接影响可执行性。

传统合成流程通常先对布尔表达式进行最小化，再将其映射为可逆电路。最小化通常以减少乘积项数和字面量为目标，假设最小化形式最优。但论文指出，最小化减少的是表达式大小，而量子实现成本由最宽门的控制数主导。根据 Maslov 成本模型，一个 nn 控制 Toffoli 门的成本是 2n+1−32^{n+1}-3，随 nn 超线性增长。因此，少数几个宽门会主导总成本，而减少项数或字面量无法降低这些宽门的宽度。

论文认为，最小化后的表达式仍保留代数结构，这些结构来自乘积项之间的包含关系和互补极性关系。传统方法在电路级才进行优化，没有在表示层提取这类结构。该工作正是要在逻辑最小化和可逆映射之间增加一个表示层的优化步骤。

核心方法和技术细节

因子化框架提取两类关系。第一类是包含关系：若一个乘积项的所有字面量都出现在另一个项中，则较小项可成为公共因子。例如，利用恒等式 X⊕XY=X⋅Y′X \oplus XY = X \cdot Y'，可得到 b′d⊕a′b′cd=b′d(a′c)′b'd \oplus a'b'cd = b'd(a'c)'。这里共享因子 b′db'd 被计算一次，残差 a′ca'c 计算到辅助线上，由其反相控制目标门。

第二类是互补极性关系：两个项共享一个因子，但在一个或多个字面量极性上不同。例如，abcde′abcde' 与 a′be′fa'be'f 共享 be′be'，但 aa 极性不同，可合并为 be′(acd⊕a′f)be'(acd \oplus a'f)。一个五控制门和一个四控制门被替换为三控制、二控制和三控制门。

具体实现分两个阶段。第一阶段处理包含关系，在每一步计算所有候选对的量子成本差异，选择减少量最大且严格为正的合并，直到没有正收益。第二阶段处理互补极性关系，把每个乘积项作为图的顶点，合法共享因子作为边的权重，按权重降序进行最大权重匹配，确保每个项最多参与一次因子化。

辅助量子位用于保存共享因子，并作为额外控制参与后续门。论文使用基于测量的反计算将辅助线恢复到 ∣0⟩|0\rangle，不需要非 Clifford 资源。在 64 个函数中，同时活跃的辅助量子位最多为 2 个，与函数规模无关。论文在 Methods 中给出推导：包含合并使 T 计数减少 4(∣L∣−1)4(|L|-1)，极性合并使 T 计数减少 4∣L∣4|L|，其中 ∣L∣|L| 是共享因子字面量数。因此，在上述成本模型下，任何包含或极性合并都不会增加 T 计数。

创新点和贡献

该工作提出表示层优化，区别于传统的逻辑最小化和电路级优化。它的关键观察是，门数不是决定成本的核心量，最宽门的控制数才是。因子化用少量宽门换取更多窄门，虽然门数增加，但总成本下降。

论文证明了该变换在表示层具有单调性：不会增加量子成本或 T 计数。这来自构造本身，而不是经验拟合。文中还展示了因子化与 ZX 演算优化器的互补关系：两者作用在不同层面，组合使用时能得到比单独使用更低的 T 计数。此外，因子化还减少了执行电路所需的量子位数量，这是电路级优化器通常不会改变的量。

论文还将因子化扩展到组合生成的模幂电路。它通过按固定单元进行因子化，避免了真值表规模随变量数指数增长的问题。不同模数宽度下，不同单元数量保持稳定，因此可按单元复用因子化结果。作者推测，如果跨单元边界进行因子化，可能暴露更多结构，但代价是随块宽度指数增长的转换成本，论文未尝试这一方向。

实验结果分析

在 64 个单输出布尔函数上，因子化使 56 个函数量子成本下降，8 个不变，没有任何函数增加；中位量子成本下降 42.7%，T 计数中位下降 28.6%（图 2a,b）。下降幅度与结构有关：结构化基准中位量子成本下降 49.7%，算法 oracles 下降 61.9%，随机生成的 100 变量函数仅下降 32.9%（图 2c）。随机宽函数中几乎没有包含关系，因为需要大量共享字面量极性一致。

论文观察到，门数在 51 个函数中增加，而最宽门在 38 个函数中下降，没有任何函数的最宽门上升；整个套件中最宽门从 86 控制降到 48（图 2d）。这表明减少来自门宽下降，而不是门数消除。

在导出到可执行电路后，表示层优势部分被反计算抵消。在 34 个完成比较的基准中，因子化单独将 T 计数中位降低 16.7%，而表示层模型下为 25%。但因子化改善了电路级优化器的最终结果：PyZX 应用于常规表示时 T 计数中位降低 42.3%，应用于因子化表示时达到 53.4%；在 34 个基准中，24 个因子化后优化结果更低，5 个常规表示更低，5 个持平，双尾符号检验得到 p=0.0005p=0.0005（论文图 3 相关段落）。在七组最大完成比较中，每组的因子化后优化 T 计数都低于常规优化后 T 计数；量子位中位下降 32.2%，优化器加速 1.9 至 8.4 倍（图 3a,c,d）。

对于算法 oracles，13 个实例的量子成本中位降低 61.9%，T 计数中位降低 38.5%。其中四个非退化模幂位中位量子成本降低 73.2%，T 计数降低 37.9%（表 1）。在组合生成的模幂电路中，按单元因子化只带来约 6.7% 的 T 计数降低。原因在于 541 个不同单元中，391 个是二项单元，只有 129 个是三项单元；能够被因子化的几乎都是三项单元（图 4c）。作者指出，这不是变换变弱，而是被应用在太小的块上。

实践建议

对于量子编译工具链，一个可操作的策略是在逻辑综合之后、可逆映射之前插入因子化预处理。它不改动上游最小化器，也不替代下游电路优化，而是暴露更多可被优化器利用的结构。在本次评测中，该组合方案比单独使用 ZX 优化器获得更低 T 计数，同时还降低量子位需求。

应优先在结构化或算术函数上应用因子化，例如模幂、加法器和多数函数。对于高度随机的布尔函数，预期收益较小，可以先用轻量级检测判断乘积项之间是否存在包含或共享因子关系后再决定是否应用。辅助量子位的测量反计算策略在论文构建中不需要非 Clifford 资源，但在具体硬件上仍需验证其与表面码调度、测量延迟和反馈控制的兼容性。

对于大规模模块化电路，可采用论文中的单元级因子化方法：先识别固定单元库存，对每个不同单元进行一次因子化，再按出现次数加权得到整电路资源估计。这样可以在不枚举整个真值表的情况下获得与宽度无关的资源减少估计。需要注意的是，论文中的表示层优势在完整可执行电路中约减半，实际部署前应在完整的 Clifford+T 分解流程中重新评估收益。