[1]杨忠明,陈汉武,安博,等.基于真值表演算的四量子电路综合方法[J].东南大学学报(自然科学版),2010,40(2):285-290.[doi:10.3969/j.issn.1001-0505.2010.02.013]
 Yang Zhongming,Chen Hanwu,An Bo,et al.4-qubit circuits synthesis based on truth table permutation[J].Journal of Southeast University (Natural Science Edition),2010,40(2):285-290.[doi:10.3969/j.issn.1001-0505.2010.02.013]
点击复制

基于真值表演算的四量子电路综合方法()
分享到:

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

卷:
40
期数:
2010年第2期
页码:
285-290
栏目:
计算机科学与工程
出版日期:
2010-03-20

文章信息/Info

Title:
4-qubit circuits synthesis based on truth table permutation
作者:
杨忠明1 陈汉武1 安博1 王冬12 李志强13
1 东南大学计算机科学与工程学院,南京 210096; 2 河南大学计算机中心, 开封 415002; 3 扬州大学信息工程学院,扬州 225009
Author(s):
Yang Zhongming1 Chen Hanwu1 An Bo1 Wang Dong12 Li Zhiqiang13
1 School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
2 Computer Center, Henan University, Kaifeng 415002, China
3 College of Information Engineering, Yangzhou University, Yangzh
关键词:
四量子 可逆逻辑 置换 四量子电路综合 量子计算
Keywords:
4-qubit reversible logic permutation 4-qubit circuit synthesis quantum computation
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2010.02.013
摘要:
为了能以较小的代价高效地自动构造量子可逆逻辑电路,提出了一种新颖的四量子可逆逻辑综合方法.该方法首先将一个四量子电路的函数表示成真值表的形式; 然后利用传统的递归思想,通过对换演算,将四量子电路映射函数的真值表分解成2块相互独立的三量子电路映射函数的真值表; 再查找相应的最优三量子电路,直接生成相关电路; 最后将对换运算的电路并入该电路,经过局部优化即可生成最终电路.分析结果表明,用该方法综合四量子电路能大幅减少TOF门的数量,平均需要15.74个TOF门,最多只需24个TOF门.同时该算法避免了穷举法所需的时空复杂度太大的问题,便于经典计算机实现.
Abstract:
In order to construct quantum reversible logic circuits efficiently and automatically with low cost, a novel method for 4-qubit circuits is proposed. It first represents a 4-qubit function by truth table. Using traditional recursive thought, through truth table permutation, a truth table of 4-qubit mapping function can be decomposed into two independent truth tables of 3-qubit mapping function. Then the corresponding optimal 3-qubit circuits are found, and relevant circuit is directly generated. Meanwhile, the circuits generated in permutation are also added into the circuit. After optimization, 4-qubit quantum reversible logic circuits are finally synthesized. Experimental results show that the number of gates to construct reversible logic circuits is less than that of other methods. For any 4-qubit binary logic function, the average number of TOF gates is 15.74 and the most number of TOF gates is 24. This method avoids the exponential nature of the memory or run-time complexity, and it is simple to implement in classical computer.

参考文献/References:

[1] Toffoli T. Reversible computing:automata,languages and programming[M].New York:Springer,1980:632-644.
[2] Song X Y,Yang G W,Perkowski M,et al.Algebraic characteristics of reversible gates[J]. Theory of Computing Systems,2004,37(2):311-319.
[3] Iwama K,Kambayashi Y,Yamashita S.Transformation rules for designing CNOT-based quantum circuits[C] //Proceedings of Design Automation Conference.New Orleans,LA,USA,2002,28(4):419-425.
[4] Miller D M,Maslov D,Gueck G W.Spectral and two-place decomposition techniques in reversible logic[C] //Proceedings of the 45th IEEE International Midwest Symposium on Circuits and Systems.Tulsa,AR,USA,2002:493-496.
[5] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis[C] //Proceedings of the 40th Design Automation Conference.Anaheim,CA,USA,2003:318-323.
[6] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Trans on Circuits and Systems-Ⅰ,2005,24(6):807-817.
[7] Li W Q,Chen H W,Li Z Q.Application of semi-template in reversible logic circuit[C] //Proceedings of the 11th International Conference on Computer Supported Cooperative Work in Design.Melbourne,Australia,2007:155-161.
[8] Shende V V,Prasad A K,Markov I L,et al.Reversible logic circuit synthesis[C] //Proceedings of the ACM/IEEE International Conference on Computer-Aided Design.San Jose,CA,USA,2002:125-132.
[9] Shende V V,Prasad A K,Markov I L,et al.Synthesis of reversible logic circuits[J]. IEEE Trans on Circuits and Systems-Ⅰ,2003,22(6):723-729.
[10] Yang Guowu,Song Xiaoyu,William N,et al.Group theory based synthesis of binary reversible circuits[C] //Proceedings of the 3rd International Conference on Theory and Applications of Models of Computation.Beijing,China,2006:365-374.
[11] 李志强,陈汉武,李文骞.基于位运算的量子可逆逻辑电路快速综合算法[J].计算机科学,2008,35(3):13-17.
  Li Zhiqiang,Chen Hanwu,Li Wenqian.Speedy algorithm for synthesis of quantum reversible logic circuits based on bit operation [J]. Computer Science,2008,35(3):13-17.(in Chinese)
[12] 陈汉武,李志强,徐宝文.置换群与整数间一对一Hash函数的构建[J].东南大学学报:自然科学版,2008,38(2):225-227.
  Chen Hanwu,Li Zhiqiang,Xu Baowen.Construction of one-for-one Hash function mapping between permutation group and integral number [J].Journal of Southeast University:Natural Science Edition,2008,38(2):225-227.(in Chinese)

相似文献/References:

[1]陈汉武,李志强,徐宝文.置换群与整数间一对一 Hash函数的构建[J].东南大学学报(自然科学版),2008,38(2):225.[doi:10.3969/j.issn.1001-0505.2008.02.008]
 Chen Hanwu,Li Zhiqiang,Xu Baowen.Construction of one-for-one Hash function mapping between permutation group and integral number[J].Journal of Southeast University (Natural Science Edition),2008,38(2):225.[doi:10.3969/j.issn.1001-0505.2008.02.008]
[2]李文骞,陈汉武,王佳佳,等.模板技术在量子逻辑电路优化中的应用[J].东南大学学报(自然科学版),2006,36(6):920.[doi:10.3969/j.issn.1001-0505.2006.06.010]
 Li Wenqian,Chen Hanwu,Wang Jiajia,et al.Application of template technique in optimizing quantum logical circuit[J].Journal of Southeast University (Natural Science Edition),2006,36(2):920.[doi:10.3969/j.issn.1001-0505.2006.06.010]

备注/Memo

备注/Memo:
作者简介: 杨忠明(1983—),男,硕士生; 陈汉武(联系人),男,博士,教授,博士生导师,hw_chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60572071,60873101)、江苏省自然科学基金资助项目(BM2006504,BK2007104).
引文格式: 杨忠明,陈汉武,安博,等.基于真值表演算的四量子电路综合方法[J].东南大学学报:自然科学版,2010,40(2):285-290. [doi:10.3969/j.issn.1001-0505.2010.02.013]
更新日期/Last Update: 2010-03-20