📚 课程目录第3章量子线路与依赖关系分析

3. 量子线路与依赖关系分析

拓扑映射与路由调度的第一步，不是急着把逻辑比特塞进物理比特，而是先把量子线路“读懂”。一条量子线路表面上是若干量子门按时间排列的序列，但真正决定映射与调度空间的是门之间的数据依赖关系：哪些门必须先后执行，哪些门可以同时执行，哪些门之间需要跨比特通信。把这些关系抽取成一张有向无环图（DAG），后续的初始映射、SWAP 插入、调度优先级才有统一的依据。

从量子门序列到依赖约束

量子门按作用的量子比特数可分为单比特门（如 X、H、Rz）与多比特门（如 CX、CZ、iSWAP）。单比特门只作用于一个逻辑比特，它只与该比特上前后相邻的门产生依赖；双比特门同时作用于两个逻辑比特，它会在两条比特链上各产生一条依赖边。因此，依赖分析的核心规则可以概括为：同一逻辑比特上，后出现的门必须等待先出现的门完成；不同逻辑比特上的门，只要不共享比特，就没有直接依赖。

以一段 4 比特线路为例，按时间顺序给出门序列（示例，非实测）：

q0: H(0) ──●───────────────
q1: ──────X───Rz(1)───●───
q2: ──────────────H(2)─X───
q3: ───────────────────────

其中 CX(0,1) 依赖 H(0)；Rz(1) 依赖 CX(0,1)；CX(1,2) 同时依赖 Rz(1) 与 H(2)。可以看到，H(2) 与 Rz(1) 之间没有共享比特，二者可以并行。这种“共享比特才依赖”的判定，是并行性提取的全部基础。

线路 DAG 的构建

把每个门视为一个节点，把依赖关系视为有向边，就得到线路 DAG。构建时通常维护每个逻辑比特的“最近一次操作节点”指针：处理新门时，将该门连接到它涉及的所有比特的最近节点上，然后更新这些比特的指针。这样得到的 DAG 天然无环，因为边总是从时间较早的门指向时间较晚的门。

DAG 中每个节点带有若干关键属性：作用的逻辑比特集合、门的类型与持续时间、入度与出度。入度为 0 的节点是当前可立即执行的门，出度为 0 的节点是线路的末端门。调度器每次从入度为 0 的集合中挑选节点执行，执行后将其后继节点入度减一，减到 0 即进入就绪集合。这一机制让“哪些门现在能做”变成一个可计算的集合，而不是靠人工判断。

关键路径与并行性

DAG 中最长的一条路径称为关键路径，它的长度（按门持续时间累加）决定了线路在理想条件下的最短执行时间。上图中，H(0)→CX(0,1)→Rz(1)→CX(1,2)→M(0) 构成关键路径，而 H(2) 虽然也参与 CX(1,2)，但它不在最长链上，存在可被“藏起来”的调度余量。识别关键路径的意义在于：调度器应优先保障关键路径上的门尽早获得资源，非关键路径上的门可以适当延后，从而压缩整体完成时间。

并行性则来自 DAG 的“宽度”。同一时刻入度为 0 的节点集合越大，可并行的门越多。但并行不是无条件的：物理设备上可同时执行的双比特门数量受耦合器与串扰限制，单比特门也受控制通道数限制。因此，DAG 给出的并行性是逻辑上界，实际并行度还要与硬件约束取交集。

通信需求的提取

对拓扑映射而言，DAG 中最有价值的信息是通信需求：每个双比特门都要求其两个逻辑比特在物理上相邻（或通过路由可达）。把 DAG 中所有双比特门涉及的逻辑比特对收集起来，就得到一张“逻辑交互图”。这张图的边权可以取该比特对之间的双比特门数量，边权越大，说明这对逻辑比特交互越频繁，初始映射时越应把它们放在相邻物理比特上。

例如上例中，交互对为 (q0,q1) 与 (q1,q2)，各出现一次。若物理拓扑是一条 0—1—2—3 的链，把 q0、q1、q2 依次映射到物理 0、1、2，则两个 CX 都无需插入 SWAP；若映射为 q0→0、q1→2、q2→1，则 CX(0,1) 需要路由，代价上升。可见通信需求提取直接决定了初始映射的优劣。

依赖分析只关心“谁等谁”，不关心门的具体物理实现。把 DAG 与交互图分开维护，可以让映射阶段专注交互图，调度阶段专注 DAG，职责清晰、便于分别优化。

可执行的依赖分析流程

把上述内容整理成可复用的分析步骤，便于在代码或工具中实现：

解析门序列：按时间顺序读取每个门的类型与作用比特，记录门的持续时间（示例：单比特门 20 ns，CX 门 200 ns，测量 500 ns）。
维护比特指针：为每个逻辑比特保存“最近一次操作节点”，初始为空。
建边：对每个门，把它连接到其涉及的所有比特的最近节点；若某比特指针为空则无入边。随后把该门设为这些比特的新最近节点。
计算入度：统计每个节点的入边数，入度为 0 者进入就绪队列。
提取关键路径：在 DAG 上做最长路径计算，路径长度按门持续时间累加，得到关键路径节点集合。
提取通信需求：遍历所有双比特门，统计逻辑比特对的交互次数，形成交互图。
输出：DAG 邻接表、关键路径列表、交互图边权表，供映射与调度模块使用。

以一个更具体的示例说明参数如何影响结果：假设线路含 6 个 CX 门，交互对为 (q0,q1)×3、(q1,q2)×2、(q2,q3)×1，单比特门若干。若物理拓扑为 4 比特链，把 q0,q1,q2,q3 顺序映射即可让全部 CX 相邻，零 SWAP；若物理拓扑为环形，则 (q0,q3) 之间多一条边，但 (q0,q1) 等仍相邻，映射选择更灵活。交互次数最高的 (q0,q1) 应优先保证相邻，这是映射的硬约束。

注意：DAG 的边方向必须与时间顺序一致，否则会出现环，导致调度死锁。若线路中包含经典控制反馈（如测量结果控制后续门），需要把经典依赖也建模为边，不能只考虑量子比特依赖。

完成依赖分析后，后续的初始映射可以直接消费交互图，路由阶段可以按 DAG 的关键路径优先插入 SWAP，调度阶段则按入度就绪规则推进。可以说，DAG 与交互图是量子芯片编译流程中承上启下的两张“地图”：一张描述时间上的先后约束，一张描述空间上的相邻需求。把这两张图建准，拓扑映射与路由调度才有可靠的基础。