基于前瞻影响因素分析的量子电路综合算法

量子电子学报

基于前瞻影响因素分析的量子电路综合算法

刘洋，程学云，管致锦*，谈莹莹，王艺臻

南通大学计算机科学与技术学院，江苏南通 226019

出版日期:2019-01-28 发布日期:2019-01-17
通讯作者: guan.zj@ntu.edu.cn
作者简介:刘洋（1997-），男，江苏徐州，本科生，主要从事线性可逆逻辑综合方面研究。E-mail：345144117@qq.com
基金资助:
江苏省自然科学基金（Natural Science Foundation of Jiangsu Province, BK20151274）、江苏省高校自然科学研究面上项目(General Project of Natural Science Research of Jiangsu Higher School ,14KJB520033)、江苏省研究生科研与实践创新计划项目（Postgraduate Research & Practice Innovation Program of Jiangsu Province，KYCX17_1916）

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

Liu Yang, Cheng Xue-yun, Guan Zhi-jin*, Tan Ying-ying, Wang Yi-zhen

College of Computer Science and Technology, Nantong University, Nantong 226019, China

Published:2019-01-28 Online:2019-01-17

摘要/Abstract

摘要： 为了解决量子电路在线性近邻化过程中电路综合与量子代价优化问题，本文提出了一种考虑前瞻影响因素的线性最近邻量子电路综合与优化算法。该算法对任意给定的非最近邻量子电路，通过分别度量不同方法下操作当前量子门的过程对其后量子门的最近邻量子代价造成的影响，降低相邻量子门近邻化过程所需的SWAP门数量，从而达到构建并优化线性最近邻量子电路的要求。采用具有代表性的Benchmark例题进行实验，并以具有代表性和可比性的文献结论作为比较对象，对线性最近邻电路逻辑综合算法的结果进行比较，结果表明，本文的优化算法在添加交换门增量上有较大改进，22例Benchmark例题正优化达到18例，占比81.82%，平均正优化率为18.32%，平均优化率为11.75%。

关键词: 量子电路, 线性最近邻, 前瞻算法, 可逆逻辑

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

刘洋，程学云，管致锦*，谈莹莹，王艺臻. 基于前瞻影响因素分析的量子电路综合算法[J]. 量子电子学报.

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.

参考文献

[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]	张超, 管致锦, 冯世光, 牛义仁, 朱明强. 一种二维架构下的量子电路布局与优化方法[J]. 量子电子学报, 2023, 40(4): 570-581.
[2]	吴希, 李志强∗. 基于 Cirq 的Grover 搜索算法的电路实现[J]. 量子电子学报, 2022, 39(3): 431-438.
[3]	戴娟∗, 李志强, 杨冬晗. 基于 Cirq 的Deutsch-Jozsa 电路综合算法[J]. 量子电子学报, 2022, 39(3): 439-445.
[4]	王艺臻, 管致锦, ∗, 管海宇. 基于预评价的量子电路线性最近邻综合算法[J]. 量子电子学报, 2021, 38(1): 75-85.
[5]	戴娟, 李志强, 潘苏含, 张威, 胡佳佳. 基于IBM Q的Deutsch-Jozsa算法实现[J]. 量子电子学报, 2020, 37(2): 202-209.
[6]	徐海管致锦程学云朱鹏程. 线性最近邻量子线路状态分析及最优逻辑综合[J]. J4, 2017, 34(2): 203-211.
[7]	程学云，管致锦，丁卫平，朱鹏程. 基于有效布尔矩阵的线性最近邻量子电路综合?[J]. J4, 2016, 33(6): 743-750.
[8]	陈实吕洪君解光军. B92协议一种新的量子电路设计与仿真[J]. J4, 2016, 33(1): 51-55.
[9]	杨洁汤其妹陈付龙齐学梅叶和平. 一种容错可逆的通用移位寄存器设计[J]. J4, 2015, 32(5): 600-606.
[10]	何金凤1，管致锦2，程学云2 ，郁可人2，徐明强3. 基于NCV门的量子电路故障的检测与定位研究[J]. J4, 2015, 32(2): 161-169.
[11]	李志强冯小霞陈汉武. 基于量子可逆逻辑的桶型位移器设计[J]. J4, 2014, 31(6): 720-727.
[12]	徐明强管致锦程学云. 一种通用的可逆比较器级联方法[J]. J4, 2014, 31(5): 583-590.
[13]	齐学梅陈付龙罗永龙. 高效容错可逆的汉明码编码和检测电路[J]. J4, 2013, 30(5): 586-593.
[14]	吕洪君乐亮韩良顺解光军. 基于遗传算法的量子可逆逻辑电路综合方法研究[J]. J4, 2011, 28(5): 596-604.
[15]	吕洪君郭俊旺彭斐吴天昊解光军. 用基本两位量子逻辑门实现N位量子逻辑门的研究[J]. J4, 2010, 27(1): 26-30.