Page 486 - 《软件学报》2025年第5期

2386 软件学报 2025 年第 36 卷第 5 期

已被执行的情况下才可被调度. 根据 DAG 模型, 可以将量子线路分成若干层, 在原始 DAG 模型中没有前驱结点
的门构成第 1 层子线路 L 0 , 将第 1 层中所有量子门从 DAG 模型中删除得到新的 DAG 模型, 新模型中无前驱的量
子门构成第 2 层子线路 L 1 , 类似的可进一步得到 L 2 、L 3 等子线路层, 逻辑线路的最大层数也称为线路深度. 需说
明的是, 本文给出的示例线路主要用于说明分布式映射问题, 由于单比特量子门不受近邻交互约束制约, 因此我们
在示例线路中忽略了单比特量子门.

g 1 g 4
q 0
g 3
g 1
q 1
g 2
q 2
g 0 g 2 g 3 g 4
g 0
q 3
L 0 L 1 L 2 L 3
(a) 量子线路 (b) 量子线路的 DAG 模型
图 3 逻辑线路及其 DAG 表示

分布式量子线路映射的第 1 步, 即量子比特分布式映射, 用于建立逻辑量子比特到物理量子比特的映射关系.
逻辑量子比特数应小于或等于可用的物理量子比特数, 但通过向逻辑线路中增加额外的空量子比特, 总可以使得
逻辑量子比特数等于物理量子比特数. 因此, 为便于说明, 假定两者数目相等. 定义 1 中给出了规模为 n 的量子比
特映射关系的数学描述, 其中的物理量子比特集合包括了来自分布式模型中各 QPU 的全部可用量子比特.
定义 1. 量子比特映射关系. 给定逻辑量子比特集合 Q = {q 0 ,q 1 ,...,q n−1 } 和物理量子位集合 V D = {v 0 ,v 1 ,...,v n−1 } ,
量子比特映射是一个双射函数 π : Q → V D , 满足 π(q i )=π(q j ) 当且仅当 q i =q j .
量子比特映射 π 可表示为如公式 (3) 所示的置换形式, 其中第 1 行是逻辑量子比特序号, 而第 2 行是与逻辑
量子比特对应的物理量子比特序号.

( )
0 1 ... n−1
π = , 其中, 0 ⩽ j 0 , j 1 ,..., j n−1 < n (3)
j 0 j 1 ... j n−1
在公式 (3) 中, π(i)=j i 表示在映射 π 下逻辑量子比特 q i 将被分配给物理量子比特 v j i , 0 ⩽ i < n . 公式 (3) 还可
简写为如下的单行形式:

} (4)
π = {v j 0 ,v j 1 ,...,v j n−1
将最初的量子比特映射关系称为初始映射. 一旦给定初始映射, 便可以开始分布式量子线路映射的第 2 步, 即
量子态路由. 量子态路由按照 DAG 定义的依赖关系依次读取量子门, 若遇到不满足近邻交互约束的双比特量子
门, 则通过插入 SWAP 门或 ST 门对该门相关的两个量子态 (即逻辑量子比特) 进行路由, 直至这两个量子态移动
至同一 QPU 上的两个近邻物理量子比特上. 在进行量子态路由时, 本文将逻辑量子比特和量子态视为两个可相互
替换的等价概念. 为便于说明, 根据是否满足近邻交互约束以及是否可立即调度, 对量子门的不同类型做了如下
定义.
定义 2. 活跃门. 若逻辑线路中的一个量子门在该线路所对应 DAG 模型中无前驱节点 (即入度为 0), 则称该门
为活跃门.
一个量子门是否是活跃门和量子比特映射关系无关, 只取决于在其所属 DAG 模型中的位置, 图 3 中的 g 0 是
唯一的活跃门.
定义 3. 局域门和非局域门. 给定分布式连通图和量子比特映射关系, 若在该映射关系下, 一个量子门所作用
的物理量子比特均位于同一个 QPU 内, 则称该门为局域门, 否则称之为非局域门.
根据定义 3, 单比特量子门总是局域门, 而双比特量子门则根据其对应的物理量子比特分布情况可为局域门
或非局域门.
定义 4. 可执行门. 给定逻辑线路、分布式连通图以及量子比特映射关系, 若一个量子门既是活跃门又是局域
门, 并同时满足近邻交互约束, 则称该门为可执行门.