一种二维架构下的量子电路布局与优化方法

doi:10.3969/j.issn.1007-5461.2023.04.016

量子电子学报 ›› 2023, Vol. 40 ›› Issue (4): 570-581.doi: 10.3969/j.issn.1007-5461.2023.04.016

一种二维架构下的量子电路布局与优化方法

张超 , 管致锦 *, 冯世光 , 牛义仁 , 朱明强

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

收稿日期:2021-04-12 修回日期:2021-05-28 出版日期:2023-07-28 发布日期:2023-07-28
通讯作者: E-mail: guan.zj@ntu.edu.cn E-mail:E-mail: guan.zj@ntu.edu.cn
作者简介:张超 ( 1996 - ), 江苏扬州人, 研究生, 主要从事计算机辅助量子逻辑综合方面的研究。 E-mail: chao_z_ntu@qq.com
基金资助:
国家自然科学基金面上项目 (62072259), 江苏省研究生科研与实践创新计划项目 (SJCX20_1151)

A quantum circuit layout and optimization method in two⁃dimensional architecture

ZHANG Chao , GUAN Zhijin *, FENG Shiguang , NIU Yiren , ZHU Mingqiang

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

Received:2021-04-12 Revised:2021-05-28 Published:2023-07-28 Online:2023-07-28

摘要/Abstract

摘要： 为解决将量子电路映射到二维架构并实现量子位近邻问题, 提出了一种二维架构下的量子电路布局与优化方法。首先根据量子门在量子电路中的执行顺序和相互作用, 提出基于量子位权重的深度优先搜索量子位映射次序, 再考虑到映射次序的已放入量子位、待放入量子位和未放入量子位的关系进行量子位的初始布局实现量子位的初始映射；进而对近邻过程中的相同前瞻量子代价的选择进行了优化, 再根据优化后的代价结果, 插入SWAP 门, 实现所有双量子门的最近邻。最后利用实验对提出的方法进行了验证, 并与已有的方法进行了比较。结果表明所提出方法在中小规模的基准电路上平均优化率达到18%, 在中大规模的基准电路上平均优化率达到17%。

关键词: 量子物理, 量子电路, 量子映射, 最近邻, 二维架构

Abstract: In order to solve the problem of mapping quantum circuits to two-dimensional architecture and realizing qubit nearest neighbor, a quantum circuit layout and optimization method in two-dimensional architecture is proposed. Firstly, according to the execution order and interaction of quantum gates in quantum circuit, a depth-first search qubit mapping order based on the weight of qubits is proposed, then the initial qubit mapping is realized by taking into account the relationship between the put qubits in the mapping order, the qubits to be put in and the unput qubits. Secondly, the selection of the same lookahead quantum cost in the nearest neighbor process is optimized, then according to the optimized cost results, SWAP gates are inserted to realize the nearest neighbor of all double quantum gates. Finally, the proposed method is verified by experiments and compared with the existing methods, and it is shown that the average optimization rate of the propsed method reaches 18% on the small and medium-sized Benchmark and 17% on the medium and large-scale Benchmark.

Key words: quantum physics, quantum circuits, quantum mapping, nearest neighbor, two-dimensional architecture

中图分类号:

TP302.2

张超, 管致锦, 冯世光, 牛义仁, 朱明强. 一种二维架构下的量子电路布局与优化方法[J]. 量子电子学报, 2023, 40(4): 570-581.

ZHANG Chao , GUAN Zhijin , FENG Shiguang , NIU Yiren , ZHU Mingqiang. A quantum circuit layout and optimization method in two⁃dimensional architecture[J]. Chinese Journal of Quantum Electronics, 2023, 40(4): 570-581.

参考文献

[1] Shor P W.Algorithms for quantum computation: Discrete logarithms and factoring[C]. proceeding of 35th Annual Symposium on Foundations of Computer Science.1994:124-134. [2] Grover L K.A fast quantum mechanical algorithm for database search[C]. 28th ACM Symposium on Theory of Computing, 1996:212-219. [3]Corcoles A D, Mageasan E, Srinivasan S J, et al.Demonstration of a quantum error detection code using a square lattice of four superconducting qubits[J].Nature Communication, 2015, 29(6):69-79 [4]Taylor J M, Petta J R, Johnson A C, Yacoby A, Marcus C M, Lukin M D.Relaxation,dephasing,and quantum control of electron spins in double quantum dots[J].Phys. Rev. B, 2007, 76(3):035-315 [5] IBM Q Experience. IBM Q Experience[EB/OL] [6] Shen Mingyan, Cheng Xueyun, Guan Zhijin, Chen Jiaqing, He xiaya .Realization method of two-dimensional nearest neighbor for quantum circuit [J] [J].Chinese Journal of Quantum Electronics, 2019, 36(4):476-482 [7] Wakaki HATTORI, YAMASHITA .Mapping a Quantum Circuit to 2D Nearest Neighbor Architecture by Changing the Gate Order [J][J].IEICE TRANSACTIONS on Information and Systems, 2019, 11( E102-D):2127-2134 [8]Zulehner A, Paler A, Wille R.An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures[J].IEEE Trans. on CAD of Integrated Circuits and Systems, 2019, 38(7):1226-1236 [9]Yuxin Zhang, Zhijin Guan, Longyong Ji, Qinfang Luan, Yizhen Wang.A Method of Mapping and Nearest Neighbor Optimization for 2-D Quantum Circuits[J].Quantum Information & Computing, 2020, 20(3-4):0194-0212 [10]Farghadan, Azim, Mohammadzadeh N.Quantum circuit physical design flow for 2D nearest-neighbor architectures[J].International journal of circuit theory and applications, 2017, 45(7):989-1000 [11]Cheng Xueyun, Tan Yingying, Guan Zhijin..An optimized simplification algorithm for reversible MCT circuits [J] [J].Chinese Journal of Quantum Electronics, 2017, 34(6):713-720 [12] Shafaei A, Saeedi M, Pedram M.Qubit placement to minimize communication overhead in 2D quantum architectures[C]. 19th Asia South Pacific Des.Autom. Conf., 2014 :495–500. [13]C. Lin,SSur-Kolay and N. K. Jha,.,PAQCS: physical design aware fault-tolerant quantum circuit synthesis[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2015, 23(7):12-21 [14] Xueyun Cheng, Zhijin Guan, and Pengcheng Zhu,.Nearest Neighbor Transformation of Quantum Circuits in 2D Architecture[J/OL][J].IEEE Access, 2020, 8:222466-222475 . [15]Prakash Murali, Jonathan, and M.Baker et al Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computer.[J].rXiv:1901.11054v1., s[J], :- [16]Shin Nishio, Yulu Pan, and Takahiko Satoh et al Extracting Success from IBM’s 20-Qubit Machines Using Error-Aware Compilatio.[J].rXiv:1903.10963v1., n[J], :- [17] Ash-Saki A, Alam M, Ghosh S.QURE: Qubit Re-allocation in Noisy IntermediateScale Quantum Computers[C] Proceedings of the 56th Annual Design Automation Conference 2019. ACM, 2019: 141. [18] IBM Q Experience.Accessed on: Mar. 20, 2021 [Online]. Available: https://www.research.ibm.com/ibm-q/technology/experience/ [19] Nielsen M A, Chuang I L.Quantum Computation and Quantum Information:10th Anniversary Edition [M] Cambridge University Press, 2011.

一种二维架构下的量子电路布局与优化方法

A quantum circuit layout and optimization method in two⁃dimensional architecture

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	吴希, 李志强∗. 基于 Cirq 的Grover 搜索算法的电路实现[J]. 量子电子学报, 2022, 39(3): 431-438.
[2]	戴娟∗, 李志强, 杨冬晗. 基于 Cirq 的Deutsch-Jozsa 电路综合算法[J]. 量子电子学报, 2022, 39(3): 439-445.
[3]	刘星灿哈斯花. 随机势场对氢原子能量本征问题的影响[J]. 量子电子学报, 2021, 38(4): 436-443.
[4]	江俊勤∗, 涂菁. 多势阱中电子的束缚态与能带形成研究[J]. 量子电子学报, 2021, 38(3): 316-326.
[5]	王艺臻, 管致锦, ∗, 管海宇. 基于预评价的量子电路线性最近邻综合算法[J]. 量子电子学报, 2021, 38(1): 75-85.
[6]	戴娟, 李志强, 潘苏含, 张威, 胡佳佳. 基于IBM Q的Deutsch-Jozsa算法实现[J]. 量子电子学报, 2020, 37(2): 202-209.
[7]	沈鸣燕1，程学云1,2，管致锦1*,陈加庆1，何娴雅1. 一种量子线路二维近邻实现方法[J]. 量子电子学报, 2019, 36(4): 476-482.
[8]	黄欣1，方卉1，霍艺芝1，巩龙延1,2*. 电子在长程跳跃随机势模型中的波粒二象性[J]. 量子电子学报, 2019, 36(2): 156-160.
[9]	刘洋，程学云，管致锦*，谈莹莹，王艺臻. 基于前瞻影响因素分析的量子电路综合算法[J]. 量子电子学报, 2019, 36(1): 40-46.
[10]	徐海管致锦程学云朱鹏程. 线性最近邻量子线路状态分析及最优逻辑综合[J]. J4, 2017, 34(2): 203-211.
[11]	吴德伟李响杨春燕苗强. 基于超导约瑟夫森结的双路径量子纠缠微波信号研究进展[J]. J4, 2017, 34(1): 1-8.
[12]	程学云，管致锦，丁卫平，朱鹏程. 基于有效布尔矩阵的线性最近邻量子电路综合?[J]. J4, 2016, 33(6): 743-750.
[13]	徐中辉姜芸李艳玲黄劲松陈宇光. 具有Stubs结构量子波导中电子的自旋传输特性[J]. J4, 2016, 33(5): 628-634.
[14]	陈实吕洪君解光军. B92协议一种新的量子电路设计与仿真[J]. J4, 2016, 33(1): 51-55.
[15]	罗国忠. 一维量子点阵列的自旋链上信息传输[J]. J4, 2015, 32(5): 595-599.