计算机科学 ›› 2014, Vol. 41 ›› Issue (9): 18-23.doi: 10.11896/j.issn.1002-137X.2014.09.002
王冬,刘强,李善治
WANG Dong,LIU Qiang and LI Shan-zhi
摘要： 基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低；又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。
| [1] Nielsen M A,Chuang I L．Quantum Computation and Quantum Information [M]．Cambridge:Cambridge University Press,2000 [2] Bennett C．Logical reversibility of computation [J]．IBM Journal of Research and development,1973,17(6):525-532 [3] Barcnco A,Bennett C,et al．Elementary gates for quantum computation [J]．Physical Review A,1995,52(5):3457-3467 [4] Yang Liu,Long Gui-lu,Yang Sun．Analytic one-bit and CNOT Gate Constructions of General n-Qubit Controlled Gates [J]．International Journal of Quantum Infоrmation,2008,6(3):447-462 [5] Song Xiao-yu,Yang Guo-wu,Perkowski M,et al．Algebraiccharacteristics of reversible gates [M]．Theory of Computing System,2004:311-391 [6] Iwama K,Kambayashi Y,Yamashita S．Transformation rules for designing CNOT-based quantum circuits[C]∥Proceedings of Design Automation Conference,2002．New Orleans,2002:419-424 [7] 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,2002．Tulsa,2002:493-496 [8] Maslov D,Dueck G W,Miller D M．Toffoli network synthesis with templates [J]．IEEE Transactions on Circuits and System-I,2005,24(6):807-817 [9] Miller D M,Maslov D,Dueck G W．A transformation based algorithm for reversible logic synthesis[C]∥Proceedings of the International Conference on Computer-Aided Design,2003．2003:318-323 [10] Shende V V,Prasad A K,Markov I L,et al．Synthesis of reversible logic circuits [J]．IEEE Transactions on Circuits and System-I,2003,22(6):710-722 [11] Yang Guo-wu,Song Xiao-yu,et al．Fast synthesis of exact Minimal reversible circuits using group theory[C]∥Proceedings of the 2005 conference on Asia South Pacific design automation,2005．Shanghai,2005:1002-1005 [12] Yang Guo-wu,Song Xiao-yu,Hung W N,et al．Bi-direction Synthesis for Reversible Circuits[C]∥Proceedings of the IEEE Computer Society Annual Symposium on VLSI,2005．Tampa:IEEE,2005 [13] Yang Guo-wu,Song Xiao-yu,Hung W N,et al．Bi-directionalSynthesis of 4-bit Reversible Circuits [J]．The Computer Journal,2008,51(2):207-215 [14] Li Zhi-qiang,Chen Han-wu,Xu Bao-wen．Fast algorithms for 4-qubit reversible logic circuits synthesis [J]．Acta Electronic Sinica,2008,36(11):2081-2089 [15] Yang Guo-wu,Xie Fei,Song Xiao-yu,et al．A constructive algorithm for reversible logic synthesis[C]∥Proceedings of 2006 IEEE Congress on Evolutionary Computation,2006 ．Vancouver BC:IEEE,2006 [16] Dixon J D,Mortimer B．Permutation Group [M]．New York:Springer,1996 [17] Toffoli T．Reversible computing [J]．Computer Science,1980,85:632-644 [18] Weiss M A．Data Structures and Algorithm Analysis in C (Se-cond Edition) [M]．Beijing:POSTS & TELECOM PRESS,2005 |
| No related articles found! |
|
||
首页