基于规则的可逆Toffoli电路优化算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (10): 32-38.

基于规则的可逆Toffoli电路优化算法

程学云,管致锦,张海豹,丁卫平

南通大学计算机科学与技术学院南通226019;南通大学计算机科学与技术学院南通226019;南通大学电子信息学院南通226019;南通大学计算机科学与技术学院南通226019

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(60873069),江苏省高校自然科学基金(12KJB520013),南通市应用研究计划(BK2013043)资助

Rule-based Optimization of Reversible Toffoli Circuits

CHENG Xue-yun,GUAN Zhi-jin,ZHANG Hai-bao and DING Wei-pin

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 可逆电路的优化是可逆逻辑综合的关键问题之一。为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法。根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止。该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s³),优于通常使用的模板优化的复杂度O(n!t^2s³)。在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价。

关键词: 可逆逻辑综合,可逆函数,Toffoli门,可逆电路优化

Abstract: Optimization of reversible circuits is one of key problems of reversible logic synthesis．To solve the problem of high algorithm complexity and poor scalability of reversible Toffoli circuits,the paper analyzed and summarized relationship between adjacent Toffoli gates,proposed and proven the moving and simplification rules of sub-sequence of reversible circuit cascaded by Toffoli gates,and gave the optimization algorithm based on these rules．The algorithm exami-nes the circuit bidirectionally according to the moving rules,searches the sub-sequence satisfying simplification rules,performs corresponding optimization,and the process is repeated until the circuit does’t change．The algorithm is irrelevant to the number of input lines,does’t need to store extra information,is suitable to different Toffoli circuit synthesis methods,and its algorithm complexity is O(s³),which is superior to O(n!t^2s³) of generally used template optimization technique．Results of examples and experiments on all 3-bit reversible functions show that the number of gates and the control bits can be reduced effectively and the cost of reversible circuit is decreased.

Key words: Reversible logic synthesis,Reversible function,Toffoli gate,Optimization of reversible circuit

程学云,管致锦,张海豹,丁卫平. 基于规则的可逆Toffoli电路优化算法[J]. 计算机科学, 2013, 40(10): 32-38. https://doi.org/

CHENG Xue-yun,GUAN Zhi-jin,ZHANG Hai-bao and DING Wei-pin. Rule-based Optimization of Reversible Toffoli Circuits[J]. Computer Science, 2013, 40(10): 32-38. https://doi.org/

参考文献

[1] Nielsen M,Chuang I．Quantum Computation and Quantum Information[M]．Cambridge Univ．Press,2000
[2] De Vos A,Desoete B,Janiak F,et al．Control Gates as Building Blocks for Reversible Computers[A]∥Proceedings of 11^th International Workshop on Power and Timing Modeling,Optimization and Simulation[C]．Yverdon,Switzerland,Sep．2001:9201-9210
[3] Merkle R C．Two types of mechanical reversible logoc[J]．Nanotechnology,1993(4):114-131
[4] Wille R,Grobe D．Fast exact Toffoli network synthesis of reversible logic[A]∥Proceedings of International Conference on Computer-Aided Design[C]．San Jose,USA,Nov．2007:60-64
[5] 倪丽慧,管致锦,聂志浪．基于可逆函数复杂性的正反控制门可逆网络综合[J]．计算机科学,2010,37(11):117-121
[6] 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
[7] Wan Si-shuang,Chen Han-wu,Cao Ru-jin．A Novel Transformation-Based Algorithm for Reversible Logic Synthesis[A]∥Proceedings of the 4^th International Symposium on Intelligence Computation and Applications(ISICA)[C]．Wuhan,PRC,Oct．2009:70-81
[8] Zheng Y,Huang C．A novel Toffoli network synthesis algorithm for reversible logic[A]∥Proceedings of the 2009Asia and South Pacific Design Automation Conference[C]．Los Alamitos:IEEE Computer Society Press,2009:739-744
[9] Arabzadeh M,Saeedi M,Zamani M S．Rule-based Optimization of Reversible Circuits[A]∥Proceedings of ASP-DAC’2010[C]．Taipei,Taiwan,Jan．2010:849-854
[10] Maslov D,Dueck G W,Miller D M．Toffoli network synthesis with templates [J]．Computer Aided Design of Integrated Circuits and Systems,2005,24(6):807-817
[11] Maslov D,Dueck G,Miller D．Techniques for the synthesis of reversible Toffoli networks[J]．ACM Transactions on Design Automation of Electronic Systems,2007,12(4):42
[12] 陈汉武,李志强,李文骞．量子可逆逻辑综合的关键技术及其算法的研究[J].软件学报,2009,2:570-583
[13] 管致锦,秦小麟,施佺,等．基于正反控制模型的可逆逻辑综合[J]．计算机学报,2008,1(5):835-844
[14] Maslov D,Dueck G W,Miller D M．Simplification of Toffoli networks via templates[A]∥Proceedings of Integrated Circuits and Systems Design[C]．San Paulo:IEEE Computer Society,2003:53-58

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed