[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]
点击复制

二分法在多线量子逻辑门分解中的应用()
分享到:

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

卷:
40
期数:
2010年第5期
页码:
928-931
栏目:
计算机科学与工程
出版日期:
2010-09-20

文章信息/Info

Title:
Application of dichotomy in decomposition of multi-line quantum logic gate
作者:
许新山12 肖芳英1 张军3 陈汉武1
1 东南大学计算机科学与工程学院,南京 211189; 2 湖北师范学院计算机科学与技术学院,黄石 435002; 3 江苏海事职业技术学院信息工程系,南京 211170
Author(s):
Xu Xinshan12 Xiao Fangying1 Zhang Jun3 Chen Hanwu1
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:
multi-line quantum reversible logic gate quantum reversible logic circuit dichotomy decomposition of quantum logic gate
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2010.05.009
摘要:
将经典的对称二分法应用于多线量子可逆逻辑门的分解中,证明当量子位数n≥5且3≤k≤n-2时,任意多线量子可逆逻辑门(’k’-CNOT门)可以在没有辅助位的情况下由少于[4log2(k-2)」+1-3(2log2(k-2)」+1-k+1)2log2(k-2)」]个’2’-CNOT门(Toffoli门)构成.利用该方法可以使由多线量子可逆逻辑门分解而生成的物理电路门阵列数大幅下降.与Yang等报道的实验结果相比,’2’-CNOT门的数量级由O(2k)减少为O(k2).
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)

备注/Memo

备注/Memo:
作者简介: 许新山(1965—),男,副教授; 陈汉武(联系人),男,博士,教授,博士生导师,hw-chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60873101)、江苏省自然科学基金资助项目(BK2007104,BK2008209).
引文格式: 许新山,肖芳英,张军,等.二分法在多线量子逻辑门分解中的应用[J].东南大学学报:自然科学版,2010,40(5):928-931. [doi:10.3969/j.issn.1001-0505.2010.05.009]
更新日期/Last Update: 2010-09-20