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

朱鹏程 等: 面向分布式超导量子计算架构的量子线路映射 2393

设分布式模型共有 n 个量子比特总数, 其中每个 QPU 均包含 s 个量子比特, 则模型中共包含 n/s 个 QPU, 并
√ √
构成一个 n/s· n/s 的二维网格型网络拓扑. CQR 的第 1 步最多包含 4n 个候选 MT 操作, 因此第 2 步共需
√
2
O(n ) 时间确定待插入的 MT 操作; 第 3 步需要 O( n/s) 时间; 由于网络拓扑中所有 QPU 间的最短路径可以预先
√ √
确定, 因此第 4 步确定 path 所需时间为 O(1), 而 path 长度为 O( n/s) , 即第 6–9 步的循环次数最多为 O( n/s) ;
√
第 7 步 MTo 最多包含 s 个候选 MT 操作, 因此第 8 步需耗时 O(s∙n); 则第 6–9 步的循环共需耗时 O(s·n· n/s) ; 综
2
上, 一次调用 CQR 的时间复杂度为 O(n +n · s ) , 由于 s<n, CQR 的渐进时间复杂度可记为 O(n ).
0.5
1.5
2

4.3 总体路由策略及方法
本文提出的量子态路由方法严格遵循 DAG 模型定义的优先级关系依次读取和处理量子线路中的活跃门集
合, 直至量子线路中的所有量子门均成为满足物理约束的可执行门. 在当前映射关系下, 活跃门集合中的门可分
为 3 类: 可执行门、不可执行的局域门以及非局域门. 对于处于活跃态的这 3 类门, 量子态路由方法优先处理可执
行门, 即, 将可执行门从逻辑线路中删除, 并将其加入物理线路; 然后根据 QPU 间量子态路由策略依次插入 MT 宏
操作尽可能地将非局域门转换成局域门, 进而根据 QPU 内量子态路由策略依次插入 SWAP 门直至将局域门转换
成可执行门.
量子态总体路由策略及方法如算法 3 所示, 其中的第 6–10 步根据 CQR 策略对非局域门作转换, 需补充说明
的是, 为防止 CQR 策略生成的 MT 操作将原先的局域门转换为非局域门, 在调用 CQR 时将冻结局域门相关的量
子态, 即禁止移动这些量子态的 MT 操作成为 CQR 策略用到的候选操作. 但量子态的冻结可能会导致在某些极端
情况找不到候选 MT 操作对非局域门作进一步转换, 当检测到这种情况时, 我们会提前退出第 6–10 步的循环, 继
而进入处理局域门的环节.

算法 3. 分布式量子态路由算法.
输入: 逻辑线路 LC, 分布式模型 DQC, 初始映射关系 π;
输出: 物理线路 PC.

1. dag=gen_DAG(LC); //为 LC 生成 DAG 模型
2. WHILE dag≠NULL DO //循环直至 DAG 为空
3. acgs=get_active(dag); //读取 dag 中的活动门集合
4. (exg, loc, nloc)=partition_act(acgs, π, DM); //将 acgs 中的门分为 3 类: 可执行门 exg, 局域门 loc, 和非局域门 nloc
5. dag.remove(exg); PC.append(exg); //从 dag 中删除所有可执行门, 并将这些门加入物理线路
6. WHILE nloc≠NULL DO //使用 CQR 策略将非局域门转换成局域门
7. mtops=cqr(nloc); //调用一次 CQR 策略
8. PC.append(mtops.decompose()); //将 CQR 策略返回的 MT 宏操作分解成 SWAP 门和 ST 门, 并加入物理线路
9. π=π⊕mtops; //根据 CQR 返回的 MT 操作更新映射关系
10. END WHILE
11. swaps=iqr3(loc); //使用 IQR 3 策略处理局域门
12. PC.append(swaps); //将 IQR 3 策略返回的 SWAP 门插入物理线路
13. π=π⊕swaps; //根据 IQR 3 策略返回的 SWAP 门更新映射关系
14. END WHILE
给定量子线路 LC(Q, G), 设分布式模型共有 n 个量子比特总数, 且每个 QPU 均包含 s 个量子比特, 并构成一
√ √
个 n/s· n/s 的二维网络拓扑. 在最坏情况下, 算法 3 遍历的每个量子门均是非局域门, 网络拓扑中两个 QPU 间
√ √
的最大距离为 O( n/s) 的量级, 则为将一个非局域门转换成局域门, 最多需要调用 CQR 策略 O( n/s) 次; 另外, 若
√
假定 QPU 内量子比特同样按方形网格排列, 则两个物理量子比特的最大距离约为 O( s) 量级, 则将一个局域门转