作者: Rajeswari Suance P S, Ruchika Gupta, Maurizio Palesi, John Jose

1. 核心物理图象

想象一下，一个大型量子计算机由许多小的“量子核心”（每个核心里有几十个量子比特）通过一个“量子网络”连接而成，就像一台多核CPU电脑。当一个量子程序（量子电路）要运行在这些核心上时，需要决定每个量子门在什么时间、哪个核心上执行。如果安排得不好，比如严格按照“一层一层”的顺序执行，那么一个慢速的跨核心通信（比如通过量子隐形传态）就会拖慢整个程序，让其他核心闲置等待。这篇论文的核心思想是：我们不应该死板地按层执行，而应该像一个聪明的调度员，一旦某个量子门的所有前置条件（比如它依赖的上一个门已经完成、通信链路空闲）都满足了，就立刻让它开始执行。这种“贪心”的调度方式能极大地挖掘并行性，把等待通信的时间隐藏在其他计算中，从而显著缩短整个程序的运行时间（称为“makespan”）。

主要贡献：提出了一种依赖感知的贪心调度算法，相比传统的分层调度，在真实量子基准测试上平均能将程序执行时间缩短40%。

2. 关键术语解释

1. 分层调度 (Layered Scheduling)：这是一种传统的、简单的调度方法。它将量子电路中所有可以同时执行的量子门归为一个“层”，然后一层一层地顺序执行。只有当当前层中所有门（包括最慢的那个）都完成后，才开始下一层。这篇论文用它作为基准来对比，证明新方法的优越性。

2. 贪心调度 (Greedy Scheduling)：这是论文提出的新方法。它不依赖预定义的“层”，而是为每个量子门计算一个“最早开始时间”。这个时间取决于：1）它所依赖的所有前序门是否已完成；2）所需的量子比特和通信链路是否空闲。一旦条件满足，门就立刻被调度执行。这样就能让快的门不等慢的门，实现更细粒度的并行。

3. Makespan：指完成一个完整的量子电路（程序）所需的总时间。它是衡量调度效率的核心指标，论文的主要目标就是最小化makespan，因为量子比特对环境噪声非常敏感（会退相干），时间越短越好。

3. 主要贡献 (Key Contributions)

1. 首次形式化定义了多核量子架构中的电路调度问题：特别引入了“纠缠链路可用性”这一新颖约束，这对于基于片上网络（NoC）的系统至关重要。此前的研究主要集中在硬件或量子比特映射上，调度问题尚未被深入探索。

2. 提出一种高效的依赖关系提取算法：通过追踪每个逻辑量子比特上最后一个执行的量子门，快速构建出所有门之间的依赖关系有向无环图（DAG），为贪心调度奠定基础。

3. 设计并实现了依赖感知的贪心调度算法：该算法能动态计算跨核心通信的延迟，并检查通信链路是否空闲，从而在最短的时间内安排每个量子门，最大化并行度并有效隐藏通信延迟。

4. 进行了全面的性能对比：在合成和真实量子基准测试上，证明了贪心调度在Makespan、核心利用率和通信-计算重叠率三个指标上，全面且显著优于传统的分层调度方案。

4. 研究方法 (Methodology)

作者首先建立了一个多核量子架构模型：核心呈2D网格排列，通过基于量子隐形传态的混合量子-经典片上网络（NoC）互连。通信采用逐跳隐形传态，延迟与跳数成正比。每个核心有部分量子比特专门用于建立通信所需的纠缠链路。

然后，作者将调度问题形式化为一个最小化Makespan的优化问题，并考虑了三个约束：门之间的依赖约束、纠缠链路约束（一条链路一次只能支持一次隐形传态）和量子比特约束。

为了解决这个问题，作者提出了贪心调度算法（论文中的Algorithm 1）。该算法首先为每个电路门构建一个依赖图，将没有任何依赖的门放入“就绪队列”。然后，循环处理队列：

• 从队列中取出一个门，计算其最早开始时间（依赖于其所有前驱门的完成时间）。
• 如果该门是跨核心的，则计算通信延迟（跳数 × 每跳时间），并检查相关通信链路的空闲时间，更新门的实际开始时间。
• 调度该门后，更新其后继门的依赖计数，一旦计数归零，就将后继门加入就绪队列。

通过一个3x3网格和5个门的案例，论文直观地展示了贪心调度如何让不依赖长时通信的门（G1）提前执行，从而让后续依赖它的门（G4）与之前的慢门（G2）并行，将Makespan从12个单位时间减少到9个单位时间。

5. 实验结果与结论 (Results and Conclusion)

关键结论：

1. Makespan显著降低：在从 3x3 到 8x8 的不同规模网格上，贪心调度均比分层调度获得更短的执行时间。在真实基准测试（Graph State, QAOA, QFT, QPE）上，平均Makespan降低40%。
2. 核心利用率提升：贪心调度通过避免核心闲置等待，提高了核心的活跃度。但由于是单电路运行，利用率仍不高（<15%），未来多电路场景有望大幅提升。
3. 通信-计算重叠率大幅提高：贪心调度能有效将通信时间隐藏在并行计算中，最佳情况下重叠率可达76%，而分层调度最多仅20%。这解释了Makespan降低的根本原因。

对领域的启示： 这项工作证明了智能的电路调度是释放多核量子计算机潜力的关键。仅增加核心数（硬件）是不够的，必须配合高效的软件调度策略来管理和利用这些资源，这对于构建大规模、实用的量子计算机至关重要。

开放性问题： 论文明确指出了两个未来方向：

1. 考虑噪声：当前模型假设隐形传态和门操作是无噪声的理想情况。未来需要引入噪声模型。
2. 多电路并发与链路竞争：未来可以研究多用户、多电路同时在多核系统上运行时的调度策略，以及由此引发的纠缠链路资源竞争问题。

6. 论文标签 (Tags)

编译与优化, 量子算法, 物理硬件

📄 点击此处展开/折叠原文 PDF

原文链接： Dependency-Aware Circuit Scheduling for Multi-Core Quantum Systems to Minimize Makespan