优化的可逆MCT电路化简算法

J4 ›› 2017, Vol. 34 ›› Issue (6): 713-720.

优化的可逆MCT电路化简算法

程学云

南通大学

收稿日期:2016-08-16 修回日期:2016-12-05 出版日期:2017-11-28 发布日期:2017-12-11
通讯作者: 程学云

Optimized Simplification Algorithm for Reversible MCT Circuits

Received:2016-08-16 Revised:2016-12-05 Published:2017-11-28 Online:2017-12-11

摘要/Abstract

摘要： 随着对低能耗电路设计及量子计算的日益重视，可逆电路的综合和优化也得到广泛关注。提出了可逆MCT电路中一种新的MCT门交换规则，并基于该交换规则给出了MCT门序列的约简规则和MCT门的移动规则。根据新给出的约简规则和移动规则，实现了更为通用的可逆MCT电路化简算法。通过实例及所有3变量可逆函数上的实验结果验证了化简算法的有效性，能进一步减少可逆电路的门数和量子代价。与已有的同类规则相比，本文提出的MCT门交换规则没有约束条件，适用性更强，改进了可逆MCT电路的化简结果。

关键词: MCT电路

Abstract: With the increasing emphasis on low power circuit design and quantum computing, synthesis and simplification of reversible circuits has also received extensive attention. A new MCT gate exchange rule in reversible MCT circuit is put forward, and corresponding MCT gate sequence reduction rules and gate moving rule based on the exchange rules are given. According to all the proposed rules, a more general simplification algorithm of reversible MCT circuit is generated. Experimental results on specific examples and all 3 variables reversible functions verify the effectiveness of the simplification algorithm, and it can further reduce the number of gates and quantum cost. Compared with the existing similar rules, the proposed MCT gate exchange rule has the characteristics of unconstrained conditions as well as stronger applicability, which improves the simplification results of reversible MCT circuit.

Key words: MCT circuit

程学云. 优化的可逆MCT电路化简算法[J]. J4, 2017, 34(6): 713-720.

参考文献

[1] R. Landauer, Irreversibility and heat generation in the computing process[J], IBM Journal of Research and Development, 2000, 44(12), pp. 261–269.
[2] C. H. Bennett, Logical reversibility of computation[J], IBM Journal of Research and Development, 1973, 17(6), pp. 525–532.
[3] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information[M]. Cambridge University Press, 2000.
[4] A. De Vos, B. Desoete, F. Jaiak, and A. Nogawski. Control gates as building blocks for reversible computers[C]//Proceedings of the 11th International Workshop on Power and Timing Modeling, Optimization and Simulation, 2001, pp. 9201-9210.
[5] O.Golubitsky, D.Maslov, A study of optimal 4-bit reversible toffoli circuits and their synthesis[J]. IEEE Transactions on Computers, 2012, 61(9): 1341-1353.
[6] Sishuang Wan, Hanwu Chen, Rujin Cao. A Novel Transformation-Based Algorithm for Reversible Logic Synthesis[C]//Proceedings of the 4th International Symposium on Intelligence Computation and Applications (ISICA), 2009, LNCS 5821, pp. 70-81.
[7] Miller, D.M., Maslov, D., Dueck, G.W. A transformation based algorithm for reversible logic synthesis[A]. Proceedings of DAC[C], Anahem, California, USA, 2003: 318-323.
[8] Maslov D, Dueck G W and Miller D M. Toffoli network synthesis with templates [J]. Computer Aided Design of Integrated Circuits and Systems, 2005, 24(6):807–817.
[9] D. Maslov, G. Dueck, and D. Miller. Techniques for the synthesis of reversible Toffoli networks[J]. ACM Transactions on Design Automation of Electronic Systems, 2007, 12(4), Article 42.
[10] Mona Arabzadeh, Mehdi Saeedi, Morteza Saheb Zamani. Rule-based Optimization of Reversible Circuits[A]. Proceedings of ASP-DAC'2010[C], Taipei, Taiwan, Jan. 18-21, 2010:849-854.
[11] 程学云,管致锦,张海豹等.基于规则的可逆Toffoli电路优化算法[J]. 计算机科学, 2013,40(10):32-38. Cheng Xueyun, Guan Zhijin, Zhang Haibao, etc. Rule-Based Optimization of Reversible Toffoli Circuits[J]. Computer Science, 2013,40(10):32-38.
[12] Maslov D. Reversible logic synthesis benchmarks page[OL]. [2016-07-12]. http://www.cs.uvic.ca/~dmaslov