Quantum circuit partition as a maze: emerging percolation transition via path finding

本文提出了一种将量子线路划分形式化为迷宫切割问题的创新框架，并证明了当 CNOT 门数量与量子比特数量相当时，一种渗流相变决定了是否可以在不移除门的情况下将线路最优地拆分为两个 CNOT 簇。

要点

想象一下，你有一个巨大的、缠绕在一起的毛线球，它代表着一个复杂的量子计算机程序。你的目标是将这个球一分为二，以便两台不同的计算机可以同时处理其中的一半，从而提高速度。然而，这里有一个陷阱：“毛线”是由被称为 CNOT 门 的特殊结组成的。如果你剪断了一个结，程序就会损坏并停止运行。你需要找到一种切割方式，确保完全不切到任何结。

这篇论文将这个问题视作解迷宫。

迷宫类比

作者将量子电路变成了一个网格，就像一个视频游戏关卡：

• 墙壁： CNOT 门就是迷宫中的墙壁。它们是坚固的障碍物，你无法穿过。
• 路径： 你需要从迷宫的左侧向右侧画一条线（即“切割线”）。
• 目标： 如果你能画出一条从左到右且不碰到墙壁的线，你就成功地将电路分割成了两个独立的部分。如果你碰到了墙，说明电路过于纠缠，无法在不破坏电路的情况下进行分割。

问题：“拥挤的中心”

在他们最初构建这些迷宫时，他们注意到一个模式。墙壁（结）往往会堆积在迷宫的正中间，就像城市中心的交通堵塞一样。因为中心区域过于拥挤，几乎不可能画出一条穿过中心的直线而不碰到墙壁。

解决方案：重新布置家具（模拟退火）

为了解决这个问题，作者使用了一种被称为模拟退火的聪明技巧。你可以把它想象成一个非常聪明、有耐心的机器人，它可以重新排列迷宫的行。

1. 洗牌： 机器人会打乱“导线”（量子比特传输的线条）的顺序。这就像拿一副扑克牌，通过洗牌来观察墙壁是否会移动到牌组的顶部或底部。
2. 目标： 机器人试图将所有的墙壁从中心推向顶部和底部的边缘。
3. 结果： 如果机器人成功了，它就会创造出一个**“中央走廊”**——一条贯穿迷宫中间的清晰、空旷的通道。现在，你可以轻松地通过这个空旷的空间画出你的切割线，而不会碰到任何墙壁。

“相变”：临界点

论文中最令人兴奋的发现是，当你改变墙壁（CNOT 门）的数量与导线（量子比特）的数量之间的比例时，会发生什么。

他们发现了一个临界点，类似于水突然结冰的过程：

• “容易”区域： 如果墙壁的数量大致等于（或小于）导线的数量，机器人几乎总能重新排列迷宫以创造出那个清晰的中央走廊。此时电路是可分割的。
• “不可能”区域： 如果墙壁太多（CNOT 门过多），迷宫会变得过于拥挤，无论机器人如何打乱行顺序，墙壁都会阻塞所有可能的路径。此时电路是不可分割的。

这种从“我们可以分割”到“我们无法分割”的突然转变被称为渗透相变。这就像一场洪水：在某个水位高度，水突然连接了整个湖泊。在这里，在某个门（gate）的密度下，墙壁突然连接了整个迷宫，从而封锁了任何路径。

为什么这很重要

这篇论文不仅仅是在说“分割电路很难”。它给出了一个实用的规则：如果你的 CNOT 门数量大约等于量子比特的数量，你很可能可以分割该电路。 如果你的门比量子比特多得多，你可能无法做到。

通过将一个复杂的数学问题转化为一个“解迷宫”的游戏，作者提供了一种清晰、直观的方法，让我们无需拆解电路，就能知道一个量子电路是否可以通过分割来进行优化。他们使用了一个“迷宫代理”（一个简单的计算机程序）来寻找最佳路径，证实了这种“走廊”策略对许多类型的量子电路都是有效的。

技术摘要

技术摘要：量子线路划分作为迷宫：通过路径寻找呈现的涌现渗流相变

问题陈述
在量子线路优化中，特别是在噪声中等规模量子（NISQ）设备中，减少双比特门（通常为 CNOT 门）的数量是一个主要目标，因为这些门具有显著的噪声影响。虽然线路划分允许在多个设备上进行并行优化，但现有方法通常依赖于通过中途测量和量子比特重置来切割 CNOT 门。目前存在一个关键空白，即如何确定一个线路是否可以被优化地划分为两个子线路，且无需切割任何 CNOT 门。挑战在于识别出一个准则，用以区分可划分的线路（允许对子线路进行独立重构）与不可划分的线路，且无需借助门切割。

方法论
作者将线路划分问题形式化为“迷宫”中的路径寻找任务。该方法论通过以下几个关键阶段进行：

1. 线路表示：

   • 线缆表示 ($W$)： 一个网格，行对应量子比特线，列对应 CNOT 门。如果一个 CNOT 涉及某个量子比特，则该单元格被标记。
   • 迷宫表示 ($M$)： 一个变换后的网格，行代表量子比特线之间的空间（加填充），列在空隙与 CNOT 门之间交替。在这种表示法中，CNOT 门充当“墙壁”。一个有效的划分对应于一条从迷宫左侧边缘到右侧边缘的连续路径，且不与这些墙壁相交。

2. 量子比特排序优化（模拟退火）：

   • 随机生成的线路初始表现出墙壁分布集中在迷宫中心的特征，使得水平遍历变得困难。
   • 作者利用模拟退火（SA）对线缆表示中的量子比特线顺序进行置换。这种置换会被映射回迷宫表示。
   • 在 SA 过程中最小化一个代价函数，该函数惩罚跨越网格中心区域的 CNOT 相互作用。目标是将相互作用推向顶部和底部边界，从而创造一个没有墙壁的“中央走廊”。

3. 路径寻找启发式算法：

   • 一旦迷宫完成优化，启发式智能体便会对迷宫进行遍历。两个确定性的智能体（一个在撞墙时向上移动，另一个向下移动）从第一列的每个单元格出发。
   • 智能体受限于单调移动（永不向后移动时间或在垂直方向反转方向），以确保生成的子线路在时间顺序上是一致的。
   • 一个加权代价函数 ($L_{tot}$) 根据三个指标评估候选路径：划分间的 CNOT 不平衡度、单元（面积）不平衡度以及路径长度相对于理想水平轨迹的偏差。

4. 网络科学分析：

   • 作者将线路分析为一个有向图，其中节点代表 CNOT 事件，边代表因果或纠缠关系。
   • 他们利用中心性度量（度中心性和介数中心性）和共识动力学（DeGroot 模型）来量化量子比特区域的分离程度，以及在 SA 优化前后信息流的混合情况。

关键结果

• 渗流相变： 研究识别了量子线路空间中的一种相变。存在一个明显的机制，即存在一个有效的、平衡的划分路径（可划分），以及一个不存在无需切割 CNOT 门即可实现路径的机制（不可划分）。
• 定标准则： 该转变由 CNOT 门数量 ($N_c$) 与量子比特数量 ($N_q$) 的比例控制。作者观察到，当 $N_c$ 大约等于 $N_q$ 时，可以将线路划分为两个平衡的 CNOT 集群是可行的。随着 CNOT 密度相对于量子比特增加， “中央走廊”会关闭，线路变得不可划分。
• 模拟退火的效果： SA 成功地重构了线路布局，将 CNOT 相互作用移至外围，并创造了一个低密度的中央走廊。这种变换将墙壁分布从单峰（Beta 分布）剖面转化为双峰剖面，从而促进了水平切割的存在。
• 网络动力学： 中心性分析表明，在可划分机制下，SA 将相互作用集中在寄存器边缘的量子比特上，使中心区域耦合较弱。共识动力学证实，在稀疏机制下，线路会分离为两个弱耦合集群；而在密集机制下，信息会全局混合，从而阻止分离。
• 三个阶段： 分析揭示了基于路径寻找得分的三个不同阶段：
  1. 第一阶段（可划分）： 存在严格的水平切割，能够平衡 CNOT 和单元。
  2. 过渡阶段： 路径必须在垂直和水平步骤之间交替，以绕过墙壁，导致划分不够平衡。
  3. 第二阶段（不可划分）： 不存在能分离线路的有效切割；智能体被迫走向边界，导致一个划分微不足道，而另一个划分包含了几乎整个线路。

意义与主张
论文声称提供了一个理论和数值框架，将线路划分理解为一种渗流现象。通过将问题映射到迷宫，作者建立了一个可扩展且实用的准则，用于确定一个量子线路是否可以在不切割 CNOT 门的情况下进行划分。

这项工作将“无需切割纠缠门即可划分线路”的能力定位为渗流相变的第一阶段，将量子线路优化与更广泛的关键现象（如测量诱导的相变和拓扑相变）联系起来。作者断言，其框架为量子线路优化算法开发提供了基础，提供了一种确定在无需中途测量开销的情况下，将优化任务并行化到多个设备上的可行性的方法。结果表明，对于纠缠门数量随量子比特数量线性缩放的线路，这种划分在理论上是可能的，并且可以通过所提出的渗流准则来识别。