含噪中型量子计算机的量子比特映射算法  

Qubit Mapping Algorithm for Noisy Intermediate-Scale Quantum Computers

作　　者：黄泓凯 张雪松[1] HUANG Hongkai;ZHANG Xuesong(China Academy of Electronics and Information Technology,Beijing 100041,China)

机构地区：[1]中国电子科学研究院,北京100041

出　　处：《计算机工程与应用》2024年第24期110-118,共9页Computer Engineering and Applications

摘　　要：由于量子硬件约束,能够实现双量子比特门的物理量子比特对是有限的。大多数量子程序需要插入额外量子门,通过改变逻辑量子比特到物理量子比特的映射关系实现在含噪中型量子计算机上执行。为了提高量子线路初始映射质量,降低算法复杂度及运行时间,提出一种基于交换门的优化双向启发式搜索算法。利用最近邻策略筛选出交换门候选队列,通过改进启发式成本函数评估候选交换门,减少交换门搜索空间和附加门数。结合量子线路结构特性,使用反向遍历方法更新初始映射策略,提高映射质量。该算法还适用于量子比特任意耦合的硬件设备。实验结果表明,与主流的IBM_QX算法、SPBHA算法和SAHA算法相比,该算法分别减少约73%、28%和20%的附加门数,执行时间减少约300%、80%和19%,提高了量子线路映射效率。Due to constrains of quantum hardware,the physical qubit pairs capable of implementing two-qubit gates are limited.Most quantum algorithms require to insert additional quantum gates to be executed on NISQ(noisy intermediate-scale quantum)computers by altering the mapping relationship between logical qubits and physical qubits.To improve the quality of initial mapping of quantum circuits,and reduce algorithm complexity and execution time,a SWAP-based opti-mization bidirectional heuristic search algorithm is proposed.The algorithm utilizes a nearest neighbor strategy to filter out a candidate queue of SWAP gates.To reduce the search space and the number of additional gates,the algorithm evalu-ates candidates of SWAP gates by enhancing the heuristic cost function.Considering the characteristics of the quantum cir-cuit structure,this algorithm uses a reverse traversal method to enhance mapping quality with updating initial mapping strategy.Moreover,this algorithm is applicable to hardware devices with arbitrary coupling of qubits.Experimental results demonstrate that compared to mainstream IBM_QX,SPBHA and SAHA algorithms,this algorithm reduces the number of additional gates by approximately 73%,28%and 20%,respectively,and decreases execution time by around 300%,80%and 19%,improving the efficiency of quantum circuit mapping.

关 键 词：量子线路 初始映射 启发式搜索 反向遍历 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]