基于动态前瞻深度的量子线路映射研究

doi:10.3969/j.issn.1007-5461.2024.04.007

量子电子学报 ›› 2024, Vol. 41 ›› Issue (4): 626-637.doi: 10.3969/j.issn.1007-5461.2024.04.007

基于动态前瞻深度的量子线路映射研究

曹可欣, 陈新宇, 朱明强, 李响, 程学云*, 管致锦

( 南通大学信息科学技术学院, 江苏南通 226019 )

收稿日期:2022-07-11 修回日期:2022-08-17 出版日期:2024-07-28 发布日期:2024-07-28
通讯作者: E-mail: chen.xy@ntu.edu.cn E-mail:chen.xy@ntu.edu.cn
作者简介:曹可欣 ( 1999 - ), 女, 江苏南通人, 研究生, 主要从事物理受限的CNOT量子线路综合方面的研究。E-mail: 2846150646@qq.com
基金资助:
国家自然科学基金面上项目 (62072259), 江苏省研究生科研与实践创新计划项目 (SJCX21_1448), 面向超导计算的量子线路调度关键技术研究 (BK20221411)

Research on quantum circuit mapping based on dynamic look‑ahead depth

CAO Kexin, CHEN Xinyu, ZHU Mingqiang, LI Xiang, CHENG Xueyun*, GUAN Zhijin

( School of Information Science and Technology, Nantong University, Nantong 226019, China )

Received:2022-07-11 Revised:2022-08-17 Published:2024-07-28 Online:2024-07-28

摘要/Abstract

摘要： 随着量子计算技术的快速发展, 现在已经进入了噪声中型量子 (NISQ) 时代。但受限于当前的技术, 目前一个量子位只能与相邻的量子位直接交互。为了使量子线路能直接在 NISQ 设备上执行, 需要在逻辑线路中插入 SWAP门或使用桥门来近邻化量子位。为了减少量子线路映射中插入额外量子门的数量, 本文研究了基于动态前瞻的线路映射方法, 考虑了在拓展层中插入交换门的影响，优化了代价函数模型。通过模拟退火算法来确定插入交换门时的最佳前瞻深度, 以减少插入交换门的数量, 进而减少CNOT门的数量。实验结果表明, 与现有映射方法相比, 本文提出的算法减少了插入的CNOT门数, 平均优化率达到45.59%。

关键词: 量子计算, 量子映射, 动态前瞻, 前瞻深度

Abstract: With the rapid development of quantum computing technology, it has entered the noisy intermediate scale quantum (NISQ) era. However, due to the limitations of current technology, a qubit can only be directly interacted with adjacent qubits. In order to implement the logical quantum circuit directly on the NISQ device, it is necessary to insert SWAP gates or use bridge gates to make the qubit nearest neighbor. In order to reduce the number of additional quantum gates inserted in quantum circuit mapping, this paper investigates the dynamic look-ahead based circuit mapping method, considering the impact of inserting SWAP gates in the expansion layer and the cost function model is optimized. Then the best lookahead depth is determined when inserting SWAP gates through the simulated annealing algorithm, in order to reduce the number of inserted SWAP gates and thereby reduce the number of CNOT gates. The experimental results show that, compared with the existing mapping method, the proposed algorithm can effectively reduce the number of CNOT gates inserted in circuit mapping, and the average optimization rate reaches to 45.59%.

Key words: quantum computing, quantum mapping, dynamic look-ahead, look-ahead depth

中图分类号:

TP302.2

曹可欣, 陈新宇, 朱明强, 李响, 程学云, 管致锦. 基于动态前瞻深度的量子线路映射研究[J]. 量子电子学报, 2024, 41(4): 626-637.

CAO Kexin, CHEN Xinyu, ZHU Mingqiang, LI Xiang, CHENG Xueyun, GUAN Zhijin. Research on quantum circuit mapping based on dynamic look‑ahead depth[J]. Chinese Journal of Quantum Electronics, 2024, 41(4): 626-637.

参考文献

[1] Shor?P?W.?Polynomialtime?algorithms?for?prime?factorization?and?discrete?logarithms?on?a?quantum?computer[J].?SIAM?review,?1999,?41(2):?303-332.
[2] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 212-219.
[3] Peruzzo A, McClean J, Shadbolt P, et al. A variational eigenvalue solver on a photonic quantum processor[J]. Nature communications, 2014, 5(1): 1-7.
[4] https://quantum-computing.ibm.com/services 2022.4.20
https://www.cnet.com/pictures/take-a-look-at-googles-quantum-computing-technology 2022.4.20
https://www.intel.com/content/www/us/en/research/quantum-computing.html 2022.4.22
https://www.originqc.com.cn 2022.4.22
[5] Cao Y, Romero J, Olson J P, et al. Quantum chemistry in the age of quantum computing[J]. Chemical reviews, 2019, 119(19): 10856-10915.
[6] Niu S, Suau A, Staffelbach G, et al. A hardware-aware heuristic for the qubit mapping problem in the nisq era[J]. IEEE Transactions on Quantum Engineering, 2020, 1: 1-14.
[7] Rahman M M, Dueck G W, Chattopadhyay A, et al. Integrated Synthesis of Linear Nearest Neighbor Ancilla-Free MCT Circuits[C]// ISMVL 2016 IEEE International Symposium on Multiple-Valued Logic. IEEE, 2016:144-149.
[8] Ash-Saki A, Alam M, Ghosh S. QURE: Qubit re-allocation in noisy intermediate-scale quantum computers[C]//Proceedings of the 56th Annual Design Automation Conference 2019. 2019: 1-6.
[9] Zulehner A, Paler A, Wille R. An efficient methodology for mapping quantum circuits to the IBM QX architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38(7): 1226-1236.
[10] Guerreschi G G, Park J. Two-step approach to scheduling quantum circuits[J]. Quantum Science and Technology, 2018, 3(4): 045003.
[11] Siraichi M Y, Santos V F, Collange C, et al. Qubit allocation[C]//Proceedings of the 2018 International Symposium on Code Generation and Optimization. 2018: 113-125.
[12] Miller?D?M,?Soeken?M,?Drechsler?R.?Mapping?NCV?circuits?to?optimized?Clifford+T?circuits[C]//International?Conference?on?Reversible?Computation.?Springer,?Cham,?2014:?163-175.
[13] Li G, Ding Y, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C]//Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 2019: 1001-1014.
[14] Floyd R W. Algorithm 97: shortest path[J]. Communications of the ACM, 1962, 5(6): 345.
[15] Zhu P, Guan Z, Cheng X. A dynamic look-ahead heuristic for the qubit mapping problem of nisq computers[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4721-4735.

基于动态前瞻深度的量子线路映射研究

Research on quantum circuit mapping based on dynamic look‑ahead depth

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	吴限, 冯世光, 李绿周. 可逆电路综合与优化的若干研究进展[J]. 量子电子学报, 2024, 41(4): 565-577.
[2]	陈新宇 , 曹可欣 , 朱明强 , 程学云 , 冯世光 , 管致锦. 一种分布式量子计算中传输代价的优化方法[J]. 量子电子学报, 2024, 41(2): 318-329.
[3]	李响 , 姜一博 , 曹可欣 , 朱明强 , 程学云 , 朱鹏程 , 管致锦. 基于SVM的量子线路输出校准方法研究[J]. 量子电子学报, 2024, 41(2): 357-366.
[4]	杨辉 , 李志强 , 潘文杰 , 杨冬晗 , 吴希. 量子近似优化算法在数字分区问题中的应用[J]. 量子电子学报, 2024, 41(2): 367-377.
[5]	王升斌, 窦猛汉, 吴玉椿, 郭国平, 郭光灿 . 分布式量子计算研究进展[J]. 量子电子学报, 2024, 41(1): 1-25.
[6]	卫丽华 , 朱鹏程 , 管致锦 . 基于随机优化模型的量子线路映射辅助设计方法[J]. 量子电子学报, 2023, 40(6): 952-962.
[7]	季雯 , 叶宾 , . HHL 量子算法的普适量子线路设计[J]. 量子电子学报, 2023, 40(5): 747-758.
[8]	朱明强, 申文杰, 牛义仁, 张超, 程学云, 管致锦, 陈亮. 面向可靠性的CNOT量子线路最近邻综合[J]. 量子电子学报, 2023, 40(4): 560-569.
[9]	张超, 管致锦, 冯世光, 牛义仁, 朱明强. 一种二维架构下的量子电路布局与优化方法[J]. 量子电子学报, 2023, 40(4): 570-581.
[10]	李志强胡佳佳张威潘苏含戴娟杨冬晗吴希. 求解量子逻辑电路酉矩阵的快速方法[J]. 量子电子学报, 2020, 37(2): 222-228.
[11]	沈鸣燕1，程学云1,2，管致锦1*,陈加庆1，何娴雅1. 一种量子线路二维近邻实现方法[J]. 量子电子学报, 2019, 36(4): 476-482.
[12]	杨春蕾普杰信董永生刘中华梁灵飞. 一种基于量子机制的图像显著性检测方案[J]. J4, 2017, 34(3): 305-315.
[13]	陈月月, 刘呈普, 冯勋立. 克服腔QED中比特反转错误的无退相干子空间量子计算[J]. J4, 2016, 33(5): 553-560.
[14]	王新良杨茜惠靳翔. 基于量子计算的僵尸网络周期性通信行为检测算法[J]. J4, 2016, 33(2): 182-187.
[15]	王乐刘莹王岩岩赵生妹. 基于重叠法的(49,1,9)量子码CNOT门扩展矩形容错构造[J]. J4, 2014, 31(2): 179-185.