面向二维近邻架构的启发式量子线路映射算法

摘要：为解决最近邻交互约束下量子线路到二维量子计算拓扑架构的映射问题，对量子比特的初始映射策略和动态路由策略进行了研究。以降低辅助量子门数（即SWAP门）为目标，构建了量子比特的映射权重系数，并基于映射权重提出了量子比特的初始映射算法；建立了基于双层展望窗口的代价函数，并基于该代价函数提出了一种启发式量子线路映射方法。实验结果表明，相较同类算法，本文算法平均减少了26.88%的辅助量子门数。

关键词：量子线路；量子比特；线路映射；最近邻约束；量子比特路由

中图分类号：TP301.6 文献标识码：A文章编号：1009-3044（2023）28-0010-04

0 引言

近年来，量子计算技术发展迅猛，IBM[1]、Google[2]以及中国科学技术大学[3-4]等多个科研机构相继发布了多种量子计算原型设备。这些设备由于量子比特资源有限以及量子操作易受噪声影响，通常也被称为中等规模带噪声量子设备[5]，简称为NISQ（NoisyIntermediate-Scale Quantum）设备。

在这些NISQ设备上，每个物理量子比特仅允许和在设备拓扑结构中与其位置相邻的比特进行交互，这种约束被称为最近邻交互约束。最近邻交互约束要求量子线路中的双比特量子门仅允许作用在一对相邻的物理量子比特上，但是量子线路在设计时并未考虑物理设备上的最近邻约束，导致量子线路通常无法直接在NISQ设备上运行。

为了在NISQ设备上运行量子线路，需要通过插入辅助量子门（如SWAP门）的方式使得量子线路中双比特量子门均满足最近邻交互约束，将这种适配物理设备近邻交互约束所需的量子线路变换称为量子线路映射。量子线路映射对量子计算的实现代价和成功率有着重要影响，其是量子计算基础核心软件中必不可缺的组件。

1 相关工作

早期的量子线路映射研究主要面向此类一维的线性最近邻架构[6-11]，但随着量子计算技术的发展，目前基于超导电路以及离子阱等技术的量子计算设备通常采用二维最近邻架构，即量子比特分布在二维的平面架构图中。二维最近邻架构更复杂的连通性使得此前面向线性最近邻架构的量子线路映射方法通常不能直接适用于二维近邻架构。二维近邻架构上的量子线路映射已被证明是一种具有NP完全复杂性的计算难题[12]，目前关于面向二维架构的量子线路映射仍处于探索阶段，已有的研究存在较多有待完善之处。文献[12-13]将量子线路映射问题转换为PBO（pseudo Boolean optimization）问题，并通过SAT（Bool⁃ean satisfiability， SAT）/SMT（satisfiability modulo theo⁃ries）求解器进行求解；文献[14-15]将映射问题形式化为CP（Constrained Planning）问题，并通过相应的TP/CP 算法进行求解。以上方法由于指数级的时间复杂度，通常仅适用于求解规模极小的量子线路映射问题。IBM的量子计算软件包Qiskit[16]提供了几种适用于大规模量子线路的启发式映射算法，其中性能最好的一种映射算法（简称SABRE）源于文献[17]，该方法基于对量子线路的正反向遍历技术对量子比特初始分配作全局优化，并构建了一种具有前瞻能力的加权代价函数和启发式映射规则。文献[12]的研究表明，现有的启发式方法由于其在搜索策略方面的局限性，仍存在很大的优化空间，特别是在较大型量子计算设备上，所得结果和最优结果之间的差距达5～45倍。

量子线路映射所需的辅助量子门数对量子线路的执行时间开销和成功率有着重要影响，为了在现有研究基础上进一步减少量子门数，本文对量子比特的初始分配策略和量子比特的动态路由策略进行了研究，并提出了基于量子比特权重优先级的初始映射算法和基于双重展望窗口的量子比特路由算法，实验结果表明，该方法可以有效降低映射插入的SWAP门数。