基于预评价的量子电路线性最近邻综合算法

量子电子学报 ›› 2021, Vol. 38 ›› Issue (1): 75-85.

基于预评价的量子电路线性最近邻综合算法

王艺臻1, 管致锦1;2∗, 管海宇1

1 南通大学信息科学技术学院, 江苏南通226019; 2 江苏省专用集成电路重点实验室, 江苏南通226019

收稿日期:2019-12-26 修回日期:2020-02-14 出版日期:2021-01-28 发布日期:2021-02-01
通讯作者: E-mail: guan.zj@ntu.edu.cn E-mail:guan.zj@ntu.edu.cn
作者简介:王艺臻( 1996 - ), 女, 江苏南通人, 研究生, 主要从事量子电路综合与二维量子电路近邻化方面的研究。 E-mail: W−yz1996@hotmail.com
基金资助:
Supported by National Natural Science Foundation of China (国家自然科学基金, 62072259), Natural Science Foundation of Jiangsu Province (江苏省自然科学基金, BK20151274), Postgraduate Research and Practice Innovation Program of Jiangsu Province (江苏省研究生科研与实践创新计划项目, KYCX17−1916)

Linear nearest neighbor synthesis algorithm of quantum circuits based on pre-evaluation

WANG Yizhen1, GUAN Zhijin1;2∗, GUAN Haiyu1

1 College of Information Science and Technology, Nantong University, Nantong 226019, China; 2 Jiangsu Key Laboratory of Asic Design, Nantong University, Nantong 226019, China

Received:2019-12-26 Revised:2020-02-14 Published:2021-01-28 Online:2021-02-01

摘要/Abstract

摘要： 线性最近邻(LNN) 量子电路是一种重要的量子电路架构, 它为量子电路的物理实现奠定了基础。为了构造LNN 量子逻辑电路, 提出了一种基于预评价的量子电路线性最近邻逻辑综合算法。该算法首先对部分非近邻量子电路进行全局换线; 接着启发式地对换线后的量子电路进行评价, 通过求解最小混乱值找到最近邻代价最小的量子电路集; 最后添加交换门, 以最少的量子代价将该量子电路转换为最近邻结构。该算法通过预评价, 一方面可以准确计算出量子电路中是否具有可删除的冗余交换门并删除之; 另一方面使每一个非近邻量子门转化为LNN 量子门时添加交换门的数量最小, 进而得到量子代价最小的量子电路。实验结果表明, 与已知算法相比, 该算法能以更低的量子电路平均门数、更高的量子代价优化率适用于更广范围内的量子电路近邻化。

关键词: 量子电路, 线性最近邻, 交换门, 量子代价

Abstract: Linear nearest neighbor (LNN) quantum circuit is an important quantum circuit architecture, which lays a foundation for the physical realization of quantum circuit. In order to construct LNN quantum logic circuits, a linear nearest neighbor logic synthesis algorithm based on pre-evaluation is proposed. In this algorithm, partial non-nearest neighbor quantum circuits are globally reordered firstly, then the reordered quantum circuits are evaluated by heuristic method, and the set of quantum circuits with the lowest nearest neighbor cost is found by computing the minimum chaos value. Finally, SWAP gates are added to convert the quantum circuit to a nearest neighbor structure with the lowest quantum cost. Through pre-evaluation, on the one hand, the algorithm can accurately calculate whether there are redundant SWAP gates that can be deleted in the quantum circuit and delete them. On the other hand, it can minimize the number of SWAP gates added when each non-nearst neighbor quantum gate is converted into LNN quantum gate, and then the quantum circuit with the lowest quantum cost is obtained. The experimental results show that compared with the known algorithm, the proposed algorithm has less average gates, higher optimization rate of quantum cost and a wider application range.

Key words: quantum circuit, linear nearest neighbor, SWAP gate, quantum cost

中图分类号:

TP302.2

王艺臻, 管致锦, ∗, 管海宇. 基于预评价的量子电路线性最近邻综合算法[J]. 量子电子学报, 2021, 38(1): 75-85.

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.

参考文献 12

[1]	Cheung D, Maslov D, Severini S. Translation techniques between quantum circuit architectures [C]. Workshop on Quantum
	Information Processing, 2007.
[2]	Hollenberg L C L, Greentree A D, Fowler A G, et al. Two-dimensional architectures for donor-based quantum computing [J].
	Physical Review B, 2006, 74(4): 45-311.
[3]	Chakrabarti A, Surkolay S, Chaudhury A. Linear nearest neighbor synthesis of reversible circuits by graph partitioning [OL].
20	11, http://arxiv.org/pdf/1112.0564v2.pdf.
[4]	Saeedi M, Wille R, Drechsler R. Synthesis of quantum circuits for linear nearest neighbor architectures [J]. Quantum Information
	Processing, 2011, 10(3): 355-377.
[5]	Barenco A, Bennett C H, Cleve R, et al. Elementary gates for quantum computation [J]. Physical Review A, 1995, 52(5):
34	57-3467.
[6]	Lee S, Lee S J, Kim T. The cost of quantum gate primitives [J]. Journal of Multiple-Valued Logic and Soft Computing, 2006,
12	(5): 561-573.
[7]	Wille R, Lye A, Drechsler R. Optimal SWAP gate insertion for nearest neighbor quantum circuits [C]. 19th Asia and South
	Pacific Design Automation Conference (ASP-DAC), 2014.
[8]	Maslov D, Miller D M. Comparison of the cost metrics through investigation of the relation between optimal NCV and optimal
	NCT three-qubit reversible circuits [J]. IET Computers & Digital Techniques, 2007, 1(2): 98-104.
[9]	Hirata Y, Nakashima Y, Nakanishi M, 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, 2009: 26-33.
[10]	Shafaei A, Saeedi M, Pedram M. Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures
[C]	Design Automation Conference, New York, NY, USA, 2013.
[11]	Maslov D, Dueck G W, Miller D M, et al. Quantum circuit simplification and level compaction [J]. IEEE Transactions on
	Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(3): 436-444.
[12]	Wille R, Gro D, Teuber L, et al. RevLib: An online resource for reversible functions and reversible circuits [C]. Proceedings
	of the International Symposium on Multiple-Valued Logic, 2008: 220-225.

[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]	戴娟, 李志强, 潘苏含, 张威, 胡佳佳. 基于IBM Q的Deutsch-Jozsa算法实现[J]. 量子电子学报, 2020, 37(2): 202-209.
[5]	刘洋，程学云，管致锦*，谈莹莹，王艺臻. 基于前瞻影响因素分析的量子电路综合算法[J]. 量子电子学报, 2019, 36(1): 40-46.
[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]	何金凤1，管致锦2，程学云2 ，郁可人2，徐明强3. 基于NCV门的量子电路故障的检测与定位研究[J]. J4, 2015, 32(2): 161-169.
[10]	李志强冯小霞陈汉武. 基于量子可逆逻辑的桶型位移器设计[J]. J4, 2014, 31(6): 720-727.
[11]	徐明强管致锦程学云. 一种通用的可逆比较器级联方法[J]. J4, 2014, 31(5): 583-590.
[12]	吕洪君乐亮韩良顺解光军. 基于遗传算法的量子可逆逻辑电路综合方法研究[J]. J4, 2011, 28(5): 596-604.
[13]	吕洪君郭俊旺彭斐吴天昊解光军. 用基本两位量子逻辑门实现N位量子逻辑门的研究[J]. J4, 2010, 27(1): 26-30.
[14]	吕洪君彭斐吴天昊解光军. 非可逆逻辑门的量子可逆实现研究[J]. J4, 2009, 26(6): 668-674.