量子可逆逻辑电路双向综合算法  

Bidirectional Quantum Reversible Logic Circuits Synthesis Algorithm

作　　者：王冬[1,2] 张晓蕾[1] 朱长江[1] 

机构地区：[1]河南大学软件学院,河南开封475001 [2]武汉大学软件工程国家重点实验室,武汉430072

出　　处：《小型微型计算机系统》2014年第5期1111-1115,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61004006)资助;武汉大学软件工程国家重点实验室

摘　　要：量子可逆逻辑电路综合技术是构建量子计算机的关键技术之一.本文提出基于数组正反变换的量子可逆逻辑电路双向综合算法.该算法依据两个数字间的汉明距离,利用邻接矩阵的电路转化规则,从正反两个方向,生成任意给定置换的量子可逆逻辑电路.理论分析表明,该方法综合n量子电路最多需要(n-1)·2n+1个扩展通用Toffoli门.与其它同类算法相比,由于不需要穷尽搜索,该算法的时间复杂度和空间复杂度都有大幅度降低.此外,由于合理采用了扩展通用Toffoli门,该算法可综合任一置换(包括奇置换和偶置换)的量子可逆逻辑电路,且电路中量子门的数量大幅减少.Quantum reversible logic circuits synthesis is one of the key techniques to construct quantum computer. Quantum reversible logic circuits synthesis algorithm based on arrayg bidirectional transformation is proposed in this paper. By using the circuit transfor- mation rules of adjacent matrix, the algorithm can construct any quantum reversible logic circuit given permutation in terms of the hamming distance of two numbers. Theoretical analysis shows that there are （ n - 1 ） , 2n ＋ 1 extended general Toffoli gates in the cir- cuit synthesized by our algorithm. Compared with the other algorithms, the time-space complexity of our algorithm has been de- creased greatly because of without exhaustive searching, moreover, the types of the quantum reversible logic circuits synthesized by our algorithm are even and odd permutation since we use extended general Toffoli gates, and the number of quantum gates in the cir- cuit is cut down greatly.

关 键 词：量子可逆逻辑电路 量子计算 Toffoli门 

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