[1]王冬,陈汉武,安博,等.量子可逆电路综合的启发式快速匹配算法[J].东南大学学报(自然科学版),2009,39(5):900-903.[doi:10.3969/j.issn.1001-0505.2009.05.006]
 Wang Dong,Chen Hanwu,An Bo,et al.Heuristic fast-matching algorithm for synthesis of quantum reversible logic circuits[J].Journal of Southeast University (Natural Science Edition),2009,39(5):900-903.[doi:10.3969/j.issn.1001-0505.2009.05.006]
点击复制

量子可逆电路综合的启发式快速匹配算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
39
期数:
2009年第5期
页码:
900-903
栏目:
计算机科学与工程
出版日期:
2009-09-20

文章信息/Info

Title:
Heuristic fast-matching algorithm for synthesis of quantum reversible logic circuits
作者:
王冬12 陈汉武1 安博1 杨忠明1
1 东南大学计算机科学与工程学院, 南京 210096; 2 河南大学计算中心, 开封 415002
Author(s):
Wang Dong12 Chen Hanwu1 An Bo1 Yang Zhongming1
1 School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Computer Center, Henan University, Kaifeng 415002, China
关键词:
量子可逆逻辑电路 Reed-Muller展开式 CNOT门 Toffoli门
Keywords:
quantum reversible logic circuits Reed-Muller expansion CNOT gate Toffoli gate
分类号:
TP387;TN911.73
DOI:
10.3969/j.issn.1001-0505.2009.05.006
摘要:
提出了基于Reed-Muller展开式,使用CNT量子门库,以量子门表达式为启发式规则进行前向模式匹配的量子可逆逻辑电路快速综合算法.与通常所用的穷尽搜索算法相比,该算法利用量子门表达式作为启发式规则进行匹配代换,避免盲目匹配,有效降低了匹配复杂度,减少匹配代换的数量.同时该算法不会出现穷尽搜索中因不能找到有效解而进行回溯的现象,能以较小的时间空间复杂度生成最优或近似最优的量子可逆电路,特别在多量子可逆逻辑电路综合上,能够表现出更好的性能.
Abstract:
Heuristic fast-matching algorithm for quantum reversible logic circuits synthesis is presented. The algorithm is based on Reed-Muller expansion, uses CNT quantum gates library, takes the quantum gate equations as the heuristic rules and adopts forward-matching method to construct quantum circuits. Compared with current exhaustive search, the proposed algorithm uses the quantum gate equations as the heuristic rules which can avoid blind matching and decrease the matching complexity. It is simple and can effectively build optimal or near-optimal circuits with lower cost. Moreover it can perform well in the multi-quantum reversible logic circuits synthesis.

参考文献/References:

[1] Bennett C.Logical reversibility of computation[J].IBM J Res Dev,1973,17(6):525-532.
[2] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Trans CADICS,2005,24(6):807-817.
[3] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis[C] //Proceedings of Design Automation Conference.Anaheim,CA,USA,2003:318-323.
[4] Shende V V,Prasad A K,Markov I L,et al.Synthesis of reversible logic circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2003,22(6):710-722.
[5] Yang G,Song X,Perkowski M A,et al.Four-level realization of 3-qubit reversible function[J]. IET Comput Digit Tech,2007,1(4):382-388.
[6] Kerntopf P.A new heuristic algorithm for reversible logic synthesis[C] //Proceedings of the Design Automation Conference.San Diego,CA,USA,2004:834-837.
[7] Shende V V,Prasad A K,Markov I L,et al.Reversible logic circuits synthesis[C] //IEEE/ACM International Computer on Confater Aided Design.San Jose,CA,USA,2002:353-360.
[8] Li Z Q,Chen H W,Xu B W,et al.Fast algorithms for 4-qubit reversible logic circuits synthesis[J].Acta Electronic Sinica,2008,36(11):2081-2089.
[9] Saeedi M,Sedighi M,Zamani M S.A novel synthesis algorithm for reversible circuits[C] //IEEE/ACM International Computer on Confater Aided Design.San Jose,CA,USA,2007:65-68.
[10] Abdollahi A,Pedram M.Analysis and synthesis of quantum circuits by using quantum decision diagrams[C] //Proceedings of Design,Automation and Test in Europe.Munich,Germany,2006:317-322.

相似文献/References:

[1]朱皖宁,陈汉武,刘志昊,等.基于Ring-Sum-Expansion范式的Reed-Muller展开式算法[J].东南大学学报(自然科学版),2010,40(5):932.[doi:10.3969/j.issn.1001-0505.2010.05.010]
 Zhu Wanning,Chen Hanwu,Liu Zhihao,et al.Reed-Muller expansion algorithm based on Ring-Sum-Expansion[J].Journal of Southeast University (Natural Science Edition),2010,40(5):932.[doi:10.3969/j.issn.1001-0505.2010.05.010]

备注/Memo

备注/Memo:
作者简介: 王冬(1977—),女,博士生; 陈汉武(联系人),男,博士,教授,博士生导师,hw_chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60572071,60873101)、江苏省自然科学基金资助项目(BM2006504,BK2007104).
引文格式: 王冬,陈汉武,安博,等.量子可逆电路综合的启发式快速匹配算法[J].东南大学学报:自然科学版,2009,39(5):900-903. [doi:10.3969/j.issn.1001-0505.2009.05.006]
更新日期/Last Update: 2009-09-20