基于新型量子逻辑门库的最优NCV三量子电路快速综合算法

doi:10.3969/j.issn.0372-2112.2013.04.011

电子学报 ›› 2013, Vol. 41 ›› Issue (4): 690-697.DOI: 10.3969/j.issn.0372-2112.2013.04.011

基于新型量子逻辑门库的最优NCV三量子电路快速综合算法

李志强¹, 陈汉武², 刘文杰², 薛希玲², 肖芳英²

1. 扬州大学信息工程学院,江苏扬州 225009;
2. 东南大学计算机科学与工程学院,江苏南京 210096

收稿日期:2011-04-06 修回日期:2012-11-07 出版日期:2013-04-25
- 作者简介:
- 李志强 男.1974年5月出生,江苏姜堰人.扬州大学副教授,硕士生导师,2011年在东南大学计算机科学与工程学院获工学博士学位,主要从事量子计算、可逆电路综合等方面的研究工作. E-mail:zqli@yzu.edu.cn 陈汉武 男.1955年11月出生,南京人.东南大学教授、博士生导师.2000年3月获日本国立山口大学大学院理工学研究科智能情报专业理工学博士学位.主要从事量子计算、信息论等方面的研究工作. E-mail:hw_chen@seu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61070240,No.60572071,No.61170321); 江苏省高校自然科学基金 (No.10KJB520021)

Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library

LI Zhi-qiang¹, CHEN Han-wu², LIU Wen-jie², XUE Xi-ling², XIAO Fang-ying²

1. College of Information Engineering, Yangzhou University, Yangzhou, Jiangsu 225009, China;
2. School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China

Received:2011-04-06 Revised:2012-11-07 Online:2013-04-25 Published:2013-04-25

摘要/Abstract

摘要： 许多量子电路综合算法由于指数级时间与空间复杂度,只能用可逆逻辑门综合3量子逻辑电路,仅有少数算法实现用量子非门,控制非门,控制V门与控制V⁺门(NCV)综合3量子逻辑电路,主要方法是将电路综合问题简化为四值逻辑综合问题.本文提出用NCV门构造新型量子逻辑门库,该库与NCV门库在综合最优3量子逻辑电路上等价,因此又可将四值逻辑综合问题进一步简化为更易求解的二值逻辑综合问题,使用基于完备Hash函数的3量子电路快速综合算法,快速生成全部最优的3量子逻辑电路,以最小代价综合电路的平均速度是目前最好结果Maslov 2007的近127倍.

关键词: 可逆逻辑, NCV门库, 多值逻辑, 完备Hash函数, 量子代价

Abstract: Owing to the exponential nature of the memory or run-time complexity,many existing methods can only synthesize 3-qubit logic circuits using quantum logic gate library,however,a few can optimally synthesize 3-qubit logic circuits for quantum NOT,CNOT,Controlled-V and Controlled-V+(NCV)gates,the key approach reduces the NCV quantum circuit synthesis problem to four-valued logic synthesis.This paper proposes using NCV gates to create a new quantum logic gate library,which is exactly the same as NCV gate library in the synthesis of all optimal 3-qubit circuits,thus it also reduces the four-valued logic synthesis to easily solved two-valued logic synthesis.We present a 3-qubit efficient synthesis algorithms based on perfect hash function,which can quickly construct all optimal 3-qubit circuits--the average speed that synthesizes circuits with minimum cost is nearly 127 times faster than that of the best result of Maslov 2007.

Key words: reversible logic, NCV gate library, multiple-valued logic, perfect hash function, quantum cost

中图分类号:

TN911.23

李志强, 陈汉武, 刘文杰, 薛希玲, 肖芳英. 基于新型量子逻辑门库的最优NCV三量子电路快速综合算法[J]. 电子学报, 2013, 41(4): 690-697.

LI Zhi-qiang, CHEN Han-wu, LIU Wen-jie, XUE Xi-ling, XIAO Fang-ying. Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library[J]. Acta Electronica Sinica, 2013, 41(4): 690-697.

参考文献

[1] R Feynman.Quantum mechanical computers[J].Optic News,1986,16(6):1120.
[2] E Fredkin,T Toffoli.Conservative logic[J].International Journal of Theoretical Physics,1982,21(3):219-253.
[3] D Maslov,G W Dueck,et al.Toffoli network synthesis with templates[J].IEEE Tran sactions on CAD,2005,24(6):807-817.
[4] P Gupta,A Agrawa,N K Jha.An algorithm for synthesis of reversible logic circuits [J].IEEE Transactions on CAD,2006,25(11):807-817.
[5] 李志强,陈汉武.量子可逆逻辑电路最小代价综合算法[J].东南大学学报,2008,38(2):249 -254. Z Q Li,H W Chen.Synthetic algorithm for reversible logic circuits of quantum wit h minimal cost[J].Journal of Southeast University,2008,38(2):249-254.(in Chine se)
[6] V V Shende,A K Prasad,et al.Synthesis of reversible logic circuits[J].IEEE Tra nsactions on CAD,2003,22(6):723-729.
[7] G W Yang,X Song,et al.Fast synthesis of exact minimal reversible circuits using group theory[A].Proceedings of the 10th Asia and South Pacific Design Automati on Conference[C].Shanghai,China:IEEE Press,2005.18-21.
[8] W N N Hung,X Song,G W Yang,J Yang,M Perkowski.Optimal synthesis of multiple outp ut boolean functions using a set of quantum gates by symbolic reach ability anal ysis[J].IEEE Transactions on CAD,2006,25(9):1652-1663.
[9] G W Yang,W N N Hung,X Song,M Perkowski.Exact synthesis of 3-qubit quantum circu its from non-binary quantum gates using multiple-valued logic and group theory [A].Proceedings of DATE 2005[C].Munich,Germany:IEEE Press,2005.434-435.
[10] D Maslov,D M Miller.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.
[11] G W Yang,X Song,M Perkowski,W N N Hung,J Biamonte,Z Tang.Four-level realization of 3-qubit reversible functions[J].IET Computers & Digital Techniques,2007,1 (4):382-388.
[12] Z Q Li,H W Chen,B W Xu,et al.Fast algorithm for 4-qubit reversible logic circui ts synthesis[A].Proceedings of WCCI 2008[C].Hong Kong:IEEE Press,2008.300-30 6.
[13] 李志强,陈汉武,等.四量子可逆逻辑电路快速综合算法[J].电子学报,2008,36(11):2081-2 089. LI Zhi-qiang,CHEN Han-wu,et al.Fast algorithms for 4-qubit reversible logic c ircuits synthesis[J].Acta Electronica Sinica,2008,36(11):2081-2089.(in Chinese )
[14] 杨忠明,陈汉武,等.基于二分法量子可逆逻辑电路综合[J].电子学报,2012,40(5):1045-10 49. YANG Zhong-ming,CHEN Han-wu,et al.Qubits reversible logic circuits synthesis b ased on bisection method[J].Acta Electronica Sinica,2012,40(5):1045-1049.(in C hinese)

[1]	吴钰, 王伦耀, 储著飞, 夏银水. 一种功能可配置的可逆触发器设计[J]. 电子学报, 2022, 50(6): 1466-1471.
[2]	吴钰, 张莹, 王伦耀, 储著飞, 夏银水. 一种可逆有限状态机的电路设计[J]. 电子学报, 2020, 48(11): 2226-2232.
[3]	常丽, 朱宇祥, 蒋辉. 量子全加器设计[J]. 电子学报, 2019, 47(9): 1863-1867.
[4]	鹿玉, 管致锦, 程学云, 谈莹莹, 张宗源. 基于矩阵变换的线性最近邻量子线路综合与优化[J]. 电子学报, 2018, 46(3): 688-694.
[5]	王冬, 朱长江, 张晓蕾. 量子三值全加器设计[J]. 电子学报, 2014, 42(7): 1452-1456.
[6]	王友仁, 沈先坤, 周影辉. 基于KFDD的可逆逻辑电路综合设计方法[J]. 电子学报, 2014, 42(5): 1025-1029.
[7]	徐明强, 管致锦, 张海豹. 基于最小混乱度的三值可逆逻辑综合算法[J]. 电子学报, 2013, 41(7): 1352-1357.
[8]	朱皖宁, 陈汉武, 李志钢, 阮越, 王冬, 周刚. 基于NCP门库的一维量子行走可逆逻辑电路[J]. 电子学报, 2013, 41(1): 91-97.
[9]	杨忠明;陈汉武;王冬;. 基于二分法量子可逆逻辑电路综合[J]. 电子学报, 2012, 40(5): 1045-1049.
[10]	汪鹏君;李昆鹏. 基于电路三要素理论的三值绝热加法器设计[J]. 电子学报, 2011, 39(5): 1037-1041.
[11]	王友仁;黄媛媛;冯冉;张砦. 基于矩阵编码的量子可逆逻辑电路进化设计方法[J]. 电子学报, 2011, 39(11): 2576-2582.
[12]	王冬;陈汉武;安博;杨忠明. 基于矩阵初等变换的四量子比特可逆电路综合算法[J]. 电子学报, 2010, 38(11): 2561-2565.
[13]	管致锦;秦小麟;陶涛;施 . 可逆逻辑门网络的表示与级联[J]. 电子学报, 2010, 38(10): 2370-2376.
[14]	李志强;陈汉武;徐宝文;肖芳英;薛希玲. 四量子可逆逻辑电路快速综合算法[J]. 电子学报, 2008, 36(11): 2081-2089.
[15]	杭国强. 基于开关信号理论的电流型CMOS多值施密特电路设计[J]. 电子学报, 2006, 34(5): 924-927.

基于新型量子逻辑门库的最优NCV三量子电路快速综合算法

Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics