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

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

√
2
换成可执行门最多需调用 IQR 3 策略 O( s) 次; 每次调用 CQR 或 IQR 3 的时间复杂度为 O(n ), 且 LC 中共有|G|个
√ √
门, 则算法 3 最坏时间复杂度为 O(( n/s+ s)·n ·|G|) , 在本文中 s=10, 则算法 3 时间复杂度约为 O(|G|·n ) .
2.5
2
另外, 算法 3 返回的物理线路还可作如下优化. 作为算法 3 输入之一的初始映射关系由算法 2 生成, 该算法在
生成映射关系时综合考虑了位于量子线路左部的子线路, 而不仅是即将处理的第 L 0 层子线路. 因此, 在该初始映
射下通常在 L 0 层子线路中存在不可执行的量子门, 为将这些门转换成可执行门, 需要插入若干 ST 门或 SWAP 门,
而这些插入的辅助门不依赖于原始线路中的任何量子门, 因此可直接将这些辅助门更新后的映射关系当作初始映
射, 并将这些门从物理线路中删除, 如例 6 所示.
例 6: 给定由例 1 生成的物理线路, 如图 4 所示. 该物理线路最左边的 SWAP(v 02 , v 06 ) 和 ST(v 06 , v 18 ) 将映射关
系由最初的 π:{v 02 , v 10 , v 11 , v 12 }更新为{v 18 , v 10 , v 11 , v 12 }, 且这两个插入的辅助门并不依赖于原始量子线路中的任何
量子门, 因此将初始映射直接设定为 π:{v 18 , v 10 , v 11 , v 12 }, 并从物理线路中删除这两个辅助量子门.

5 实验与结果

本节通过基准量子线路库上的实验对本文所提分布式量子线路映射方法所需的路由代价 (即 ST 门数和
SWAP 门数) 以及时间性能作评价.

5.1 实验配置
本文实验采用了一种被广泛用于量子线路映射评价的基准线路库 [30−38] , 该基准库中包含了百余个量子线路,
每个量子线路均由 Clifford+T 门组成, CNOT 门是其中唯一的双比特量子门, 量子线路的规模从几十量子门到数
十万量子门不等, 线路包含的量子比特数目从 5 到 16 个不等, 为了便于测试分布式映射算法的性能, 我们从中选
取了量子比特数目超过 10 的部分线路进行测试. 另外, 所有实验除特别说明外均以如图 1 所示的分布式连通图作
为映射的目标量子平台.
为便于评价本文算法的总体性能, 通过对现有基于假想模型的分布式量子线路映射方法 [21,22] 的改造和适配构
造了一种基线算法 (简称 DQP). 文献 [21,22] 所提分布式映射方法的基本工作过程如下: 首先, 以最小化非局域门
数量为目标, 将逻辑量子比特划分成若干不相交的子集, 每个子集对应网络中的一个 QPU; 然后, 按序依次调度量
子线路中的量子门, 当遇到一个非局域门时, 通过隐形传态技术将该门的一个量子态移至另一个量子态所在的
QPU 上, 并在执行完这个门后, 立刻将该量子态移回原来位置, 本文将这种量子态传输策略称为往返传输策略. 这
些方法以隐形传态次数作为首要评价指标, 并假定网络中的 QPU 两两相互连通且每个 QPU 内的量子比特也是全
连通的, 此外在跨 QPU 传送量子态时未考虑 QPU 的容量问题. 为了匹配本文的分布式模型, 我们对 DQP 算法作
了如下适配: (1) 在划分逻辑量子比特时, 要求每个子集的元素个数最多不超过 QPU 内的数据量子比特个数, 并将
每一个子集中的逻辑量子比特随机映射到对应 QPU 内的数据量子比特上, 如此不仅可以建立完善的量子比特映
射关系, 还使得通信量子比特处于空闲态, 从而确保使用量子态往返传输策略时 QPU 总有剩余空间; (2) 在网络中
两个物理量子比特间传输量子态时, 以 ST 门和 SWAP 门组成的序列取代隐形传态, 即沿着两个量子比特间的最
短路径, 通过 ST 门和 SWAP 门实现量子态的往返传输 . 关于 DQP 算法进一步的知识请查阅文献 [21,22].
在实验中, 本文提出的分布式量子线路映射方法 (简称 DQM) 在生成初始映射时 (算法 2), 仅将逻辑量子比特
映射到 QPU 内的数据量子比特上, 如此不仅和 DQP 算法的做法保持一致, 还可以使得量子线路分布到更多
QPU 上, 更有利于评价分布式映射算法的路由代价. 另外, 在实验中, 公式 (7) 和公式 (9) 中的权重因子 ω 均等于
0.2, 前瞻层数 K 除特别说明外取值为 5; 算法 2 中总迭代次数 L 设定为 1 000 次.
本文所提算法使用 Python 语言实现, 并使用 Qiskit 作为读取基准量子线路的辅助工具. 所有实验运行的硬件
环境配置如下: Intel i7-4710HQ CPU, 8 GB 内存.

5.2 算法总体性能评价
首先将 DQP 算法和 DQM 算法进行比较, 从而检验 DQM 算法在路由开销以及时间开销等方面的性能, 实验
结果如表 2 所示. 表 2 的前 4 列分别给出了基准量子线路的相关信息, 包括序号、线路名称、量子比特数以及包