⚛️ quantum physics

A Multilevel Framework for Partitioning Quantum Circuits

本文提出了一种多层级框架，该框架通过改进 Fiduccia-Mattheyses 启发式算法并引入一种新颖的目标函数，旨在高效地将量子电路划分到分布式量子处理单元中，与现有最先进方法相比，显著降低了纠缠代价并提升了对更大规模电路的扩展能力。

原作者： Felix Burt, Kuan-Cheng Chen, Kin K. Leung

发布于 2026-02-05

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Felix Burt, Kuan-Cheng Chen, Kin K. Leung

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

想象一下，你正在试图解决一个巨大且极其复杂的拼图。在量子计算的世界里，这个拼图就是一个“量子线路”（quantum circuit）——即一套给量子计算机的指令。问题在于，今天的量子计算机（称为 QPU）就像是一个个小型、单人使用的工作台。它们无法一次性容纳整个拼图。

为了解决这个大拼图，科学家们必须将其拆分成较小的碎片，并将这些碎片发送到通过网络连接的不同工作台（QPU）上。然而，这里有一个难点：为了让这些碎片能够相互通信，它们必须使用一种特殊的、脆弱的资源，叫做纠缠（entanglement，可以把它想象成一条“量子电话线”）。

使用这些电话线的成本很高。建立它们需要耗费大量时间，而且噪声很大（容易出错）。如果你只是随机地把拼图切碎并发送到不同的工作台，你会产生数以千计的电话通话，这不仅会拖慢速度，还会毁掉结果。

论文的解决方案：一种智能的“多层级”策略

这篇论文介绍了一种更聪明、更高效的拆分量子拼图的方法。作者 Felix Burt、Kuan-Cheng Chen 和 Kin K. Leung 构建了一个框架，其作用就像一位极其高效的项目经理。以下是他们是如何实现的，使用了简单的类比：

1. “远程传输”工具箱

通常，当两个拼图碎片需要通信时，你需要将其中一个碎片移动到另一个工作台（状态远程传输，State Teleportation），或者设置一个特殊的链路以便它们进行远程通信（门远程传输，Gate Teleportation）。

创新之处： 作者意识到，你可以做得更好。有时，你可以将几条指令组合在一起，通过同一条“量子线路”同时发送它们。他们称之为多门远程传输（Multi-gate Teleportation）。
新技巧： 他们还发现了一种被称为嵌套状态远程传输（Nested State Teleportation）的方法。想象一下，你有一个包裹需要从工作台 A 发送到工作台 C，但它必须先在工作台 B 停留一下。与其进行两次昂贵的旅程（A→B，然后 B→C），他们找到了一种方法，可以直接实现 A→C 的传输，仅将 B 作为临时中转站。这节省了大量的“电话线”使用量。

2. “地图”与“缩放”（多层级框架）

为了找到拆分拼图的最佳方式，作者将量子线路转化为了一个巨大的 3D 地图（“超图”，hypergraph），其中每一条指令都是一个节点，每一条连接都是一条线。

问题： 这张地图如此庞大且复杂，以至于标准的计算机程序在寻找最佳路径时会迷失方向。这就像试图通过同时观察每一块路牌来寻找城市中最短的路线一样。
解决方案（粗化）： 他们使用了一种名为多层级划分（Multilevel Partitioning）的技术。想象你在看一张国家的地图：
1. 缩小视角（粗化/Coarsening）： 首先，他们大幅模糊地图，直到城市看起来像单个的点。他们在这种简单的、模糊的地图上解决问题。在这里，看清大局非常容易。
2. 放大视角（细化/Uncoarsening）： 然后，他们慢慢放大，重新显现出街道。因为他们已经解决了大局问题，所以当细节出现时，他们只需要进行微调。
3. 优化（Refinement）： 在每一个缩放层级，他们都使用一种基于著名方法（称为 Fiduccia-Matthesses）的智能算法来进行微调，以确保各个部分平衡，并使“电话通话”次数降至最低。

3. 跳出“死胡同”

有时，计算机会被困在“局部最小值”（local minimum）中——即它认为自己找到了最优解，但实际上它只是山脉中的一个小山谷，而在另一座山头之后还存在着更好的方案。

修复方法： 作者增加了一个“探索性”模式。算法不仅仅是采取向前迈出的最佳步子，而是偶尔会采取一些“冒险”的步骤，即使这些步骤暂时会让情况变糟，以此来观察是否能找到另一边更好的山谷。这有助于它跳出死胡同，找到真正的最优解。

成果：他们取得了什么成就？

作者使用许多不同类型的量子拼图（线路），将他们的新框架与现有的最佳方法进行了对比测试。

更少的“电话通话”： 与次优方法相比，他们的方法平均减少了 35% 的纠缠需求（即“电话通话”）。在某些情况下，效果甚至更好。
处理速度更快： 由于采用了“放大/缩小”策略，计算机不需要花费太多精力去寻找解法。对于非常大的线路，它的运行速度通常比竞争对手更快。
可扩展性： 他们的办法可以处理包含数百个量子比特（qubit，量子信息的最小单位）的线路，而其他方法在合理的时间内根本无法解决这类问题。

局限性

论文指出存在一种权衡。为了获得如此巨大的“电话通话”节省，系统有时需要在工作台上需要更多的“存放室”（通信量子比特），以便在处理多条指令时保持链路开启。如果一台量子计算机没有足够的这些存放室，该方法可能需要进行调整。

总结：
这篇论文提出了一种全新的、高效的方法，用于将量子计算任务分配到多台机器上。通过使用“放大/缩小”策略和一种巧妙的新型指令分组方法，他们成功地大幅降低了运行这些任务所需的昂贵通信成本，使得分布式量子计算变得更加实用且强大。

技术摘要：一种用于量子电路划分的多层级框架

问题陈述
分布式量子计算（DQC）通过连接多个量子处理单元（QPU）并利用纠缠，为可扩展量子系统提供了路径。然而，在这些分布式节点上执行量子算法会引入显著的开销。将电路进行朴素的 QPU 映射会导致高昂的通信成本，具体表现为纠缠对（e-bits）的消耗、执行时间的增加以及噪声的加剧。核心挑战在于如何优化逻辑比特到 QPU 的分配，并确定覆盖非局部操作（作用于不同 QPU 上比特的门）的最有效方法。尽管现有方法已在解决这些问题，但它们往往无法捕捉到所有远程态传输（teleportation）的可能性，或者在面对优化问题的 NP-hard 特性时（特别是随着电路规模和网络规模的增加）显得力不从心。

方法论
作者提出了一个综合性的多层级框架，将量子电路划分形式化为一个超图划分问题。其工作流程由几个不同的阶段组成：

图构建与门分组：
- 电路被转译为特定的门集（ $U(\theta, \phi, \lambda)$ 和 $CP(\theta)$ ），并转换为一个在时间上扩展的图，其中节点代表特定时间步的量子比特。
- 该图通过根据“兼容性”对门进行分组，被泛化为一个超图。如果两个量子比特门共享一个共同的控制量子比特、是连续的，且未被控制端的非对角单比特门中断，则构成一组。
- 该框架引入了嵌套态传输（nested state teleportation），这是一种新颖的协议，其中门传输过程被部分折叠为态传输过程。这使得系统能够通过重定向多门传输过程的“结束过程（ending process）”，在态传输和门传输之间进行动态选择。
目标函数：
- 设计了一个独特的代价函数，旨在最小化所需的 e-bits 数量。超边的代价由接收集合所跨越的分区数量减去根集合所涵盖的部分（实际上是在统计需要新纠缠资源的切割量）来定义。
- 目标是最小化所有边代价的总和： $\min_{\Phi} \sum_{e \in E} c_e(\Phi)$ 。
划分算法（改进型 FM）：
- 采用了著名的 Fiduccia-Mattheyses (FM) 启发式算法，并对其进行了改进，以处理时间超图结构和特定的平衡约束（每个时间步内每个 QPU 的量子比特容量）。
- 为了确保效率，作者预计算了所有可能的超边配置的代价，并使用辅助数据结构（根/接收计数）以常数时间计算“增益变化量（delta gains）”。
- 为了跳出静态初始分配中固有的局部最优解，作者引入了探索性传递（exploratory passes），这类传递不会回滚到最佳累积增益，而是允许算法遍历那些暂时增加代价以达到更好全局最优解的移动序列。
多层级框架：
- 受最先进图划分器（如 METS, KaHypar）的启发，该框架采用了**时间粗化（temporal coarsening）**技术。它不是随机合并节点，而是合并时间步（例如：窗口、块或递归粗化）。
- 该过程包括：
  - 粗化（Coarsening）： 降低时间分辨率以创建一个更小、更粗糙的超图。
  - 划分（Partitioning）： 在最粗糙的图上求解划分问题。
  - 解粗化与精化（Uncoarsening and Refinement）： 逐渐恢复时间分辨率，使用前一层的解作为起点，并在每一层应用 FM 精化。
- 递归粗化策略（合并相邻时间步）被确定为最有效的方法，它在层级数量上实现了对数级的缩放。
电路提取：
- 最终划分的图被转换回分布式量子电路。这包括调度纠缠生成、管理传输过程的开始与结束，以及管理通信量子比特资源。

核心贡献

形式化嵌套态传输： 本文引入了一个统一的视角，将态传输、门传输和嵌套态传输视为同一种程序的变体，其区别在于结束过程的方向。这扩大了优化纠缠成本的设计空间。
多层级时间划分： 针对量子电路的时间结构适配了多层级技术，从而能在不同的粒度下解决问题，提高解的质量和运行速度。
改进型 FM 启发式算法： 一种改进的 Fiduccia-Mattheyses 算法，能高效处理 DQC 特有的代价函数和平衡约束，并包含通过探索性传递规避局部最优的机制。
开源实现： 该框架在 disqco 仓库中实现，为分布式量子电路编译提供了一个可复现的工具。

结果
该框架与最先进的方法进行了基准测试，包括 Pytket-DQC（使用 Partition, PartitionEmbed 和 EmbedSteinerDetached 工作流）以及细粒度划分（FGP-rOEE）方法。

纠缠减少： 在各种电路类型（CP-fraction, QFT, QAOA, Quantum Volume 和 QASM 基准测试）中，所提出的多层级框架（特别是递归变体 MLFM-R）在大多数情况下实现了最低的纠缠成本。
定量提升： 与排名第二的方法相比，该框架平均减少了 35% 的纠缠需求。
可扩展性： 与标准 FM 相比，多层级方法显著缩短了运行时间，并允许划分比竞争方法规模大得多的电路（数百个量子比特），前提是分区数量不是过大。
权衡： 使用门分组（多门传输）显著降低了电路深度，但也增加了对通信量子比特的需求。该框架允许用户根据可用硬件资源调整这种权衡。

意义与主张
论文声称，所提出的多层级框架代表了分布式量子电路编译领域的重大进展。通过将各种传输协议（态传输、门传输和嵌套态传输）统一在一个单一的优化目标下，并利用多层级图划分技术，作者证明了大幅降低纠缠开销（这是 DQC 的主要瓶颈）是可行的。

作者强调，虽然目前的工作假设所有 QPU 之间具有全连接性，并侧重于少于 20 个 QPU 的网络，但其核心技术设计具有可扩展性。他们断言，该框架为未来的分布式量子计算编译器栈提供了稳健的基础，能够处理大规模、高噪声且受限的量子网络。这项工作凸显了优化纠缠最小化不仅是一个理论练习，更是使分布式量子算法在近期及未来硬件上变得可行的实际必要条件。

1. “远程传输”工具箱

2. “地图”与“缩放”（多层级框架）

3. 跳出“死胡同”

成果：他们取得了什么成就？

局限性

技术摘要：一种用于量子电路划分的多层级框架

类似论文