二分法在多线量子逻辑门分解中的应用  

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

作　　者：许新山[1,2] 肖芳英[1] 张军[3] 陈汉武[1] 

机构地区：[1]东南大学计算机科学与工程学院,南京211189 [2]湖北师范学院计算机科学与技术学院,黄石435002 [3]江苏海事职业技术学院信息工程系,南京211170

出　　处：《东南大学学报（自然科学版）》2010年第5期928-931,共4页Journal of Southeast University：Natural Science Edition

基　　金：国家自然科学基金资助项目(60873101);江苏省自然科学基金资助项目(BK2007104;BK2008209)

摘　　要：将经典的对称二分法应用于多线量子可逆逻辑门的分解中,证明当量子位数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).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）.

关 键 词：多线量子可逆逻辑门 量子可逆逻辑电路 二分法 量子逻辑门分解 

分 类 号：TP387[自动化与计算机技术—计算机系统结构]