基于随机优化模型的量子线路映射辅助设计方法

doi:10.3969/j.issn.1007-5461.2023.06.015

量子电子学报 ›› 2023, Vol. 40 ›› Issue (6): 952-962.doi: 10.3969/j.issn.1007-5461.2023.06.015

基于随机优化模型的量子线路映射辅助设计方法

卫丽华 1, 朱鹏程 1,2*, 管致锦 2

( 1 宿迁学院信息与计算科学系, 江苏宿迁 223800; 2 南通大学信息科学技术学院, 江苏南通 226019 )

收稿日期:2022-01-10 修回日期:2022-04-09 出版日期:2023-11-28 发布日期:2023-11-28
通讯作者: E-mail: zhupcnt@163.com E-mail:E-mail: zhupcnt@163.com
作者简介:卫丽华 ( 1984 - ), 女, 江苏南通人, 硕士,讲师, 主要从事可逆逻辑综合、量子逻辑综合方面的研究。E-mail: angelirene@163.com
基金资助:
国家自然科学基金 (62072259), 江苏省自然科学基金 (BK20221411), 江苏省高校哲学社会科学项目(2022SJYB2416)

A computer⁃aided⁃design methodology for quantum circuit mapping based on stochastic optimization model

WEI Lihua1 , ZHU Pengcheng1,2*, GUAN Zhijin2

( 1 Department of Information and Computing Science, Suqian University, Suqian 223800, China; 2 College of Information Science and Technology, Nantong University, Nantong 226019, China )

Received:2022-01-10 Revised:2022-04-09 Published:2023-11-28 Online:2023-11-28

摘要/Abstract

摘要： 物理量子位之间的受限连通性是含噪中型量子计算设备面临的重要约束之一。量子线路映射方法通过插入量子交换 (SWAP) 门对量子线路进行变换，使得其中的每一个量子位交互操作均满足物理设备施加的受限连通约束。在噪声环境下，减少插入的SWAP门数对于提升量子计算成功率有重要意义。以最小化SWAP门数为目标, 结合随机搜索技术，提出了一种基于多迭代随机寻优模型的启发式量子线路映射优化方法。实验结果表明，该方法可以通过迭代大幅减少量子线路映射过程所需插入的量子门数，并有效降低结果物理线路对初始映射的依赖程度。

关键词: 量子计算, 量子线路映射, 含噪中型量子计算, 受限连通性, 随机优化

Abstract: The limited connectivity between physical qubits is one of the most important constraints for noisy intermediate-scale quantum (NISQ) computing devices. Quantum circuit mapping makes all qubits in quantum circuits exchange mutually by inserting SWAP gates to satisfy the restricted connectivity constraints of physical devices. In a noisy computing environment, reducing the number of inserted SWAP gates is of great significance to improve the success rate of quantum computing. In order to minimize the number of SWAP gates, a heuristic quantum circuit mapping algorithm is proposed, and then based on the heuristic algorithm and the random search technology, a multi-iterative stochastic optimization model for quantum circuit mapping is proposed. The experimental results show that the method can greatly reduce the number of quantum gates inserted during the quantum circuit mapping process, and effectively reduce the dependence of the resulting physical circuit on the initial mapping.

Key words: quantum computing, quantum circuit mapping, noisy intermediate-scale quantum computing, limited connectivity, stochastic optimization

中图分类号:

TP302.2

卫丽华 , 朱鹏程 , 管致锦 . 基于随机优化模型的量子线路映射辅助设计方法[J]. 量子电子学报, 2023, 40(6): 952-962.

WEI Lihua , ZHU Pengcheng, GUAN Zhijin. A computer⁃aided⁃design methodology for quantum circuit mapping based on stochastic optimization model[J]. Chinese Journal of Quantum Electronics, 2023, 40(6): 952-962.

参考文献

[1] IBM Quantum. IBM Quantum computer systems define the future of computing, [OL]. [2021-03-08]. https://www.ibm.com/quantum-computing/.
[2] Arute F, Arya K, Babbush R, et al. Quantum supremacy using a programmable superconducting processor[J]. Nature, 2019, 574(7779): 505-510.
[3] Zhong H S, Wang H, Deng Y H, et al. Quantum computational advantage using photons[J]. Science, 2020, 370(6523): 1460-1463.
[4] Wu Y, Bao W S, Cao S, et al. Strong quantum computational advantage using a superconducting quantum processor[J]. Physical review letters, 2021, 127(18): 180501.
[5] Preskill J. Quantum Computing in the NISQ era and beyond[J]. Quantum, 2018, 2: 79-98.
[6] Wille R, Fowler A, Naveh Y. Computer-aided design for quantum computation[C]//Proceedings of IEEE/ACM International Conf. on Computer-Aided Design (ICCAD). San Diego, CA :IEEE, 2018: 1-6.
[7] Amy M, Maslov D, Mosca M, et al. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(6): 818-830.
[8] Miller D M, Wille R, Sasanian Z. Elementary quantum gate realizations for multiple-control Toffoli gates[C]//Proceedings of of 41st IEEE International Symposium on Multiple-Valued Logic. Tuusula, Finland: IEEE, 2011: 288-293.
[9] H?ner T, Steiger D S, Svore K, et al. A software methodology for compiling quantum programs[J]. Quantum Science and Technology, 2018, 3(2): 020501.
[10] Cheng XY, Guan ZJ, Xu H, et al. The Nearest Neighbor Arrangement of Quantum Circuits Based on MCT Reversible Circuits[J]. Acta Electronica Sinica, 2018,46(08):1891-1897(in Chinese) .
程学云, 管致锦, 徐海, 等. 基于MCT可逆线路的量子线路近邻化排布[J]. 电子学报, 2018, 46(08): 1891-1897.
[11] Lu Y, Guan ZJ, Cheng XY, et al. Linear Nearest Neighbor Quantum Circuit Synthesis and Optimization Based on the Matrix[J]. Acta Electronica Sinica, 2018, 46(03): 688-694(in Chinese) .
鹿玉, 管致锦, 程学云, 等. 基于矩阵变换的线性最近邻量子线路综合与优化[J]. 电子学报, 2018, 46(03): 688-694.
[12] Wille R, Lye A, Drechsler R. Exact Reordering of Circuit Lines for Nearest Neighbor Quantum Architectures [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(12): 1818-1831.
[13] Siraichi M Y, Santos V F, Collange S, et al. Qubit allocation[C]//Proceedings of International Symposium on Code Generation and Optimization. New York, NY: ACM, 2018: 113-125.
[14] Botea A, Kishimoto A, Marinescu R. On the complexity of quantum circuit compilation[C]//Proceedings of 11th Annual Symposium on Combinatorial Search. Palo Alto, CA :AAAI, 2018: 138–142.
[15] Ding J, Yamashita S. Exact Synthesis of Nearest Neighbor Compliant Quantum Circuits in 2-D Architecture and Its Application to Large-Scale Circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(5): 1045-1058.
[16] Booth K, Do M, Beck J, et al. Comparing and integrating constraint programming and temporal planning for quantum circuit compilation[C]//Proceedings of International Conference on Automated Planning and Scheduling. Delft, Netherlands: TUDelft, 2018, 28(1):366-374.
[17] Venturelli D, Do M, Rieffel E G, et al. Temporal Planning for Compilation of Quantum Approximate Optimization Circuits[C]//Proceedings of 26th International Joint Conference on Artificial Intelligence IJCAI. Melbourne, Australia: IJCAI, 2017: 4440-4446.
[18] De Almeida A A A, Dueck G W, Da Silva A C R. Finding optimal qubit permutations for IBM's quantum computer architectures[C]//Proceedings of of 32nd Symposium on Integrated Circuits and Systems Design. S?o Paulo, Brazil: IEEE, 2019: 1-6.
[19] Wille R, Burgholzer L, Zulehner A. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations[C]//Proceedings of 56th ACM/IEEE Design Automation Conference. New York, NY: IEEE, 2019: 1-6.
[20] Wu B, He X, Yang S, et al. Optimization of CNOT circuits on topological superconducting processors[J]. arXiv:1910.14478, 2019, https://arxiv.org/abs/1910.14478.
[21] Nash B, Gheorghiu V, Mosca M. Quantum circuit optimizations for NISQ architectures[J]. Quantum Science and Technology, 2020, 5(2): 025010.
[22] Kissinger A, de Griend A M. CNOT circuit extraction for topologically-constrained quantum memories[J]. arXiv:1904.00633, 2019, https://arxiv.org/abs/1904.00633.
[23] Zhou X, Li S, Feng Y. Quantum circuit transformation based on simulated annealing and heuristic search[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(12): 4683-4694.
[24] Li S, Zhou X, Feng Y. Qubit mapping based on subgraph isomorphism and filtered depth-limited search[J]. IEEE Transactions on Computers, 2020, Early Access, https://ieeexplore.ieee.org/abstract/document/9194320.
[25] 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.
[26] Kole A, Hillmich S, Datta K, et al. Improved mapping of quantum circuits to IBM QX architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(10): 2375-2383.
[27] Kole A, Datta K, Sengupta I. A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(1): 182-192.
[28] Li G, Ding Y, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C]//Proceedings of the 24TH International Conference on Architectural Support for Programming Languages and Operating Systems. New York, NY: ACM 2019: 1001-1014.
[29] 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.
[30] Finigan W, Cubeddu M, Lively T, et al. Qubit allocation for noisy intermediate-scale quantum computers[J]. arXiv:1810.08291, 2018, https://arxiv.org/abs/1810.08291.
[31] Paler A. On the influence of initial qubit placement during NISQ circuit compilation[C]//Proceedings of International Workshop on Quantum Technology and Optimization Problems. Munich, Germany: Springer, 2019: 207-217.
[32] Nishio S, Pan Y, Satoh T, et al. Extracting success from IBM’s 20-qubit machines using error-aware compilation[J]. ACM Journal on Emerging Technologies in Computing Systems, 2020, 16(3): 1-25.
[33] Murali P, Baker J M, Javadi-Abhari A, et al. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers[C]//Proceedings of 24th International Conference on Architectural Support for Programming Languages and Operating Systems. New York, NY: ACM, 2019: 1015-1029.
[34] Tan B, Cong J. Optimality study of existing quantum computing layout synthesis tools[J]. IEEE Transactions on Computers, 2020, Early Access, https://ieeexplore.ieee.org/abstract/document/9140293.
[35] M. A. Nielsen and I. L. Chuang, Quantum Circuits[M]//Quantum Computation and Quantum Information, 10th ed. New York, NY: Cambridge Univ. Press, 2010:171-215.

基于随机优化模型的量子线路映射辅助设计方法

A computer⁃aided⁃design methodology for quantum circuit mapping based on stochastic optimization model

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价

[1]	牛义仁管致锦李海峰陆俊宇. 一种提高量子线路保真度的转换方法[J]. 量子电子学报, 2024, 41(1): 161-169.
[2]	王升斌窦猛汉吴玉椿郭国平郭光灿. 分布式量子计算研究进展[J]. 量子电子学报, 2024, 41(1): 1-25.
[3]	季雯 , 叶宾 , . HHL 量子算法的普适量子线路设计[J]. 量子电子学报, 2023, 40(5): 747-758.
[4]	朱明强, 申文杰, 牛义仁, 张超, 程学云, 管致锦, 陈亮. 面向可靠性的CNOT量子线路最近邻综合[J]. 量子电子学报, 2023, 40(4): 560-569.
[5]	李志强胡佳佳张威潘苏含戴娟杨冬晗吴希. 求解量子逻辑电路酉矩阵的快速方法[J]. 量子电子学报, 2020, 37(2): 222-228.
[6]	沈鸣燕1，程学云1,2，管致锦1*,陈加庆1，何娴雅1. 一种量子线路二维近邻实现方法[J]. 量子电子学报, 2019, 36(4): 476-482.
[7]	杨春蕾普杰信董永生刘中华梁灵飞. 一种基于量子机制的图像显著性检测方案[J]. J4, 2017, 34(3): 305-315.
[8]	陈月月, 刘呈普, 冯勋立. 克服腔QED中比特反转错误的无退相干子空间量子计算[J]. J4, 2016, 33(5): 553-560.
[9]	王新良杨茜惠靳翔. 基于量子计算的僵尸网络周期性通信行为检测算法[J]. J4, 2016, 33(2): 182-187.
[10]	王乐刘莹王岩岩赵生妹. 基于重叠法的(49,1,9)量子码CNOT门扩展矩形容错构造[J]. J4, 2014, 31(2): 179-185.
[11]	李胜张培林李兵周云川. 量子GA-PLS特征选择算法及其应用[J]. J4, 2014, 31(2): 194-201.
[12]	董阳，高山青，吴敏，吕洪君. 量子触发器的设计与优化[J]. J4, 2013, 30(6): 743-751.
[13]	张刚董萍. 腔耦合量子点系统的非常规几何量子计算[J]. J4, 2009, 26(4): 431-436.