📚 课程目录第2章量子任务调度问题定义

2. 量子任务调度问题定义

量子任务调度并不是把经典作业调度换个名字，而是要在量子硬件真实的物理限制下，决定“哪些量子操作在什么时刻、落在哪些量子比特上执行”。要把它讲清楚，需要先回答四个问题：量子任务长什么样、调度要优化什么、硬件给了哪些约束、这些约束如何写成可求解的形式。本节围绕这四点展开，并给出一个可复用的形式化描述。

一、量子任务的特征建模

一个量子任务（quantum task）通常由量子线路描述，其本质是一个有向无环图（DAG）。图中节点是量子操作，边表示数据依赖。节点可分为三类：单量子比特门（如 H、X、Rz）、双量子比特门（如 CNOT、CZ、iSWAP）、测量操作。每个节点带有若干属性：

操作类型：决定它需要几个量子比特、能否被并行执行；
作用比特：单比特门作用于一个逻辑比特，双比特门作用于一对逻辑比特；
持续时间：单比特门典型 20～50 ns，双比特门典型 100～500 ns，测量约 300～1000 ns（示例量级，随硬件而异）；
依赖关系：只有前驱节点完成后，后继节点才能开始。

此外，逻辑比特到物理比特的映射（qubit mapping）是调度前的关键一步。若两个逻辑比特之间存在双比特门，它们必须被映射到物理上可直接耦合的比特对，否则需要插入 SWAP 门来“搬运”量子态，这会显著增加门数量和深度。

二、调度目标与约束

调度目标通常不是单一的，而是多目标权衡：

最小化总执行时间（makespan）：即最后一个操作完成的时间；
最小化线路深度：深度直接影响相干时间内的可执行门数；
最大化并行度：让互不依赖的门在同一时间片内并发执行；
最小化 SWAP 开销：减少因连通性不足引入的额外门；
满足保真度阈值：确保整体成功概率不低于可接受水平。

约束主要来自三方面：依赖约束（DAG 的偏序关系）、资源约束（同一物理比特同一时刻只能执行一个门）、拓扑约束（双比特门只能作用于耦合边上的比特对）。这些约束共同决定了可行调度空间。

三、量子比特拓扑与连通性约束

物理量子比特并非全连接，而是按特定拓扑排列，常见的有线性链、环形、网格（grid）、重六边形（heavy-hex）等。拓扑决定了哪些比特对可以直接执行双比特门。若逻辑线路中某对逻辑比特需要交互，但它们在物理上不相邻，就必须通过 SWAP 链把其中一个逻辑比特“移动”到相邻位置。

例如，在 5 比特线性链 q0—q1—q2—q3—q4 上，若需要执行 CNOT(q0, q4)，则需插入至少 3 个 SWAP 才能让 q0 与 q4 相邻。每个 SWAP 本身由 3 个 CNOT 实现，因此一次远距离交互可能带来 9 个额外 CNOT。这说明拓扑约束对调度质量影响极大。

四、相干时间与门操作时间对调度的影响

量子比特的相干时间 T₂ 是调度中最“硬”的约束之一。所有操作必须在相干窗口内完成，否则量子态退相干导致结果不可信。设某条路径上串行门的总时长为 Σtᵢ，则必须满足 Σtᵢ ≤ T₂（实际中还需留出测量和读取时间）。

门操作时间决定了并行调度的粒度。若单比特门 30 ns、双比特门 200 ns，则一个双比特门的时间片可以容纳约 6 个单比特门。调度器应尽量把单比特门“塞”进双比特门的等待间隙，提高时间利用率。但要注意：同一比特上的门必须串行，不能重叠。

一个实用的判断方法是计算“关键路径长度”。关键路径是 DAG 中从起点到终点的最长加权路径，其权重为门持续时间。关键路径长度给出了 makespan 的下界。若关键路径长度已接近 T₂，则必须通过减少 SWAP、优化映射或拆分任务来降低深度。

五、调度问题的形式化描述

综合以上，量子任务调度可形式化为一个带约束的优化问题。给定：

量子线路 DAG：G = (V, E)，V 为操作节点，E 为依赖边；
物理拓扑：P = (Q, C)，Q 为物理比特集合，C 为可耦合边集合；
映射函数：m: 逻辑比特 → 物理比特；
每个操作 v 的持续时间 d(v) 和所需比特集合 q(v)。

求一个调度函数 s: V → ℝ⁺（开始时间），使得：

minimize  makespan = max_{v∈V} (s(v) + d(v))
subject to:
  (1) 依赖约束：∀(u,v)∈E, s(v) ≥ s(u) + d(u)
  (2) 资源约束：∀u,v, 若 q(u)∩q(v)≠∅ 且 u≠v，
      则 s(u)+d(u) ≤ s(v) 或 s(v)+d(v) ≤ s(u)
  (3) 拓扑约束：∀v 为双比特门，m(q(v)) 对应的物理比特对 ∈ C
  (4) 相干约束：makespan + t_measure ≤ T₂_eff
  (5) 保真度约束：∏_{v∈V} F(v) ≥ F_threshold

其中 F(v) 为操作 v 的保真度，F_threshold 为可接受阈值（例如 0.9 或 0.95，视应用而定）。这是一个 NP 难问题，实际中常用启发式方法求解：先做初始映射（如基于交互图的贪心匹配），再用列表调度（list scheduling）按优先级分配时间片，最后用 SWAP 插入策略优化连通性。

教学示例：假设 4 比特线性链 q0—q1—q2—q3，T₂_eff = 800 ns，单比特门 30 ns，双比特门 200 ns，测量 400 ns。若线路关键路径为 H(q0)→CNOT(q0,q1)→H(q1)→CNOT(q1,q2)→M(q2)，则串行总时长 = 30+200+30+200+400 = 860 ns，已超过 800 ns。此时必须通过并行化或减少 SWAP 来压缩关键路径，例如把 H(q1) 与 CNOT(q0,q1) 的等待时间重叠，或重新映射使 CNOT(q1,q2) 无需 SWAP。该示例说明：调度不是简单排序，而是要在物理约束下重新组织执行顺序。

总结来说，量子任务调度问题的定义包含四个层次：任务特征（DAG + 门属性）、目标函数（makespan、深度、保真度）、约束条件（依赖、资源、拓扑、相干）、形式化模型（调度函数 + 约束不等式）。理解这四层，才能在实际调度器中做出合理的设计与取舍。