# [1]许新山,肖芳英,张军,等.二分法在多线量子逻辑门分解中的应用[J].东南大学学报(自然科学版),2010,40(5):928-931.[doi:10.3969/j.issn.1001-0505.2010.05.009] 　Xu Xinshan,Xiao Fangying,Zhang Jun,et al.Application of dichotomy in decomposition of multi-line quantum logic gate[J].Journal of Southeast University (Natural Science Edition),2010,40(5):928-931.[doi:10.3969/j.issn.1001-0505.2010.05.009] 点击复制 二分法在多线量子逻辑门分解中的应用() 分享到： var jiathis_config = { data_track_clickback: true };

40

2010年第5期

928-931

2010-09-20

## 文章信息/Info

Title:
Application of dichotomy in decomposition of multi-line quantum logic gate

1 东南大学计算机科学与工程学院,南京 211189; 2 湖北师范学院计算机科学与技术学院,黄石 435002; 3 江苏海事职业技术学院信息工程系,南京 211170
Author(s):
1 School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2 School of Computer Science and Technology, Hubei Normal University, Huangshi 435002, China
3 Department of Communication E

Keywords:

TP387
DOI:
10.3969/j.issn.1001-0505.2010.05.009

Abstract:
The classical symmetric dichotomy is applied to the decomposition of a multi-line quantum reversible logic gate. A conclusion is proved that any multi-line quantum reversible logic gate ’k’-CNOT can be constituted by less than [4log2(k-2)」+1-3(2log2(k-2)」+1-k+1)2log2(k-2)」] ’2’-CNOT gates(Toffoli gate)without auxiliary bit under the condition that the quantum bit n≥5 and 3≤k≤n-2. This method can make a substantial decrease in the number of the gate array corresponding circuit generated by the decomposition of a multi-line reversible quantum logic gate. Compared with the experimental results presented by Yang et al., the number of the ’2’-CNOT gates is cut down from O(2k)to O(k2).

## 参考文献/References:

[1] Nielsen M A,Chuang I L.Quantum computation and quantum information[M].Cambridge,UK:Cambridge University Press,2000.
[2] Deutsch D,Barenco A,Ekert A.Universality in quantum computation[J].Mathematical and Physical Sciences,1995,449(1937):669-677.
[3] Lloyd S.Almost any quantum logic gate is universal[J].Phys Rev Lett,1995,75(2):346-349.
[4] Vos A D,Rentergem Y V.Reversible computing:from mathematical group theory to electronical circuit experiment[C] //Proceedings of the 2005 Computing Frontiers Conference. Ischia,Italy,2005:35-44.
[5] Rentergem Y V,Vos A D,Keyser K D.Six synthesis methods for reversible logic[J].Open Systems &Information Dynamics,2007,14(1):91-116.
[6] Yang G W,Song X Y,Hung W N N,et al.Group theory based synthesis of binary reversible circuits[J].Lecture Notes in Computer Science,2006,3959:365-374.
[7] Maslov D,Dueck G W.Garbage in reversible designs of multiple-output functions[C] //Proceedings of the 6th International Symposium on Representations and Methodology of Future Computing Technologies.Trier,Germany,2003:162-170.
[8] Toffoli T.Reversible computing[J].Lecture Notes in Computer Science,1980,85:632-644.
[9] Shende V V,Prasad A K,Markov I L,et al.Reversible logic circuit synthesis[C] //Proceedings of the International Conference on Computer Aided Design.San Jose,California,USA,2002:125-132.
[10] 李文骞,陈汉武,王佳佳,等.模板技术在量子逻辑电路优化中的应用[J].东南大学学报:自然科学版,2006,36(6):920-926.
Li Wenqiang,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(6):920-926.(in Chinese)
[11] 李志强,陈汉武,徐宝文,等.基于Hash表的量子可逆逻辑电路综合的快速算法[J].计算机研究与发展,2008,45(12):2162-2171.
Li Zhiqiang,Chen Hanwu,Xu Baowen,et al.Fast algorithms for synthesis of quantum reversible logic circuits based on hash table [J].Journal of Computer Research and Development,2008,45(12):2162-2171.(in Chinese)
[12] 李志强,陈汉武,徐宝文,等.量子可逆逻辑电路综合的快速算法研究[J].计算机学报,2009,32(7):1291-1303.
Li Zhiqiang,Chen Hanwu,Xu Baowen,et al.A fast algorithm for synthesis of quantum reversible logic circuits [J].Chinese Journal of Computers,2009,32(7):1291-1303.(in Chinese)