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

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

根据定义 7, 量子线路 LC 的总体路由代价如公式 (5) 所示, 其中, count(g(q i , q j )) 用于统计 LC 中作用在 q i 和
q j 上的双比特量子门总数.

∑
tcost(LC,DQC,π) = count(g(q i ,q j )).rcost[π(q i )][π(q j )] (5)
(q i ,q j )∈Q 2
公式 (5) 的值越小, 表明 π 越有利于将逻辑线路中频繁交互的逻辑量子比特对聚集在相同 QPU 上.

3.2 量子比特分布式映射算法
量子比特分布式映射方法的主要任务便是在所有可能的量子比特映射关系中找到使公式 (5) 取最小值的 π*,
如公式 (6) 所示. 其中 n 表示量子比特数目, S n 表示由所有可能量子比特映射关系构成的集合, 由于每个映射关系
可等价的视为一个 n 元素的全排列, 则 S n 可视为一个 n 阶置换群.

π = argmintcost(LC,DQC,π) (6)
∗
π∈s n
公式 (6) 定义的优化问题具有 O(n!) 规模的可行解空间, 因此很难通过暴力枚举法获得其中的最优初始映射.
在这种情况下, 可以借助元启发式算法在求解速度和精度上取得较好的平衡. 因此, 我们以模拟退火 [45] 为算法框
架, 并通过最速下降法对退火过程进行强化, 从而提出了一种量子比特分布式映射方法.
模拟退火 [45] 是一种常用的元启发式算法, 通过模拟固体退火过程, 在问题状态空间内进行寻优搜索, 其可以
概率的跳出局部最优并最终趋近于全局最优. 然而, 模拟退火算法探索问题状态空间的方式是完全随机的, 其在得
到某个局部最优解之前通常会遍历大量较差的解, 在迭代次数不够的情况下, 算法最终获得的解会存在质量不佳
或不稳定的情况. 为加速模拟退火趋近局域最优解的过程, 我们引入了一种基于最速下降的启发式算法. 该启发式
算法的基本思想是从一个给定的映射关系 π 出发, 以公式 (5) 为代价函数, 通过最速下降的方式不断交换 π 中的
两个不同元素, 使得频繁交互的逻辑量子比特逐渐“聚拢”至同一 QPU, 并最终生成量子比特映射的一个局部最优
解. 算法 1 给出了该算法的详细过程, 其以对换运算 p ij (交换 π 中的第 i 和第 j 个元素) 作为邻域算子对当前解 π
的邻域结构进行探索, 在邻域结构中搜索最小化公式 (5) 的对换操作 p uv , 并用 p u 更新当前解 π. 算法 1 将重复该
v
过程直至 π 为可达邻域内的局部最优解.
算法 1. 量子比特映射局部最优解生成算法.
输入: 映射关系 π, 逻辑线路 LC, 分布式模型 DQC;
输出: 可达邻域内的局部最优解 π*.

1. loc_opt=FALSE; //初始化循环控制条件
2. WHILE not loc_opt DO //循环至找到局部最优解
3. Δmax=0; //Δmax 记录代价函数值的最大降幅
4. FOR each possible p ij DO //p i 表示交换 π 的第 i 和第 j 个元素
j
5. Δ=tcost(π)–tcost(π⊕p ij ); //计算应 p i 后公式 (5) 的降幅
j
6. IF Δ>Δmax THEN //判断是否更新 Δmax
7. Δmax=Δ, u=i, v=j;
8. END IF
9. END FOR
10. IF Δmax>0 THEN //如果 Δmax 发生更新
11. π=π⊕p uv ; //更新当前 π
12. ELSE //否则将 loc_opt 设置为 TRUE
13. loc_opt=TRUE;
14. END IF
15. END WHILE