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

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

5
入. 算法 2 共需 L 次循环, 在每次循环内, 对算法 1 的调用是最耗时的操作, 因此算法 2 的时间复杂度为 O(L∙n ).

4 分布式量子态路由算法

本节将重点介绍构成分布式量子态路由算法, 包括 QPU 内量子态路由策略、QPU 间量子态路由策略以及量
子态路由整体策略.

4.1 QPU 内量子态路由策略
QPU 内量子态路由策略以最小化线路映射所需的 SWAP 门数为主要目标, 在分布式量子线路映射场景中, 存
在 3 种情形需要在 QPU 内部移动逻辑量子比特 (量子态). 第 1 种情形是, 在将某 QPU 上的一个逻辑量子比特/
量子态传输至另外一个 QPU 时, 该逻辑量子比特尚未处于通信量子比特上, 此时需要将该逻辑量子比特交换至同
一 QPU 上的通信量子比特, 将这种情形对应的量子态路由策略简称为 IQR 1 ; 第 2 种情形是, 某 QPU 上的一个通
信量子比特即将作为 ST 门的目标量子比特, 即接受从其他 QPU 传输而来的量子态, 但是该量子比特已被某个逻
辑量子比特占用, 此时为执行 ST 门需将某个空闲量子比特的量子态 ( |0⟩ 态) 交换至该通信量子比特, 将这种情形
对应的量子态路由策略简称为 IQR 2 ; 第 3 种情形是, 量子线路中当前活跃门是不满足近邻交互约束的局域门, 此
时为了执行这些局域门, 需要将其相关的两个逻辑量子比特移动至 QPU 内的近邻位置上, 将该情形对应的量子态
路由策略简称为 IQR 3 .
IQR 1 的实现相对简单, 首先找到在当前映射关系下该逻辑量子比特对应的物理量子比特, 然后沿着该物理量
子比特和相应通信量子比特之间的最短路径插入 SWAP 门, 即可将该逻辑量子比特交换至特定的通信量子比特,
如例 2 所示.
例 2: 给定如图 1 所示的分布式连通图和量子比特映射关系 π, 并假定 π(q)= v 18 , 即逻辑量子比特 q 位于计算
节点 M 1 的物理量子比特 v 1 上, 此时若要将 q 从 M 1 传输至 M 0 , 则首先要将 q 从 v 1 移至通信量子比特 v 18 , 由于
1
1
v 1 到 1 v 1 间的最短路径为: v 11 →v 10 →v 18 , 则插入 SWAP 门序列: {SWAP(v 11 , v 10 ), SWAP(v 10 , v 18 )}便可实现 q 的
8
移动.
IQR 2 要求当前 QPU 内至少存在一个空闲物理量子比特, 即至少存在一个尚未关联逻辑量子比特的物理量子
比特, 我们首先在这些空闲量子比特中找到距离通信量子比特最近的那个, 然后沿着该空闲量子比特和通信量子
比特之间的最短路径插入 SWAP 门, 从而将空闲量子比特上的 |0⟩ 态移动到通信量子比特, 如例 3 所示.
例 3: 给定如图 1 所示的分布式连通图, 假设即将执行 ST(v 18 , v 06 ), 但是 v 0 被某个逻辑量子比特占用, 若此时
6
M 0 上未被逻辑量子占用的空闲量子比特有{v 05 , v 07 , v 08 }, 其中 v 0 距离 v 0 最近, 它们之间的最短路径为:
6
5
v 05 →v 02 →v 06 , 则通过插入以下 SWAP 门序列: {SWAP(v 05 , v 02 ), SWAP(v 02 , v 06 )}, 可以将 |0⟩ 态从 v 0 交换至 v 06 , 从
5
而解除 v 0 的被占用状态, 为执行 ST 门做好准备.
6
IQR 3 用于将待调度的局域门转换成满足近邻交互约束的可执行门, 与 IQR 1 和 IQR 2 不同, IQR 3 不是一次性
插入多个 SWAP 门, 而是每次决策仅插入一个 SWAP 门, 通过多次决策使得所有考虑的局域门转换成可执行门,
其单次执行步骤如下所示: (1) 根据所考虑的局域门集合, 生成候选 SWAP 门集合 SW={SWAP(v 1 , v 2 )|v 1 或 v 2 至少
和一个局域门相关}; (2) 为集合 SW 中的每个 SWAP 门计算效应函数值 (如公式 (7) 所示), 并选择效应函数值最大
的 SWAP 门, 在出现平局情况时随机选取一个效应值最大的 SWAP 门; (3) 返回选中的 SWAP 门, 并相应的更新
映射关系. 公式 (7) 用于量化在映射关系 π 下 SWAP(v 1 , v 2 ) 对映射后续 K+1 层子线路所需路由代价的影响. 其中,
Δrcost(g, π) 用于计算在插入 SWAP 门后量子门 g 的路由代价减少值, 如公式 (8) 所示, τ 表示应用 SWAP 门后得
到新的映射关系, Δrcost 的最大取值为 1, 最小取值为−1.

∑ 1 K ∑∑
sw_eff(v 1 ,v 2 ,π) = ∆rcost(g,π)+ω· ∆rcost(g,π) (7)
K
g∈L 0 k=1 g∈L k

∆rcost(g(q i ,q j ),π) = rcost[π(q i )][π(q j )]−rcost[τ(q i )][τ(q j )] (8)
公式 (7) 不仅考虑了即将调度的 L 0 层子线路, 还同时考虑了后续 K 层子线路, 其等式右边第 1 部分量化了