基于NCP门库的一维量子行走可逆逻辑电路

doi:10.3969/j.issn.0372-2112.2013.01.017

电子学报 ›› 2013, Vol. 41 ›› Issue (1): 91-97.DOI: 10.3969/j.issn.0372-2112.2013.01.017

基于NCP门库的一维量子行走可逆逻辑电路

朱皖宁¹, 陈汉武^1,3, 李志钢¹, 阮越^1,2, 王冬¹, 周刚¹

1. 东南大学计算机科学与工程学院,江苏南京 210096;
2. 安徽工业大学计算机学院,安徽马鞍山 243005;
3. 东南大学计算机网络和信息集成教育部重点实验室,江苏南京 210096

收稿日期:2012-04-21 修回日期:2012-10-12 出版日期:2013-01-25
- 作者简介:
- 朱皖宁 男,1983年1月生,江苏南京人.2005年毕业于东南大学计算机科学与工程学院.2006年在东南大学计算机科学与工程学院就读硕士,方向为系统结构专业,2010年进入东南大学计算机科学与工程学院,现为博士生,从事量子计算与量子可逆逻辑方面的有关研究. E-mail:granny025@163.com 陈汉武 男,1955年11月生,江苏南京人.教授,博士生导师.现从事量子信息与量子计算方向研究. E-mail:hanwu_chen@163.com 李志钢 男,1985年8月生,山西省阳泉人.2009年7月毕业于同济大学电子与信息工程学院.2009年9月进入东南大学计算机科学与工程学院,现为硕博连读生,从事量子计算与量子可逆逻辑方面的有关研究. 阮越 男,1972年8月生,安徽马鞍山人.东南大学在职博士生,安徽工业大学讲师,主要研究领域为量子计算和量子算法.
- 基金资助:
- 国家自然科学基金 (No.61170321); 高等学校博士学科点专项科研基金 (No.20110092110024); 计算机网络和信息集成教育部重点实验室基金

Reversible Logic Circuit for One-Dimensional Quantum Walk Based on NCP Quantum Gates Library

ZHU Wan-ning¹, CHEN Han-wu^1,3, LI Zhi-gang¹, RUAN Yue^1,2, WANG Dong¹, ZHOU Gang¹

1. School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China;
2. School of Computer Science, Anhui University of Technology, Ma'anshan, Anhui 243005, China;
3. Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing, Jiangsu 210096, China

Received:2012-04-21 Revised:2012-10-12 Online:2013-01-25 Published:2013-01-25
- Supported by:
- National Natural Science Foundation of China (No.61170321); Research Fund for the Doctoral Program of Higher Education of China (No.20110092110024); Key Laboratory of Computer Network and Information Integration of Ministry of Education

摘要/Abstract

摘要： 本文提出了基于NCP门库的一维量子行走可逆逻辑电路设计方案.根据一维量子行走的特点,电路被划分为投掷硬币和S操作两个部分;文章详细分析一维量子行走,对其行为数学建模,巧妙利用可控加减电路实现了S操作.目前对于量子行走算法的研究多数局限于数学理论和数理解析层面,在量子电路理论层面对量子行走算法的研究为数不多.本文利用原始递归给出了一维量子行走中每一步在量子电路理论层面上的数学表达式;提出的可逆逻辑电路描述了一维量子行走的最基本操作,并且将其使用模块化表示,使一维量子行走算法的研究从理论到实现上前进了一步.

关键词: 一维量子行走, NCP门库, 可逆逻辑, 可控加减电路, 原始递归

Abstract: The design proposal of reversible logic circuit for one-dimensional quantum walk based on NCP quantum gates library is presented.According to the features of the one-dimensional quantum walk,this circuit is divided to two parts,one part is quantum coin tossing and the other part is S operation.Besides the work above,this paper thoroughly analyses the one-dimensional quantum walk and builds a mathematical model of the one-dimensional quantum walk and uses controlled add-sub circuit to realize the S operation.At present the researches on quantum walk often limited to the mathematical theory and analysis.Depend on the primitive recursive,Mathematical expression of every step of the one-dimensional quantum walk is given in this paper;the circuit studied in this paper describes element operation of the one-dimensional quantum walk,and make this modular which contribute to the realization for the algorithm of one-dimensional quantum walk.

Key words: one-dimensional quantum walk, NCP quantum gates library, reversible logic, controlled add-sub circuit, primitive recursive

中图分类号:

朱皖宁, 陈汉武, 李志钢, 等. 基于NCP门库的一维量子行走可逆逻辑电路[J]. 电子学报, 2013, 41(1): 91-97.

ZHU Wan-ning, CHEN Han-wu, LI Zhi-gang, et al. Reversible Logic Circuit for One-Dimensional Quantum Walk Based on NCP Quantum Gates Library[J]. Acta Electronica Sinica, 2013, 41(1): 91-97.

参考文献

[1] P W Shor.Algorithms for quantum computation:discrete logarithms and factoring[A].Proceedings of the 35th Annual Symposium on Foundations of Computer Science [C].Los Alamitos,California :IEEE Press,1994.124-134.
[2] L K Grover.Quantum mechanics helps in searching for a needle in a haystack[J].Physical Review Letters,1997,79(2):325-328.
[3] Y Aharonov,L Davidovich,N Zagury.Quantum random walks[J].Physical Review A,1993,48(2):1687-1690.
[4] A Ambainis.Quantum search algorithms[J].SIGACT News,2004,35(2):22-35.
[5] A Ambainis.Quantum walk algorithm for element distinctness[A].Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science[C].USA:IEEE Press,2004.22-31.
[6] F Magniez,A Nayak,J Roland,M Santha.Search via quantum walk[A].Proceedings of the 39th Annual ACM Symposium on theory of Computing[C].USA:ACM Press,2007.575-584.
[7] A M Childs,R Cleve,E Deotto,E Farhi,S Gutmann,D A Spielman.Exponential algorithmic speedup by quantum walk[A].Proceedings of the 35th ACM Symposium on Theory of Computing[C].USA:ACM Press,2003.59-69.
[8] A M Childs,L J Schulman,U V Vazirani.Quantum algorithms for hidden nonlinear structures[A].Proceedings of the 45th IEEE Symposium on Foundations of Computer Science[C].USA:IEEE Press,2007.395-404.
[9] A M Chids.Universal computation by quantum walk[J].Physical Review Letters,2009,102(18):180501.
[10] A Ambainis,E Bach,A Nayak,A Vishwanath,J Watrous.One-dimensional quantum walks[A].Proceedings of the 33rd ACM Symposium on the Theory of Computing [C].New York:ACM,2001.60-69.
[11] D Deutsch.Quantum theory,the Church-Turing principle and the universal quantum computer[J].Proceedings of the Royal Society of London Series A,1985,400(1818):96-117.
[12] D Deutsch.Quantum computational networks[J].Proceedings of the Royal Society of London Series A,1989,425(1868):73-90.
[13] Feynman R.Quantum mechanical computers[J].Foundations of Physics,1986,16(6):507-531.(Originally appeared in Optics News,1985,11(2):11-20.)
[14] Peres A.Reversible logic and quantum computers[J].Physical Review:A,1985,32(6):3266-3276.

基于NCP门库的一维量子行走可逆逻辑电路

Reversible Logic Circuit for One-Dimensional Quantum Walk Based on NCP Quantum Gates Library

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

[1]	吴钰, 王伦耀, 储著飞, 夏银水. 一种功能可配置的可逆触发器设计[J]. 电子学报, 2022, 50(6): 1466-1471.
[2]	吴钰, 张莹, 王伦耀, 储著飞, 夏银水. 一种可逆有限状态机的电路设计[J]. 电子学报, 2020, 48(11): 2226-2232.
[3]	常丽, 朱宇祥, 蒋辉. 量子全加器设计[J]. 电子学报, 2019, 47(9): 1863-1867.
[4]	王友仁, 沈先坤, 周影辉. 基于KFDD的可逆逻辑电路综合设计方法[J]. 电子学报, 2014, 42(5): 1025-1029.
[5]	徐明强, 管致锦, 张海豹. 基于最小混乱度的三值可逆逻辑综合算法[J]. 电子学报, 2013, 41(7): 1352-1357.
[6]	李志强, 陈汉武, 刘文杰, 薛希玲, 肖芳英. 基于新型量子逻辑门库的最优NCV三量子电路快速综合算法[J]. 电子学报, 2013, 41(4): 690-697.
[7]	杨忠明;陈汉武;王冬;. 基于二分法量子可逆逻辑电路综合[J]. 电子学报, 2012, 40(5): 1045-1049.
[8]	王友仁;黄媛媛;冯冉;张砦. 基于矩阵编码的量子可逆逻辑电路进化设计方法[J]. 电子学报, 2011, 39(11): 2576-2582.
[9]	王冬;陈汉武;安博;杨忠明. 基于矩阵初等变换的四量子比特可逆电路综合算法[J]. 电子学报, 2010, 38(11): 2561-2565.
[10]	管致锦;秦小麟;陶涛;施 . 可逆逻辑门网络的表示与级联[J]. 电子学报, 2010, 38(10): 2370-2376.
[11]	李志强;陈汉武;徐宝文;肖芳英;薛希玲. 四量子可逆逻辑电路快速综合算法[J]. 电子学报, 2008, 36(11): 2081-2089.