PureMagic: A Dynamic Scheduler for Lattice Surgery

PureMagic 是一种用于晶格手术的动态调度器，它通过将所有辅助补丁重新用于路由和随机魔态培育，从而消除了专用的总线补丁，与传统静态方法相比，在效率、资源利用率和制备时间方面实现了显著改进。

要点

想象一下，你正在运营一座规模宏大、极其复杂的工厂。这座工厂不生产汽车或手机，而是制造量子计算机，这些计算机能够解决当今机器无法解决的难题。但有一个棘手之处：这座工厂极其脆弱。如果一名工人打个喷嚏，整个生产线都可能崩溃。为了解决这个问题，工厂采用了一种名为纠错的“安全网”系统，即让许多工人执行相同的任务以确保准确性。

然而，要完成最先进的工作，工厂需要一种特殊且稀有的原料，称为**“魔态”**。制造这种原料颇具挑战性。

旧方法：专用的“魔态工厂”

在传统方法（被先前系统所采用）中，工厂建造了巨大的永久性建筑，专门用于制造这些魔态。

• 问题所在：这些建筑占据了巨大的空间（逻辑量子比特）。它们就像坐落在工厂边缘的巨型仓库。
• 瓶颈：由于它们位置固定，无法移动。如果主生产线需要一名工人将箱子从工厂一侧搬到另一侧，魔态工厂里的工人无法帮忙；他们被束缚在制造魔态的任务中。
• 赌博性质：制造魔态就像掷骰子。有时只需几秒钟；有时，由于运气不佳，可能需要数小时。旧系统必须等待“慢速投掷”完成才能继续，导致整个工厂陷入闲置。

新方法：PureMagic（“瑞士军刀”式工人）

这篇论文介绍了PureMagic，这是一种彻底改变规则的工厂运营新方式。

1. 不再需要专用工厂
PureMagic 提出：与其建造专门用于制造魔态的特殊建筑，不如**“人人都是魔态制造者”**。
工厂里的每一位工人（称为“辅助补丁”）都接受过制造魔态的训练。他们不断地尝试酿造魔态原料。

2. 动态切换
这里是巧妙之处：这些工人同时也是送货司机。

• 情景 A：一名工人正忙于酿造魔态。
• 情景 B：突然，主生产线需要这名工人将箱子穿过工厂（路由）。
• 魔性操作：该工人立即停止酿造，丢弃未完成的魔态，转而搬运箱子。一旦箱子送达，他们便立即从头开始重新酿造魔态。

为什么这更好？

• 切断“长尾”：在旧系统中，如果一次制造魔态的尝试陷入“运气不佳”的循环（耗时无限长），整个工厂都会等待。而在 PureMagic 中，如果一名工人在酿造时陷入停滞，他们会被送货任务打断。这自然地切断了缓慢尝试的“长尾”。工厂只保留“快速”的魔态制造者，使得获取魔态的平均时间大大缩短（根据论文，快了 4.5 倍）。
• 无闲置时间：在旧系统中，当魔态工厂工作时，送货工人会闲置，反之亦然。而在 PureMagic 中，每位工人总是在做某件事——要么制造魔态，要么搬运物品。没有浪费的空间。

3. “负重限制”技巧
论文还提到了一种名为“负重限制”（记为 $\omega$）的软件技巧。你可以将其想象为关于一名工人一次能携带多少箱货物的规则。

• 旧方法试图携带巨大的负载（复杂的指令）以节省步骤，但这很容易导致停滞。
• PureMagic 使用规则将指令分解为微小的、单箱负载。这意味着工厂可以同时并行运行许多工人。由于 PureMagic 拥有大量可用的工人（因为他们不会被困在魔态工厂中），它比旧系统能更好地利用这种并行性。

结果

研究人员在 29 种不同的“工厂设计”（基准电路）上测试了这一新系统。以下是他们的发现：

• 效率：PureMagic 比旧的总线路由系统高效 40% 到 150%。
• 空间：完成相同工作所需的工人（逻辑量子比特）减少了 19% 到 80%。
• 速度：它将准备魔态原料所需的时间缩短了 4.5 倍。
• 对比：与现有的最佳静态调度器（DASCOT）相比，在计入制造魔态状态的成本后，PureMagic 的效率最高可达 15 倍。

核心结论

PureMagic 将工厂车间视为一个流体、动态的环境，而非具有固定角色的刚性网格。通过让每位工人在“制造魔态”和“运送包裹”之间瞬间切换，它消除了空间浪费，剔除了最缓慢的尝试，并保持量子计算机以峰值速度运行。论文声称，这种方法如此接近理论上的完美极限，以至于如果不改变机器的基本物理原理，几乎不可能做得更好。

技术摘要

技术摘要：PureMagic

问题陈述

利用表面码进行容错量子计算依赖魔态（magic states）来实现通用性。传统方法利用蒸馏工厂，即大型、静态的逻辑量子比特阵列（每个输出端口包含 121–176 个补丁），以确定性方式生产魔态。这导致资源必须静态地放置在边缘，形成一种僵化的架构，其中“总线”补丁专用于路由，而“魔态”补丁专用于生产。

另一种替代方案是魔态培育，它将占用面积减少到单个逻辑量子比特，但引入了固有的随机性。生产高保真度魔态所需的时间遵循具有“长尾”的指数分布，意味着某些尝试所需时间显著长于平均值。假设资源可用性是确定性的静态调度器无法适应这种变异性，从而导致停顿和低效。此外，培育时间的长尾迫使静态调度器要么过度配置资源，要么接受显著的延迟。

方法论

作者提出了PureMagic，这是一个动态调度框架，从根本上重新思考了晶格手术中辅助补丁（ancilla patches）的作用。

1. 双用途辅助架构

PureMagic 消除了专用总线补丁与魔态培育器之间的区别。相反，所有辅助补丁都被视为双用途资源：

• 培育：每个非数据补丁持续尝试培育魔态。
• 路由：当需要为泡利积（Pauli product）建立路由路径时，任何补丁（包括正在培育的补丁）都可以立即被重新利用。
• 中断与重启：如果某个补丁需要用于路由，其正在进行的培育将被取消。一旦路由任务完成，该补丁上的培育将从头开始。这种机制自然地截断了培育时间分布的长尾，因为生长缓慢的状态会被路由需求中断，从而确保只有最快的成功尝试能纳入调度。

2. 动态调度算法

调度器在**基于泡利的计算（PBC）**框架内运行，其中 Clifford+T 电路被转换（transpiled）为多量子比特泡利积测量序列。

• 实时适应：调度器在一个逻辑周期内（对于码距 $d=17$ 约为 17µs）做出决策。它处理两个非确定性来源：随机的培育完成时间和 50% 的 T 态注入失败概率（需要 S 门校正）。
• 启发式打包：为了解决 NP 难的晶格手术调度问题（LSSP），PureMagic 采用了一种贪婪的斯坦纳森林（Steiner forest）打包算法。它根据估计的树大小（使用曼哈顿距离）对泡利积进行优先级排序，优先调度最紧凑的操作。
• 路径查找：对于单算子泡利积，使用高效的 A* 算法寻找通往可用魔态的路径。对于多量子比特积，使用最短路径启发式方法来近似斯坦纳树。

3. 带权重限制（$\omega$）的转换

作者引入了一种使用权重限制 $\omega$ 的表算法（Tableau algorithm）转换扩展。

• $\omega = 1$（轻量级-PBC）：将泡利积限制为单算子。这略微增加了总门数（2–6%），但通过最大化并行性，极大地减少了电路深度（高达 26 倍）。
• $\omega = \infty$（重量级-PBC）：标准方法，其中所有 Clifford 门都被交换，导致门数较少，但泡利积的权重更高，并行性更低。
  PureMagic 专门设计用于利用 $\omega = 1$ 设置的高并行性，因为更多可用的培育补丁可以服务更多的并发路由请求。

主要贡献

1. PureMagic 架构：一种布局设计，消除了专用总线补丁，允许每个辅助补丁可互换地作为培育器和路由资源。
2. 动态调度器：一种实时调度器，能够适应随机的培育时间和 T 态注入失败，利用贪婪的斯坦纳森林打包方法。
3. 仿真框架：一个逻辑量子比特级别的模拟器，用于模拟概率性培育和注入失败，以评估调度性能。
4. 带权重限制的转换：表算法的扩展，以门数为代价换取电路并行性，从而优化 PureMagic 架构的工作负载。

实验结果

该框架在 Benchpress 套件中的29 个基准电路上进行了评估，模拟了在抽象表面码模型（$d=17$）上的执行。

• 效率提升：与传统的总线路由布局相比，PureMagic 实现了40% 到 150% 的效率提升（时空体积的倒数）。在使用轻量级转换设置（$\omega = 1$）时，收益最为显著。
• 资源减少：PureMagic 使用的逻辑量子比特数量比总线路由布局少 19% 到 80%，因为它不需要固定周边的专用魔态工厂。
• 培育时间：由于截断了培育分布的长尾，平均魔态制备时间减少了4.5 倍（从平均 26 个周期降至 5.8 个周期）。
• 与静态调度器的比较：与DASCOT（一种假设魔态立即可用的最先进静态调度器）相比，当包含魔态制备成本（培育时间或蒸馏工厂面积）时，PureMagic 的效率最高可达15 倍。
• 理论界限：PureMagic 的调度体积介于保守和乐观的FLASQ 理论下界之间，表明这种动态双用途策略非常接近“流体”辅助资源的理想状态。

意义与主张

该论文认为，路由与魔态生产的分离是蒸馏工厂高开销的产物。通过采用培育和动态调度，“流体辅助”理想——即任何可用资源都可以服务于任何功能——变得可实现。

作者声称，PureMagic 证明了动态调度对于高效的容错量子计算至关重要，特别是在使用如培育等资源高效的方法时。他们建议，未来对量子纠错码（QECCs）的比较应超越静态门级指标，纳入动态调度和资源管理的开销。这项工作暗示，随着算法对更高保真度魔态的需求（需要更长的培育时间），PureMagic 能够在大量补丁池中分摊培育成本的优势将变得更加显著。