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

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

的结构, 网络拓扑和物理量子比特排列信息的缺失, 使得 DQP 生成的初始量子比特映射质量低于 DQM; (2) DQP
在移动量子态时所用的往返传输策略虽然简单易实现, 但在优化 SWAP 门和 ST 门数上存在很大局限性, 相反,
DQM 所用的 IQP 和 CQP 策略能在多个候选操作中选择最有利于降低路由代价的 SWAP 门或 ST 门, 从而减少所
需的 SWAP 门和 ST 门总数. 此外, DQM 和 DQP 在所有基准线路上所需的 SWAP 门数均普遍多于 ST 门数, 这主
要是由于无论是将非局域门转换成局域门还是将局域门转换成可执行门均需插入 SWAP 门, 而 ST 门仅在转换非
局域门时用到. 在时间开销方面, DQM 和 DQP 均是多项式时间复杂度算法, 且在进行分布式量子比特映射时均采
用了多迭代的算法模型, 因此两者的时间开销相近.

5.3 QPU 内量子态路由策略的性能评价
面向单个 QPU 芯片的量子线路映射在近几年得到了大量关注和研究, 但由于底层架构的巨大差异, 这些已有
方法无法直接适用于分布式场景. 然而, 仅将这些方法用于实现分布式映射场景下 QPU 内的量子态路由是显然可
行的. 本文通过将 Qiskit [42] 中的两种先进量子线路映射方法 (LookaheadSwap 和 SabreSwap) 分别集成至本文所提
的分布式量子态路由算法 (见算法 3), 实现了另外两种版本的分布式路由算法. 所用集成方式如下: 当算法 3 执行
到 QPU 内量子态路由时 (算法 3 第 11 行), 从当前量子线路为架构中的各 QPU 分别读取作用其上的由连续局域
门组成的最大待调度子线路, 并调用特定映射方法 (LookaheadSwap 或 SabreSwap) 完成各局域子线路向特定
QPU 的映射任务. LookaheadSwap 方法和文献 [36] 类似, 通过对映射决策树的深度搜索选择最有利于线路执行的
SWAP 门, 以下将集成 LookaheadSwap 的分布式量子态路由方法简称为 DQM_L 算法; SabreSwap 方法 [31] 采用了
一种前瞻性启发式搜索规则, 通过计算候选 SWAP 门的映射代价函数值, 选择待插入的 SWAP 门, 以下将包含
SabreSwap 的分布式量子态路由方法简称为 DQM_S 算法.
为评价 QPU 内量子态路由策略, 在所有基准测试线路上对 DQM、DQM_L 和 DQM_S 分别进行测试. 公平
起见, 3 种算法在每个基准线路上的实验均采用相同的初始映射:

for i in [0, 3] for j in [0, 5]} (11)
π = {v i j
即, 为量子线路中的各逻辑比特按以下顺序依次分配物理比特:{v 00 , v 01 , v 02 , v 03 , v 04 , v 05 , v 10 , v 11 , v 12 , …}.
后文图 7 给出了 3 种算法在所有基准线路 (见表 2) 上所需的平均 SWAP 门数、ST 门数和平均用时, 其中左
边的纵轴用于统计门数, 而右边的纵轴表示时间 (以 s 为单位). 从图 7 可知, 3 种算法所需的平均 ST 门数大致相
当, 这是由于三者采用了相同的 QPU 间量子态路由策略, 至于 ST 门数上的少量差异主要源于在平局情况下
QPU 间量子态路由策略所作的随机选择. 相反, 由于三者采用了不同的 QPU 内量子态路由策略, 其在平均 SWAP
门数存在较大差异. 即便 LookaheadSwap 和 SabreSwap 等方法在单 QPU 映射问题上表现优异, 但在分布式映射
场景下显然表现欠佳, 其分别对应的 DQM_L 和 DQM_S 算法在平均 SWAP 门数上均明显多于 DQM 算法. 经分
析原因如下: 在分布式映射进行到 QPU 内量子态路由进程时, 由于受非局域门的间隔, 在各 QPU 上即将调度的由
连续局域门构成的子线路通常是浅层子线路, 这些局域子线路极小的线路深度使得现有单 QPU 映射方法无法充
分发挥出所用深度搜索或前瞻性启发式搜索技术的优势; 另外, 由于这些单 QPU 映射方法并不区分通信量子比特
和数据量子比特, 因此在进行量子态路由时极易使一些待移出 QPU 的量子态远离通信量子比特, 从而增加了后
续 QPU 间量子态传输所需的 SWAP 门开销. 相反, DQM 算法基于整个分布式连通图构建量子态路由策略, 如公
式 (7) 所示的效应函数中所考虑的多层子线路并不会被非局域门打断, 从而保证了较强的前瞻能力. 从图 7 还可
知, DQM_L 算法的平均耗时远高于 DQM 和 DQM_S 算法, 这主要由于其采用的深度搜索策略, 在其默认配置中,
每次选择 SWAP 门时均需在决策树上向下探索 5 层, 而 DQM 和 DQM_S 算法均是根据启发式代价函数直接做出
决策. 综上, 相较 DQM_L 算法和 DQM_S 算法, DQM 算法在平均门数和时间性能上均表现更佳, 这也表明了在分
布式场景下进行 QPU 内量子态路由时感知量子态在其他 QPU 分布情况的重要性.

5.4 网络拓扑对算法性能的影响
网络拓扑是设计分布式量子计算系统时需要考虑的重要因素之一, 其对量子线路映射所需的路由代价同样有
着重要影响. 为了评价网络拓扑对本文 DQM 算法的性能影响, 我们构建了一个具有线性拓扑的网络. 除拓扑结构