基于遗传算法的量子可逆逻辑电路综合方法研究
|
摘要
随着集成电路的集成度越来越高,电子器件的内部量子效应越来越明显,制造计算机的传统方法在提高集成度上越来越力不从心;集成电路能耗导致计算机芯片发热,也影响了芯片集成度的进一步提高。量子逻辑电路实现都是可逆操作,不存在热耗散,从理论上解决了芯片发热问题,而且其计算能力较传统电路有巨大提高,因此引起了人们极大的兴趣。本文阐述的重点是量子电路的可逆逻辑综合问题。
量子可逆逻辑电路综合主要是研究在给定的量子门和量子电路的约束条件及限制下,找到最小或较小的量子代价电路实现所需电路逻辑功能。本文介绍了现在对此方面的研究现状和成果,探索了量子电路综合方法的规律,并提出一种将遗传算法应用于量子可逆逻辑电路综合的新方法。这个方法将量子逻辑门的功能用矩阵的数学模型表示,用遗传算法作全局搜索工具,实现了合成、优化同步进行,在实验中取得了良好效果,展示了此方法在高阶量子电路综合问题上的应用前景。
本文详细介绍了量子逻辑门的计算原理和遗传算法应用在量子电路综合问题上的实现方法以及考虑物理实现、完备性、不同量子门代价和算法性能各方面建立门库的过程。在三阶、四阶电路综合实验中,分析了新方法的性能,此方法很好的利用了遗传算法在全局搜索中的强大功能,并巧妙的将量子可逆电路的消去规则加入算法实现中对算法做出改进,用实验数据体现了此方法的可调试性强,适用性和实用性高的特点。
With the rapid development of IC technology, classical method of produce has little ability to rise integration mastering. The energy loss of integrated circuit cause the heat generated from computer chips. It delays the increase of chip integration level. The operation of quantum logical circuit is reversible. It does not have heat generating problem, so can settle the heat generated from chips from theory. And it has faster compute speed which is the other reason makes people give more and more attentions to this domain. This paper expatiates on synthesis of quantum reversible logic circuits.
Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost. This paper introduces the current situation and production of the research of synthesis of quantum reversible logic circuits and its rules. We present a new method to synthesize quantum reversible logic circuits based on genetic algorithm. The function of quantum logic gates is expressed in terms of matrix. Then we use genetic algorithm as search tool to synthesis reversible logic circuits. This method got good performance which proves a bright application prospect in synthesis of high-order quantum circuits.
This paper introduces the calculation principle of quantum logic gates and how to synthesize quantum reversible logic circuits with genetic algorithm. The process of foundation gate library should consider physical realization, integrity, performance and different quantum cost of different gates. The new synthesis algorithm is analyzed in three-order and four-order circuit experiments, which utilize powerful search function of genetic algorithm and is improved by adding remove rule in. Experimental results demonstrate that the algorithm has good practicability, applicability and debug ability.
量子可逆逻辑电路综合主要是研究在给定的量子门和量子电路的约束条件及限制下,找到最小或较小的量子代价电路实现所需电路逻辑功能。本文介绍了现在对此方面的研究现状和成果,探索了量子电路综合方法的规律,并提出一种将遗传算法应用于量子可逆逻辑电路综合的新方法。这个方法将量子逻辑门的功能用矩阵的数学模型表示,用遗传算法作全局搜索工具,实现了合成、优化同步进行,在实验中取得了良好效果,展示了此方法在高阶量子电路综合问题上的应用前景。
本文详细介绍了量子逻辑门的计算原理和遗传算法应用在量子电路综合问题上的实现方法以及考虑物理实现、完备性、不同量子门代价和算法性能各方面建立门库的过程。在三阶、四阶电路综合实验中,分析了新方法的性能,此方法很好的利用了遗传算法在全局搜索中的强大功能,并巧妙的将量子可逆电路的消去规则加入算法实现中对算法做出改进,用实验数据体现了此方法的可调试性强,适用性和实用性高的特点。
With the rapid development of IC technology, classical method of produce has little ability to rise integration mastering. The energy loss of integrated circuit cause the heat generated from computer chips. It delays the increase of chip integration level. The operation of quantum logical circuit is reversible. It does not have heat generating problem, so can settle the heat generated from chips from theory. And it has faster compute speed which is the other reason makes people give more and more attentions to this domain. This paper expatiates on synthesis of quantum reversible logic circuits.
Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost. This paper introduces the current situation and production of the research of synthesis of quantum reversible logic circuits and its rules. We present a new method to synthesize quantum reversible logic circuits based on genetic algorithm. The function of quantum logic gates is expressed in terms of matrix. Then we use genetic algorithm as search tool to synthesis reversible logic circuits. This method got good performance which proves a bright application prospect in synthesis of high-order quantum circuits.
This paper introduces the calculation principle of quantum logic gates and how to synthesize quantum reversible logic circuits with genetic algorithm. The process of foundation gate library should consider physical realization, integrity, performance and different quantum cost of different gates. The new synthesis algorithm is analyzed in three-order and four-order circuit experiments, which utilize powerful search function of genetic algorithm and is improved by adding remove rule in. Experimental results demonstrate that the algorithm has good practicability, applicability and debug ability.
引文
[1] M Nielsen, I Chuang,赵千川译.量子计算和量子信息,北京:清华大学出版社,2004.
[2] M Nielsen, I Chuang. Quantum Computation and Quantum Information, Cambridge, UK: Cambridge University Press,2000.
[3] D Maslov. Reversible Logic Synthesis, The University of New Brunswick, 2003.
[4] V V Shende, A K Prasad, I L Markov. Synthesis of Reversible Logic Circuits, IEEE Trans Computer-Aided Design Integrated Circuits Systems, Vol.22, No.6, (2003), 723-729.
[5] G W Dueck, D Maslov. Reversible Function Synthesis with Minimum Garbage Outputs, Proc 6th Int Symp Represent Methodol Future Comput Technol, Trier, (2003), 154-161.
[6] D M Miller, G W Dueck. Spectral Techniques for Reversible Logic Synthesis, Proc 6th Int Symp Represent Methodol Future Comput Technol, Trier, (2003), 56-62.
[7] P Kerntopf. A New Heuristic Algorithm for Reversible Logic Synthesis, Proc Design Automation Conf. San Diego, (2004), 834-837.
[8] K Iwama, Y Kambayashi, S Yamashita. Transformation Rules for Designing CNOT-Based Quantum Circuits, Proc Design Automation Conf. New Orleans, (2002), 419-425.
[9] D Maslov, G W Dueck, D M Miller. Toffoli Network Synthesis with Templates, IEEE Trans Computer-Aided Design Integrated Circuits Systems, Vol.24, No.6, (2005), 807-817.
[10] G W Dueck, D Maslov, D M Miller. Transformation-Based Synthesis of Network of Toffoli/Fredkin Gates, Electrical and Computer Engineering 2003 IEEE CCECE, Montreal, (2003), 211-214.
[11] A Agrawal, N K Jha. Synthesis of Reversible Logic, Design, Automation and Test in Europe Conference and Exhibition, Paris, (2004), 1384-1385.
[12] P Gupta, A Agrawal, N K Jha. An Algorithm for Synthesis of Reversible Logic Circuits, IEEE Trans Computer-Aided Design of Integrated Circuits Systems, Vol.25, No.11, (2006), 2317-2330.
[13] A Mishchenko, M Perkowski. Logic Synthesis of Reversible Wave Cascodes, Proc Int Workshop Logic Synthesis, New Orleans, (2002), 197-202.
[14] D Maslov, G W Dueck, D M Miller. Simplication of Toffoli Networks via Templates, Proceedings Integrated Circuits and Systems Design, San Paulo,(2003), 53-58.
[15] D Maslov, C Young, D M Miller. Quantum Circuit Simplication using Templates , Design, Automation and Test in Europe, Munich, (2005), 1208-1213.
[16] M A Thornton. Fixed Polarity Reed-Muller Forms[EB/OL][2006-03-01] http://engr.smu.edu/mitch/class/8391/week12/esop.pdf.
[17] M A Thornton, R Drechsler, D M Miller. Spectral Techniques in VLSI CAD, Kluwer Academic Publishers, 2001.
[18] W N Hung, X Song, G Yang. Quantum Logic Synthesis by Symbolic Reachability Analysis, Proc Design Automation Conf. San Diego, (2004), 838-841.
[19] Shende V V, Bullock S S, Markov I L. Synthesis of Quantum Logic Circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.25, No.6, (2006),1000-1010.
[20] Yang G W, Song X Y, Hung W N. Group Theory based Synthesis of Binary Reversible Ccircuits, TAMC, (2006), 365-374.
[21] Yang G W, Song X Y, Hung W N. Fast Synthesis of Exact Minimal Reversible Circuits using Group Theory. Proceedings of IEEE ASP-DAC, Shanghai China, (2005), 18-21.
[22] Miller D M, Maslov D, Dueck G W. A Transformation based Algorithm for Reversible Logic Synthesis, DAC, Vol.11, No. 7 (2003), 318-321.
[23] Gupta P, Agrawal A, Jha N K. An Algorithm for Synthesis of Reversible Logic Circuits. IEEE Transactions on Circuits and Systems, Vol.25, No.11, (200611), 807-811.
[24] Ville R, Robert T D, Grobe D A. Fast Exact Toffoli Network Synthesis of Reversible Logic, IEEE Transactions on Computer-Aided Design, Vol.4, No.8, (2007), 60-64.
[25] Li Z Q, Chen H W, Xu B W. Fast Algorithm for 4-qubit Reversible Logic Circuits Synthesis, Evolutionary Computation,CEC,(2008), 2202-2207.
[26] Li Z Q, Chen H W, Xu B W. An Algorithm for Synthesis of Optimal 3-qubit Reversible Circuits based on Bit Operation, Genetic and Evolutionary Computing, WGEC, (2008), 455-458.
[27] Bergholm V, Vartiainen J. J, Mottonen M. Quantum Circuits with Uniformly Controlled One-Qubit Gates,Physical Review A,Vol.71, No.5, (2005), 1-7.
[28] Coffey M. W, Deiotte R, Semi, T. Comment on "Universal Quantum Circuit for Two-Qubit Transformations with Three Controlled-NOT Gates" and "Recognizing Small-Circuit Structure in Two-Qubit Operators", Physical ReviewA,Vol.77, No.6, (2008), 31-36.
[29] Iwama K, Kambayashi Y, Yamashita S. Transformation Rules for Designing CNOT-based Quantum Circuits, Proceedings 2002 Design Automation Conference (IEEE Cat. No.02CH37324), Vol.39, No.14, (2002), 419-424.
[30] Maslov D. Efficient Reversible Quantum Implementations of Symmetric Boolean Functions, IEEE Proceedings-Circuits Devices and Systems, Vol.153, No.5, (2006), 467-472.
[31] Maslov D, Dueck G. W. Improved Quantum Cost for n-bit Toffoli Gates, Electronics Letters, Vol.39, No.25, (2003), 1790-1791.
[32] Maslov D, Dueck G. W. Reversible Cascades with Minimal Garbage, IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems, Vol.l23, No.11,(2004), 1497-1509.
[33] Maslov D, Dueck, G. W, Miller D. M. Synthesis of Fredkin-Toffoli Reversible Networks, IEEE Transactions On Very Large Scale Integration (VLSI) Systems, Vol.13, No.6, (2005), 765-769.
[34] Shende V. V, Prasad A. K, Markov I. L. Synthesis of Reversible Logic Circuits, IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems, Vol.22, No.6, (2003), 710-722.
[35] Sedlak M, Plesch M. Towards Optimization of Quantum Circuits, Central European Journal Of Physics, Vol.6, No.1, (2008), 128-134.
[36]陈国良,王煦法,庄镇泉。遗传算法及其应用,北京:人民邮电出版社,(2001),157-162。
[37]周明,孙树栋。遗传算法原理及应用,北京:国防工业出版社,(1999),1-64。
[38] T Toffoli. Reversible Computing, Tech Memo MIT/LCS/TM-151, MIT Lab for Comp Sci,1980.
[2] M Nielsen, I Chuang. Quantum Computation and Quantum Information, Cambridge, UK: Cambridge University Press,2000.
[3] D Maslov. Reversible Logic Synthesis, The University of New Brunswick, 2003.
[4] V V Shende, A K Prasad, I L Markov. Synthesis of Reversible Logic Circuits, IEEE Trans Computer-Aided Design Integrated Circuits Systems, Vol.22, No.6, (2003), 723-729.
[5] G W Dueck, D Maslov. Reversible Function Synthesis with Minimum Garbage Outputs, Proc 6th Int Symp Represent Methodol Future Comput Technol, Trier, (2003), 154-161.
[6] D M Miller, G W Dueck. Spectral Techniques for Reversible Logic Synthesis, Proc 6th Int Symp Represent Methodol Future Comput Technol, Trier, (2003), 56-62.
[7] P Kerntopf. A New Heuristic Algorithm for Reversible Logic Synthesis, Proc Design Automation Conf. San Diego, (2004), 834-837.
[8] K Iwama, Y Kambayashi, S Yamashita. Transformation Rules for Designing CNOT-Based Quantum Circuits, Proc Design Automation Conf. New Orleans, (2002), 419-425.
[9] D Maslov, G W Dueck, D M Miller. Toffoli Network Synthesis with Templates, IEEE Trans Computer-Aided Design Integrated Circuits Systems, Vol.24, No.6, (2005), 807-817.
[10] G W Dueck, D Maslov, D M Miller. Transformation-Based Synthesis of Network of Toffoli/Fredkin Gates, Electrical and Computer Engineering 2003 IEEE CCECE, Montreal, (2003), 211-214.
[11] A Agrawal, N K Jha. Synthesis of Reversible Logic, Design, Automation and Test in Europe Conference and Exhibition, Paris, (2004), 1384-1385.
[12] P Gupta, A Agrawal, N K Jha. An Algorithm for Synthesis of Reversible Logic Circuits, IEEE Trans Computer-Aided Design of Integrated Circuits Systems, Vol.25, No.11, (2006), 2317-2330.
[13] A Mishchenko, M Perkowski. Logic Synthesis of Reversible Wave Cascodes, Proc Int Workshop Logic Synthesis, New Orleans, (2002), 197-202.
[14] D Maslov, G W Dueck, D M Miller. Simplication of Toffoli Networks via Templates, Proceedings Integrated Circuits and Systems Design, San Paulo,(2003), 53-58.
[15] D Maslov, C Young, D M Miller. Quantum Circuit Simplication using Templates , Design, Automation and Test in Europe, Munich, (2005), 1208-1213.
[16] M A Thornton. Fixed Polarity Reed-Muller Forms[EB/OL][2006-03-01] http://engr.smu.edu/mitch/class/8391/week12/esop.pdf.
[17] M A Thornton, R Drechsler, D M Miller. Spectral Techniques in VLSI CAD, Kluwer Academic Publishers, 2001.
[18] W N Hung, X Song, G Yang. Quantum Logic Synthesis by Symbolic Reachability Analysis, Proc Design Automation Conf. San Diego, (2004), 838-841.
[19] Shende V V, Bullock S S, Markov I L. Synthesis of Quantum Logic Circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.25, No.6, (2006),1000-1010.
[20] Yang G W, Song X Y, Hung W N. Group Theory based Synthesis of Binary Reversible Ccircuits, TAMC, (2006), 365-374.
[21] Yang G W, Song X Y, Hung W N. Fast Synthesis of Exact Minimal Reversible Circuits using Group Theory. Proceedings of IEEE ASP-DAC, Shanghai China, (2005), 18-21.
[22] Miller D M, Maslov D, Dueck G W. A Transformation based Algorithm for Reversible Logic Synthesis, DAC, Vol.11, No. 7 (2003), 318-321.
[23] Gupta P, Agrawal A, Jha N K. An Algorithm for Synthesis of Reversible Logic Circuits. IEEE Transactions on Circuits and Systems, Vol.25, No.11, (200611), 807-811.
[24] Ville R, Robert T D, Grobe D A. Fast Exact Toffoli Network Synthesis of Reversible Logic, IEEE Transactions on Computer-Aided Design, Vol.4, No.8, (2007), 60-64.
[25] Li Z Q, Chen H W, Xu B W. Fast Algorithm for 4-qubit Reversible Logic Circuits Synthesis, Evolutionary Computation,CEC,(2008), 2202-2207.
[26] Li Z Q, Chen H W, Xu B W. An Algorithm for Synthesis of Optimal 3-qubit Reversible Circuits based on Bit Operation, Genetic and Evolutionary Computing, WGEC, (2008), 455-458.
[27] Bergholm V, Vartiainen J. J, Mottonen M. Quantum Circuits with Uniformly Controlled One-Qubit Gates,Physical Review A,Vol.71, No.5, (2005), 1-7.
[28] Coffey M. W, Deiotte R, Semi, T. Comment on "Universal Quantum Circuit for Two-Qubit Transformations with Three Controlled-NOT Gates" and "Recognizing Small-Circuit Structure in Two-Qubit Operators", Physical ReviewA,Vol.77, No.6, (2008), 31-36.
[29] Iwama K, Kambayashi Y, Yamashita S. Transformation Rules for Designing CNOT-based Quantum Circuits, Proceedings 2002 Design Automation Conference (IEEE Cat. No.02CH37324), Vol.39, No.14, (2002), 419-424.
[30] Maslov D. Efficient Reversible Quantum Implementations of Symmetric Boolean Functions, IEEE Proceedings-Circuits Devices and Systems, Vol.153, No.5, (2006), 467-472.
[31] Maslov D, Dueck G. W. Improved Quantum Cost for n-bit Toffoli Gates, Electronics Letters, Vol.39, No.25, (2003), 1790-1791.
[32] Maslov D, Dueck G. W. Reversible Cascades with Minimal Garbage, IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems, Vol.l23, No.11,(2004), 1497-1509.
[33] Maslov D, Dueck, G. W, Miller D. M. Synthesis of Fredkin-Toffoli Reversible Networks, IEEE Transactions On Very Large Scale Integration (VLSI) Systems, Vol.13, No.6, (2005), 765-769.
[34] Shende V. V, Prasad A. K, Markov I. L. Synthesis of Reversible Logic Circuits, IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems, Vol.22, No.6, (2003), 710-722.
[35] Sedlak M, Plesch M. Towards Optimization of Quantum Circuits, Central European Journal Of Physics, Vol.6, No.1, (2008), 128-134.
[36]陈国良,王煦法,庄镇泉。遗传算法及其应用,北京:人民邮电出版社,(2001),157-162。
[37]周明,孙树栋。遗传算法原理及应用,北京:国防工业出版社,(1999),1-64。
[38] T Toffoli. Reversible Computing, Tech Memo MIT/LCS/TM-151, MIT Lab for Comp Sci,1980.