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

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

算法 1 从一个任意给定的可行解出发, 可迅速找到其可达邻域空间内的局部最优解. 在算法 1 的每次循环中,
2
2
共需为 O(n ) 个对换操作计算公式 (5) 的值, 而计算公式 (5) 的时间复杂度为 O(n), 且算法 1 最多循环 O(n ) 次, 因
5
此算法 1 的时间复杂度为 O(n ).
算法 2 使用模拟退火过程不断探索和跳出由算法 1 产生的量子比特映射局部最优解, 从而逐步逼近全局最
优. 算法 2 采用了一种非均匀退火控制机制 [40] , 相关控制参数如表 1 所示, 其中 Δmin 和 Δavg 分别表示退火过程
中目标函数差值 Δ 的最小值和平均值, 在实际设定时我们通过将算法 2 的总迭代次数 L 设定为 100 对这两个参
数取值进行估计.

表 1 算法 2 模拟退火相关参数设定

参数 参数设定
总迭代次数 L=1000
初始温度 t 0 =0.3Δmin+0.7Δavg
终止温度 t 1 =0.7Δmin+0.3Δavg
温度衰减系数 β=(t 0 –t f )/Lt 0 t f
降温函数 t=t/(1+βt)

算法 2. 量子比特分布式映射算法.
输入: 逻辑线路 LC, 分布式连通图 DQC;
输出: 量子比特映射关系 π*, 即物理量子比特的排列.
1. set_parameters(); //根据表 1 设置参数 L, t 0 , t 1 , β
2. t=t 0 ; //将温度初始化为 t 0
3. π=π*=randomize(); //随机初始化 π 和 π*
4. FOR i=1 to L DO //最多迭代 L 次
5. π 1 =perturb(π); //对 π 作扰动得到 π 1 , 扰动由连续多次随机对换组成
6. π 1 =local_search(π 1 ); //调用算法 1, 从 π 1 出发寻找局部最优解
7. Δ=tcost(π 1 )–tcost(π 0 ); //计算 π 1 和 π 0 在代价函数上的差值
8. IF Δ<0 THEN
9. accept=TRUE; //接受 π 1
10. ELSE IF rand()<e –Δ/t THEN
11. accept=TRUE; //否则, 以 e –Δ/t 的概率接受 π 1
12. ELSE
13. accept=FALSE; //拒绝 π 1
14. END IF
15. IF accept THEN
16. π 0 =π 1 ; //将 π 0 更新为 π 1
17. π*=( tcost(π 0 )< tcost(π*)?π 0 , π*); //更新目前为止的最优解 π*
18. END IF
19. t=t/(1+βt); //降低温度
20. END FOR
算法 2 重点考虑了量子线路中量子比特的整体交互结构, 但一般而言量子线路的不同子部分会表现出不同的
交互特性. 由于量子线路的执行具有严格的时序性, 在构建初始映射时重点关注量子线路中最先执行的部分子线
路要比考虑整体线路更具实际意义. 因此, 在实验中我们以包含前 10n 个双比特量子门的子线路作为算法 2 的输