计算机科学 ›› 2014, Vol. 41 ›› Issue (9): 18-23.doi: 10.11896/j.issn.1002-137X.2014.09.002

• 综述 • 上一篇    下一篇

基于矩阵初等变换的量子可逆逻辑电路双向综合算法

王冬,刘强,李善治   

  1. 河南大学软件学院 开封475001;武汉大学软件工程国家重点实验室 武汉430072;河南大学软件学院 开封475001;河南大学软件学院 开封475001
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金项目(61004006),软件工程国家重点实验室(武汉大学)开放课题(SKLSE2012-09-41)资助

Bidirectional Reversible Logic Circuit Synthesis Algorithm Based on Matrix Elementary Transformation

WANG Dong,LIU Qiang and LI Shan-zhi   

  • Online:2018-11-14 Published:2018-11-14

摘要: 基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低;又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。

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

Abstract: Quantum reversible logic circuit synthesis is one of the key techniques to construct the quantum computer.Bidirectional reversible logic circuit synthesis algorithm based on matrix elementary transformation was proposed in this paper.The algorithm can construct reversible logic circuit of any given permutation by using the circuit transformation rules of the adjacent matrix and the method of exchanging either the row number or the elements of the matrix in terms of hamming distance of two numbers.Compared with the other algorithms,the time-space complexity of our algorithm has been decreased greatly because of without exhaustive searching.Moreover,the types of the quantum reversible logic circuits synthesized by our algorithm are even and odd permutation because using n-qubit extended general Toffoli gates,and the number of quantum gates in the circuit is cut down.

Key words: Quantum reversible logic circuit,Quantum computation,Toffoli gate

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .