⚛️ quantum physics

Heuristic and Optimal Synthesis of CNOT and Clifford Circuits

本文介绍了用于 CNOT 和 Clifford 电路启发式与最优合成的三类算法，这些算法旨在最小化门数量或电路深度，展示了优于现有方法的性能，并提供了开源实现。

原作者： Mark Webster, Stergios Koutsioumpas, Dan E Browne

发布于 2026-08-17

📖 1 分钟阅读🧠 深度阅读

原作者： Mark Webster, Stergios Koutsioumpas, Dan E Browne

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图用乐高积木搭建一台复杂的机器，但有一个转折：这些积木是隐形的，而说明书是用纯数学语言编写的。这就是量子计算的世界。在这个领域，科学家们不仅仅是在建造静态的结构，他们还在构建“电路”，通过操纵现实本身的织物来解决常规计算机无法处理的难题。为了让这些电路发挥作用，他们需要执行特定的动作，比如拨动开关或交换两个部件。最常见的动作被称为“CNOT”门（可以将其想象为一个主开关，只有当另一个部件处于特定状态时，才会翻转其中一个部件）和“Clifford”门（这是一组稍微复杂一点的动作，包括上述主开关以及一些特殊的旋转）。

为什么这很重要？因为这些电路是“量子纠错”的支柱。就像嘈ino的无线电信号需要解码器来从静电噪声中理出头绪一样，量子计算机非常脆弱，极易出错。为了修复这些错误并运行有用的算法，我们需要尽可能高效地构建这些电路。问题在于，排列同一组动作的方法有成千上万种。有些排列就像一团乱麻——冗长、缓慢且容易断裂；而另一些则像一条流畅的直线——短小、快速且可靠。目标是找到完成任务的最短、最高效的路径，因为在量子世界中，每多走一步，出错导致整个计算失败的概率就会增加。

现在，伦敦大学学院的一个研究团队决定用一套全新的工具来应对这团乱麻般的乐高积木。他们不仅想找到一种构建电路的方法，还想找到一种“最好”的方法，或者至少是一种比目前大家使用的都要好得多的方法。他们开发了三种不同的策略，每种策略都针对不同规模的谜题而设计。

首先，对于小型谜题（涉及多达 7 个量子比特），他们创建了一种“最优”（Optimal）方法。想象这是一个极其缓慢但极其细致的制图师，他会检查迷宫中每一条可能的路径，以确保找到了绝对最短的路线。他们建立了一个庞大的数据库，记录了所有可能的“捷径”，通过将那些看起来不同但在旋转或翻转棋盘后实际上相同的路径进行分组来实现。这使得他们能够为小型问题瞬间查找出最佳解决方案，在速度和效率上都超越了以往的方法。

对于中型谜 жизни 谜题，他们使用了“A*”策略。你可以把它想象成一个带着指南针的聪明徒步者。这位徒步者不会检查每一条路径，而是使用一种聪明的猜测（一种“启发式算法”）来估计哪个方向看起来最有希望。他们维护着一个潜在路径的列表，始终选择那个看起来离终点最近的路径。研究人员发现，通过使用一种特定的数学方法来进行这些猜测，他们的徒步者可以找到几乎与完美制图师路径一样短的路径，但寻找过程要快得多。

最后，对于巨大的、大规模的谜题（数十个量子比特），他们使用了“贪婪”（Greedy）法。这就像是一个只看眼前一步的徒步者，总是采取当前看起来能最大限度缩短距离的那一步。通常，这种“目光短浅”的思维会导致你陷入死胡同（局部最小值），但该团队发明了一种新的观察地图的方式。他们不再仅仅是计数步骤，而是利用一个向量（一组数字）来观察问题的“形状”，这有助于他们避开死胡同。这种方法产生的电路始终比现有的最佳工具（如 Qiskit 或 Rustiq）更短。

结果令人印象深刻。当他们在随机电路和特定的纠错码（如著名的 Golay 码）上测试这些方法时，他们的算法所使用的“纠缠”两量子比特门（即最昂贵且最易出错的部分）的数量，始终低于目前任何其他方法。对于 Golay 码，他们甚至找到了一个仅包含 56 个门的电路，击败了此前 57 个门的最优纪录。他们不仅仅是找到了一种稍好一点的方法，而是找到了一种在问题规模扩大时表现更佳的扩展方式。

然而，作者也谨慎地指出，他们的“魔法”在哪里会失效。那个“完美的”制图师（Optimal）只适用于非常小的电路，因为路径数量增长得太快，以至于对于更大的规模来说，检查所有路径变得不再可能。那个“聪明的徒步者”（A*）虽然擅长处理中等规模，但如果迷宫过于复杂，仍然会变慢。而那个“目光短浅的徒步者”（Greedy），虽然在处理大型电路时表现出色，但并不能保证找到绝对最短的路径，只能找到一个非常好的路径。他们还指出，他们的工作侧重于理论上的门数量；如何在具有特定连接限制的真实物理硬件上运行这些电路，是接下来的下一步。

简而言之，这篇论文为量子工程师提供了一套全新的工具包。它提供了一种将纠缠的量子电路乱麻缩减为流畅、高效线条的方法，让实现无错量子计算机的梦想离现实又近了一步。通过结合用于处理小任务的完美捷径数据库、用于中型任务的聪明猜谜游戏，以及用于大型任务的巧妙“预判”策略，他们证明了我们可以用比以往更少的动作和更少的浪费来构建这些电路。

技术摘要：CNOT 与 Clifford 电路的启发式与最优合成

问题陈述

高效实现 Clifford 电路对于量子纠错和量子算法至关重要。这些电路的效率通常通过纠缠两比特门（特别是线性可逆电路中的 CNOT 门）的数量或电路深度来衡量。优化这些指标具有挑战性，因为单个 Clifford 算子可以通过众多具有截然不同门计数和深度的电路配置来实现。现有的方法，例如 rustiq、tket 和 qiskit 中的高斯消元法或启发式方法，往往无法找到最紧凑的实现，特别是在处理较大比特数或特定编码电路时。此外，关于线性可逆电路（仅限 CNOT）的经典文献已经建立了各种合成技术，但仍需要统一且高效的方法，以同时最小化 CNOT 电路和通用 Clifford 电路的双比特门数量。

方法论

作者提出了一个用于合成 CNOT 和通用 Clifford 电路的统一框架，该框架包含三种不同的算法族：最优（Optimal）、A* 和 贪婪（Greedy） 合成。其核心方法是将电路算子映射为二进制矩阵，并利用等价类来缩小搜索空间。

1. 数学表示

CNOT 电路： 映射为 $GL(n, 2)$ 中的可逆二进制矩阵。一个 CNOT 门对应于将一列加到另一列上。
通用 Clifford 电路： 映射为 $Sp(2n, 2)$ 中的辛二进制矩阵。作者利用了一种由三层组成的电路结构：比特置换、单比特 Clifford 以及两比特辛变换（在单比特 Clifford 意义下等价于 CNOT）。
等价类： 作者通过考虑以下维度的等价类，显著降低了计算复杂度：
- 行和列置换（比特置换）。
- 矩阵转置和求逆。
- 对于 Clifford 电路，左乘和右乘单比特 Clifford 算子。
- 这允许从一个等价类中选择具有最低门计数或深度的电路成员。

2. 算法族

A. 最优合成 (Optimal Synthesis)

方法： 生成所有在一定比特数范围内（CNOT 为 $n \le 7$ ，Clifford 为 $n \le 5$ ）的矩阵等价类的数据库。
机制： 通过应用所有可能的门序列来生成矩阵。等价性的判定是通过将矩阵映射为双色图（针对 CNOT）或广义图（针对 Clifford），并使用如 nauty 或 Bliss 等软件包进行同构检查。
用法： 对于目标矩阵，算法在其预计算的数据库中查找其等价类，并检索最优门序列，最后应用必要的置换以匹配目标。

B. A* 合成 (A* Synthesis)

方法： 一种旨在处理中等规模电路的最佳优先搜索算法，适用于最优数据库过大的情况。
机制： 使用优先队列来探索门序列。它采用启发式函数 $h(P)$ 来估计到达置换矩阵（对于 CNOT）或置换加单比特 Clifford（对于 Clifford）的剩余代价。
启发式： 作者基于矩阵的行和列和推导出了鲁棒的估计器（具体为 $H_{sum}$ 和 $H_{prod}$ 指标）。他们发现缩放这些启发式函数（ $r \cdot h$ ）可以提高性能。算法不会立即提交一个门，而是扩展具有最低 $g(P) + h(P)$ 值的节点。
优化： 为了管理指数级的最坏情况复杂度，优先队列的大小被限制（例如 100 个条目），如果超过限制，则移除最大项。

C. 贪婪合成 (Greedy Synthesis)

方法： 一种针对大规模电路的快速确定性算法。
机制： 在每一步中，它评估所有可能的门，并选择使特定启发式函数最小化的那个。
创新： 不同于以往通过对条目或对数和进行求和的标量启发式方法（这些方法经常陷入局部极小值），作者引入了一种基于向量的启发式方法。该向量通过对矩阵、其逆矩阵、其转置及其逆转置的列和进行排序而形成。
深度优化： 贪婪算法可以经过修改以最小化电路深度，即将深度作为主要代价，并将启发式函数作为次要惩罚项。

核心贡献与结果

1. 算法改进

向量启发式： 提出的用于贪婪合成的向量启发式方法在避免局部极小值方面显著优于标量启发式方法（如 $H_{sum}$ 和 $H_{prod}$ ）。对于 $n \ge 32$ 比特的电路，向量启发式占主导地位，而标量启发式则表现失败（放弃运行），其在 $n > 32$ 的电路上的放弃率达 100%。
等价类缩减： 通过将问题映射到图同构问题并考虑置换、转置和求逆，作者生成的数据库比以往的方法（例如，相比于 Bravyi 等人 [4] 显著缩小了 $Sp(2n, 2)$ 的搜索空间）要小得多。

2. 基准测试结果

作者使用随机矩阵和特定数据集对他们的算法与 rustiq、tket、qiskit、PyZX 和 Volanto 进行了基准测试。

CNOT 电路：
- Optimal/A*： 对于 $n \le 7$ ，A* 算法达到了最优门计数。对于高达 $n = 32$ 的电路，A* 算法提供了最低的门计数。对于 $n \ge 32$ 的电路，带有向量启发式的贪婪算法产生了最低的 CNOT 计数，比高斯消元法的门计数平均减少了 50%。
通用 Clifford 电路：
- 随机矩阵： A* 算法在 $n \le 5$ 时匹配最优计数，并在高达 $n = 16$ 的电路中提供最低计数。对于 $n > 16$ 的电路，贪婪算法的表现显著优于所有其他测试方法（包括 pytket 和 rustiq）。
- 哈密顿量数据集： 在 4 到 64 比特的哈密顿量演化电路数据集上，贪婪算法在门计数和运行时间上均优于 BSHM 算法（以及随后的 pytket 优化）。
- 编码电路： 对于 Golay 码 $[[23, 1, 7]]$ ，作者通过 A* 算法找到了一个包含 56 个纠缠两比特门的编码电路，优于之前的最佳方案——Steane 方法（57 个）和强化学习方法（61 个）。
与 SAT 求解器的比较： 与 qsynth（基于 SAT 的求解器）相比，作者的最优和 A* 算法在处理高达 5 比特的电路时，不仅匹配或提高了门计数，且处理速度快了几个数量级。对于 $n \ge 6$ ，qsynth 在几乎所有实例中都超时了，而作者的方法均成功完成。

3. 实现

这些算法已实现为一个 Python 包并在 GitHub 上发布，允许社区复现结果并将这些方法应用于他们自己的电路。

重要性与声明

论文声称其主要意义在于提供了一套合成工具，这些工具在广泛的电路规模下，都能持续实现比现有最先进方法更低的双比特门计数。

可扩展性： 该工作填补了小规模最优合成与大规模启发式合成之间的空白，为高达 64 比特的电路提供了切实可行的解决方案，而此前的方法要么因数据库规模问题导致最优合成失败，要么因时间限制导致 SAT 求解器失败。
鲁棒性： 向量启发式被强调为一项关键进步，它防止了贪婪法中常见的“局部极小值”陷阱。
实际影响： 为纠错码（如 Golay 码）寻找更紧凑电路的能力，通过减少逻辑操作所需的资源开销，直接影响了容错量子计算的可行性。
局限性说明： 作者承认，由于数据库规模的原因，目前的最优合成在 CNOT 上限于 $n \le 7$ ，在 Clifford 上限于 $n \le 5$ ，尽管他们认为可以通过更好的编码技术进行扩展。他们还指出，虽然其贪婪算法速度很快，但不能保证大规模电路的全局最优性，尽管实验证明其表现优于竞争对手。