A Synthesis Algorithm of Quantum Circuit based on Look-ahead Influencing Factors

Abstract

Abstract: To resolve the problem of circuit synthesis and quantum cost optimization in linear nearest neighboring of quantum circuits, this paper proposed an algorithm that considers prospective influencing factors for synthesizing and optimizing the linear nearest neighbor quantum circuit. For any given non-nearest neighbor quantum circuit, the algorithm could separately measure the impact of operating the current quantum gate with different methods on the nearest neighbor cost of the subsequent quantum gate and reduce the number of SWAP gates required for the near-neighboring process of adjacent quantum gates, so as to facilitate constructing and optimizing the linear nearest neighbor quantum circuit. In this study, experiments were conducted with the typical Benchmark examples, and the results of the logic synthesis algorithms for linear nearest neighbor circuit were compared among the representative and comparable research findings. The results showed that the proposed optimization algorithm made a great improvement in adding the incremental SWAP gates. Specifically, among the 22 Benchmark examples, 18(81.82%) were positively optimized, with an average positive optimization rate of 18.32%, and an average optimization rate of 11.75%.

Key words: quantum circuit, linear nearest neighbor(LNN), look-ahead algorithm, reversible logic

Liu Yang, Cheng Xue-yun, Guan Zhi-jin*, Tan Ying-ying, Wang Yi-zhen. A Synthesis Algorithm of Quantum Circuit based on Look-ahead Influencing Factors[J]. Chinese Journal of Quantum Electronics.

References

[1] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C].Foundations of Computer Science,1994 Proceedings.Symposium on.IEEE, 2002:124-134. [2] Grover L K.A fast quantum mechanical algorithm for database search[C].Twenty-Eighth ACM Symposium on Theory of Computing. ACM, 1996:212-219. [3] Große D, Wille R, Dueck G W, et al. Exact Synthesis of Elementary Quantum Gate Circuits[J]. Journal of Multiple-Valued Logic & Soft Computing, 2009:283-300. [4] 程学云, 管致锦, 丁卫平,等. 基于有效布尔矩阵的线性最近邻量子电路综合[J]. 量子电子学报, 2016, 33(6):743-750. Cheng Xueyun, Guan Zhijin, Ding Weiping, et al. Linear nearest neighbor quantum circuit synthesis based on valid Boolean matrix[J]. Chinese Journal of Quantum Electronics, 2016, 33(6): 743-750. [5] Soeken M, Wille R, Hilken C, et al. Synthesis of reversible circuits with minimal lines for large functions[C].Design Automation Conference. IEEE, 2012:85-92. [6] Miller D M, Wille R, Sasanian Z. Elementary Quantum Gate Realizations for Multiple-Control Toffoli Gates[C].IEEE International Symposium on Multiple-Valued Logic. IEEE Computer Society, 2011:288-293. [7] Nickerson N H,Li Y, Benjamin S C. Topological quantum computing with a very noisy network and local error rates approaching one percent[J]. Nature Communications, 2012, 4(4):1756. [8] Saeedi M, Wille R, Drechsler R. Synthesis of quantum circuits for linear nearest neighbor architectures[J]. Quantum Information Processing,2012,10(3):355-377. [9] Hirata Y, Nakanishi M, Yamashita S, et al. An Efficient Method to Convert Arbitrary Quantum Circuits to Ones on a Linear Nearest Neighbor Architecture[C]. International Conference on Quantum, Nano and MICRO Technologies. IEEE, 2009:26-33. [10] Wille R, Lye A, Drechsler R. Exact Reordering of Circuit Lines for Nearest Neighbor Quantum Architectures[J].Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2014, 33(12):1818-1831. [11] Kole A, Datta K, Sengupta I. A Heuristic for Linear Nearest Neighbor Realization of Quantum Circuits by SWAP Gate Insertion Using N-Gate Lookahead. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2016,6(1):62–72. [12] Saeedi M, Wille R, Drechsler R. Synthesis of quantum circuits for linear nearest neighbor architectures[J]. Quantum Information Processing,2012,10(3):355-377.

[1]	ZHU Mingqiang , SHEN Wenjie , NIU Yiren , ZHANG Chao , CHENG Xueyun , GUAN Zhijin , CHEN Liang. Reliability⁃oriented nearest neighbor synthesis of CNOT quantum circuits [J]. Chinese Journal of Quantum Electronics, 2023, 40(4): 560-569.
[2]	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.
[3]	WU Xi, LI Zhiqiang∗. Circuit realization of Grover algorithm based on Cirq [J]. Chinese Journal of Quantum Electronics, 2022, 39(3): 431-438.
[4]	DAI Juan∗, LI Zhiqiang, YANG Donghan. Synthesis of Deutsch-Jozsa circuits based on Cirq [J]. Chinese Journal of Quantum Electronics, 2022, 39(3): 439-445.
[5]	WANG Yizhen, GUAN Zhijin, ∗, GUAN Haiyu. Linear nearest neighbor synthesis algorithm of quantum circuits based on pre-evaluation [J]. Chinese Journal of Quantum Electronics, 2021, 38(1): 75-85.
[6]	DAI Juan, LI Zhiqiang, PAN Suhan, ZHANG Wei, HU Jiajia. Deutsch-Jozsa algorithm realized on IBM Q [J]. Chinese Journal of Quantum Electronics, 2020, 37(2): 202-209.
[7]	SHEN Mingyan1, CHENG Xueyun1,2, GUAN Zhijin1*, CHEN Jiaqing1, HE Xianya1. A Realization Method of Two-Dimensional Nearest Neighbor for Quantum Circuit [J]. Chinese Journal of Quantum Electronics, 2019, 36(4): 476-482.
[8]	CHENG Xueyun, GUAN Zhijin, DING Weiping, ZHU Pengcheng. Linear nearest neighbor quantum circuit synthesis based on valid Boolean matrix [J]. J4, 2016, 33(6): 743-750.
[9]	CHEN Shi, LV Hongjun, XIE Guangjun. Design and simulation of quantum circuits of B92 QKD Protocol [J]. J4, 2016, 33(1): 51-55.
[10]	YANG Jie, TANG Qimei, CHEN Fulong, QI Xuemei, YE Heping. Design of Fault Tolerant Universal Shift Register Using Reversible Logic [J]. J4, 2015, 32(5): 600-606.
[11]	Wu Junqin, Lin Huiying. Scheme of N-qubit secret sharing based on four-particle cluster state [J]. J4, 2015, 32(4): 472-477.
[12]	HE Jin-feng1, GUAN Zhi-jin2, CHENG Xue-yun2, YU Ke-ren2, XU Ming-qiang3. Fault Fault Detection and Location for Quantum Circuits based on NCV gates [J]. J4, 2015, 32(2): 161-169.
[13]	LI Zhi-qiang, FENG Xiao-xia, CHEN Han-wu. Design of Barrel Shifters Based on Quantum Reversible Logic [J]. J4, 2014, 31(6): 720-727.
[14]	XU Ming-qiang, GUAN Zhi-jin, CHENG Xue-yun. A Universal Cascaded Method for Reversible Comparator [J]. J4, 2014, 31(5): 583-590.
[15]	QI Xue-mei, CHEN Fu-long , LUO Yong-long. Efficient fault tolerant reversible Hamming code encoding and detection circuits [J]. J4, 2013, 30(5): 586-593.