Reversible circuit synthesis by genetic programming using dynamic gate libraries. (English) Zbl 1373.81131
Summary: We have defined a new method for automatic construction of reversible logic circuits by using the genetic programming approach. The choice of the gate library is 100% dynamic. The algorithm is capable of accepting all possible combinations of the following gate types: NOT TOFFOLI, NOT PERES, NOT CNOT TOFFOLI, NOT CNOT SWAP FREDKIN, NOT CNOT TOFFOLI SWAP FREDKIN, NOT CNOT PERES, NOT CNOT SWAP FREDKIN PERES, NOT CNOT TOFFOLI PERES and NOT CNOT TOFFOLI SWAP FREDKIN PERES. Our method produced near optimum circuits in some cases when a particular subset of gate types was used in the library. Meanwhile, in some cases, optimal circuits were produced due to the heuristic nature of the algorithm. We compared the outcomes of our method with several existing synthesis methods, and it was shown that our algorithm performed relatively well compared to the previous synthesis methods in terms of the output efficiency of the algorithm and execution time as well.
MSC:
| 81P68 | Quantum computation |
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 94C05 | Analytic circuit theory |
References:
| [1] | Maslov, D., Dueck, G.W., Miller, D.M.: Fredkin-Toffoli templates for reversible logic synthesis. In: Proceedings of the 2003 IEEE-ACM International Conference on Computer-Aided Design, Ser. ICCAD ’03, p. 256. IEEE Computer Society, Washington (2003). doi:10.1109/ICCAD.2003.73 |
| [2] | Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Reversible logic circuit synthesis. In: Proceedings of the 2002 IEEE/ACM International Conference on Computer-Aided Design, Ser. ICCAD ’02, pp. 353-360. ACM, New York (2002). doi:10.1145/774572.774625 |
| [3] | Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457 (1995) · doi:10.1103/PhysRevA.52.3457 |
| [4] | De Vos, A., Van Rentergem, Y., De Keyser, K.: The decomposition of an arbitrary reversible logic circuit. J. Phys. A Math. Gen. 39(18), 5015 (2006) · Zbl 1090.94030 · doi:10.1088/0305-4470/39/18/017 |
| [5] | De Vos, A., Desoete, B., Adamski, A., Pietrzak, P., Sibinski, M., Widerski, T.: Design of reversible logic circuits by means of control gates. In: Integrated Circuit Design, pp. 255-264. Springer, Berlin (2000) |
| [6] | Fredkin, E., Toffoli, T.: Conservative Logic. Springer, Berlin (2002) · Zbl 0496.94015 · doi:10.1007/978-1-4471-0129-1_3 |
| [7] | Donald, J., Jha, N.K.: Reversible logic synthesis with Fredkin and Peres gates. ACM J. Emerg. Technol. Comput. Syst. (JETC) 4(1), 2 (2008) |
| [8] | Fazel, K., Thornton, M., Rice, J.: ESOP-based Toffoli gate cascade generation. In: IEEE Pacific Conference on Communications, Computers and Signal Processing, pp. 206-209. Citeseer (2007) |
| [9] | Grobe, D., Chen, X., Dueck, G.W., Drechsler, R.: Exact SAT-based Toffoli network synthesis. In: Proceedings of the 17th ACM Great Lakes Symposium on VLSI, pp. 96-101. ACM (2007) |
| [10] | Kerntopf, P.: A new heuristic algorithm for reversible logic synthesis. In: Proceedings of the 41st Annual Design Automation Conference, pp. 834-837. ACM (2004) |
| [11] | Lukac, M., Pivtoraiko, M., Mishchenko, A., Perkowski, M.: Automated synthesis of generalized reversible cascades using genetic algorithms. In: Proceedings of the 5th International Workshop on Boolean Problems, 2002. Citeseer (2002) |
| [12] | Markov, K.N.P.I.L., Hayes, J.P.: Optimal synthesis of linear reversible circuits. Quantum Inf. Comput. 8(3 and 4), 0282-0294 (2008) · Zbl 1152.81794 |
| [13] | Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: Proceedings of the 40th Annual Design Automation Conference, pp. 318-323. ACM (2003) |
| [14] | Rubinstein, B.I.: Evolving quantum circuits using genetic programming. In: Evolutionary Computation. Proceedings of the 2001 Congress on, vol. 1, pp. 144-151. IEEE (2001) |
| [15] | Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Reversible circuit synthesis using a cycle-based approach. ACM J. Emerg. Technol. Comput. Syst. (JETC) 6(4), 13 (2010) |
| [16] | Toffoli, T.: Reversible Computing. Springer, Berlin (1980) · Zbl 0443.68038 · doi:10.1007/3-540-10003-2_104 |
| [17] | R. Wille and R. Drechsler, BDD-based synthesis of reversible logic for large functions. In: Proceedings of the 46th Annual Design Automation Conference, pp. 270-275. ACM (2009) · Zbl 1267.81108 |
| [18] | Zakablukov, D.V.: Fast synthesis of invertible circuits based on permutation group theory. Prikl. Diskretn. Mat. 2, 101-109 (2014) · Zbl 1504.94249 |
| [19] | Maslov, D., Dueck, G.W., Miller, D.M., Negrevergne, C.: Quantum circuit simplification and level compaction. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 27(3), 436-444 (2008) · doi:10.1109/TCAD.2007.911334 |
| [20] | Saeedi, M., Markov, I.L.: Synthesis and optimization of reversible circuits: a survey. ACM Comput. Surv. (CSUR) 45(2), 21 (2013) · Zbl 1293.94141 · doi:10.1145/2431211.2431220 |
| [21] | Saeedi, M., Sedighi, M., Zamani, M.S.: A library-based synthesis methodology for reversible logic. Microelectron. J. 41(4), 185-194 (2010) · doi:10.1016/j.mejo.2010.02.002 |
| [22] | Mamun, M., Al, S., Menville, D.: Quantum Cost Optimization for Reversible Sequential Circuit, arXiv preprint arXiv:1407.7098 (2014) |
| [23] | Szyprowski, M., Kerntopf, P.: Reducing Quantum Cost in Reversible Toffoli Circuits. arXiv preprint arXiv:1105.5831 (2011) · Zbl 1451.81155 |
| [24] | Younes, A.: Reducing quantum cost of reversible circuits for homogeneous boolean functions. J. Circuits Syst. Comput. 19(07), 1423-1434 (2010) · doi:10.1142/S0218126610006736 |
| [25] | Mukhanov, O., et al.: Energy-effecient single UX quantum technology. IEEE Trans. Appl. Supercond. 21(3), 760-769 (2011) · doi:10.1109/TASC.2010.2096792 |
| [26] | Ye, Y., Roy, K.: Energy recovery circuits using reversible and partially reversible logic. IEEE Trans. Circuits Syst. I Fundam. Theory Appl. 43(9), 769-778 (1996) · doi:10.1109/81.536746 |
| [27] | Athas, W.C., Svensson, L.: Reversible logic issues in adiabatic CMOS. In: Physics and Computation. PhysComp’94, Proceedings, Workshop on, pp. 111-118. IEEE (1994) |
| [28] | Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, UK (2000) · Zbl 1049.81015 |
| [29] | Bahauddin, S.M., Irfan, A.A.M.: Permutation algebra for constructing reversible circuits. J. Quantum Inf. Sci. 2(03), 61 (2012) · doi:10.4236/jqis.2012.23011 |
| [30] | Younes, A.: Tight bounds on the synthesis of 3-bit reversible circuits: Nr library. J. Circuits Syst. Comput. 23(03), 1450040 (2014) · doi:10.1142/S0218126614500406 |
| [31] | Zakablukov, D.: Application of Permutation group Theory in Reversible Logic Synthesis, arXiv preprint arXiv:1507.04309 (2015) · Zbl 1480.94059 |
| [32] | Younes, A.: On the universality of n-bit reversible gate libraries. Appl. Math. Inf. Sci 9(5), 2579-2588 (2015) |
| [33] | Zakablukov, D.: On Asymptotic Gate Complexity and Depth of Reversible Circuits Without Additional Memory, arXiv preprint arXiv:1504.06876 (2015) · Zbl 1391.94921 |
| [34] | Arabzadeh, M., Zamani, M.S., Sedighi, M., Saeedi, M.: Depth-optimized reversible circuit synthesis. Quantum Inf. Process. 12(4), 1677-1699 (2013) · Zbl 1267.81108 · doi:10.1007/s11128-012-0482-8 |
| [35] | Rayner, M., Newman, D.J.: On the symmetry of logic. J. Phys. A Math. Gen. 28(19), 5623 (1995) · Zbl 0866.94032 · doi:10.1088/0305-4470/28/19/016 |
| [36] | Storme, L., De Vos, A., Jacobs, G.: Group theoretical aspects of reversible logic gates. J. Univ. Comput. Sci. 5(5), 307-321 (1999) · Zbl 0961.68008 |
| [37] | De Vos, A.: Reversible computing. Prog. Quantum Electron. 23(1), 1-49 (1999) · doi:10.1016/S0079-6727(99)00002-6 |
| [38] | Al-Rabadi, A.N.: Reversible Logic Synthesis: From Fundamentals to Quantum Computing. Springer, Berlin (2012) · Zbl 1140.94022 |
| [39] | Perkowski, M., Al-Rabadi, A., Kerntopf, P., Buller, A., Chrzanowska-Jeske, M., Mishchenko, A., Azad Khan, M., Coppola, A., Yanushkevich, S., Shmerko, V., Jozwiak. L.: A general decomposition for reversible logic. In: Proceedings of RM, pp. 119-138 (2001) |
| [40] | Maslov, D., Dueck, G.W., Miller, D.M.: Synthesis of Fredkin-Toffoli reversible networks. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 13(6), 765-769 (2005) · doi:10.1109/TVLSI.2005.844284 |
| [41] | Gupta, P., Agrawal, A., Jha, N.K.: An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 25(11), 2317-2330 (2006) · doi:10.1109/TCAD.2006.871622 |
| [42] | Maslov, D., Dueck, G.W., Miller, D.M.: Techniques for the synthesis of reversible toffoli networks. ACM Trans. Des. Autom. Electron. Syst. (TODAES) 12(4), 42 (2007) · doi:10.1145/1278349.1278355 |
| [43] | Wille, R., Le, H.M., Dueck, G.W., Grobe, D.: Quantied synthesis of reversible logic. In: Design, Automation and Test in Europe. DATE’08, pp. 1015-1020. IEEE (2008) |
| [44] | Yang, G., Song, X., Hung, W.N., Perkowski, M.A.: Fast synthesis of exact minimal reversible circuits using group theory. In: Proceedings of the 2005 Asia and South Pacific Design Automation Conference, pp. 1002-1005. ACM (2005) |
| [45] | Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Synthesis of reversible logic circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 22(6), 710-722 (2003) · doi:10.1109/TCAD.2003.811448 |
| [46] | Nagamani, A., Ashwin, S., Abhishek, B., Agrawal, V.: An exact approach for complete test set generation of Toffoli-Fredkin-Peres based reversible circuits. J. Electron. Test. 32(2), 175-196 (2016) |
| [47] | Maslov, D., Young, C., Miller, D.M., Dueck, G.W.: Quantum circuit simplification using templates. In: Design, Automation and Test in Europe. Proceedings, pp. 1208-1213. IEEE (2005) |
| [48] | Lukac, M., Perkowski, M.: Evolving quantum circuits using genetic algorithm. In: Evolvable Hardware. Proceedings. NASA/DoD Conference on, pp. 177-185. IEEE (2002) |
| [49] | Ruican, C., Udrescu, M., Prodan, L., Vladutiu, M.: Genetic algorithm based quantum circuit synthesis with adaptive parameters control. In: Evolutionary Computation. CEC’09. IEEE Congress on, pp. 896-903. IEEE (2009) |
| [50] | Bautu, A., Bautu, E.: Quantum circuit design by means of genetic programming. Roman. Phys. 52(5-7), 697-704 (2007) · Zbl 1224.93002 |
| [51] | Vatan, F., Williams, C.: Optimal quantum circuits for general two-qubit gates. Phys. Rev. A 69(3), 032315 (2004) · doi:10.1103/PhysRevA.69.032315 |
| [52] | Williams, C.P., Gray, A.G.: Automated Design of Quantum Circuits. Springer, Berlin (1999) · Zbl 0945.68061 · doi:10.1007/3-540-49208-9_8 |
| [53] | Yabuki, T., Iba, H.: Genetic algorithms for quantum circuit design-evolving a simpler teleportation circuit. In: Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference. Citeseer, pp. 421-425 (2000) |
| [54] | Spector, L.: Automatic Quantum Computer Programming: A Genetic Programming approach, vol. 7. Springer, Berlin (2006) · Zbl 1131.68461 |
| [55] | Kameyama, M., Lukac, M., Perkowski, M.: Evolutionary Quantum Logic Synthesis of Boolean Reversible Logic Circuits Embedded in Ternary Quantum Space Using Heuristics, arXiv preprint arXiv:1107.3383 (2011) |
| [56] | GAP, Groups, Algorithms, and Programming, Version 4.8.3, http://www.gap-system.org. Accessed 04 Aug 2016 (2016) |
| [57] | Prasad, A.K., Shende, V.V., Markov, I.L., Hayes, J.P., Patel, K.N.: Data structures and algorithms for simplifying reversible circuits. ACM J. Emerg. Technol. Comput. Syst. (JETC) 2(4), 277-293 (2006) · doi:10.1145/1216396.1216399 |
| [58] | Hung, W.N., Song, X., Yang, G., Yang, J., Perkowski, M.: Optimal synthesis of multiple output boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 25(9), 1652-1663 (2006) · doi:10.1109/TCAD.2005.858352 |
| [59] | Maslov, D., Miller, D.M.: Comparison of the cost metrics through investigation of the relation between optimal NCV and optimal nct three-qubit reversible circuits. Comput. Digit. Tech. IET 1(2), 98-104 (2007) · doi:10.1049/iet-cdt:20060070 |
| [60] | Wille, R., Saeedi, M., Drechsler, R.: Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost. arXiv preprint arXiv:1004.4609 (2010) |
| [61] | Arabzadeh, M., Saeedi, M., Zamani, M.S.: Rule-based optimization of reversible circuits. In: Proceedings of the 2010 Asia and South Pacific Design Automation Conference, pp. 849-854. IEEE Press (2010) |
| [62] | Hirata, Y., Nakanishi, M., Yamashita, S., Nakashima, Y.: An efficient conversion of quantum circuits to a linear nearest neighbor architecture. Quantum Inf. Comput. 11(1), 142-166 (2011) · Zbl 1237.81050 |
| [63] | Maslov, D., Saeedi, M.: Reversible circuit optimization via leaving the boolean domain. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 30(6), 806-816 (2011) · doi:10.1109/TCAD.2011.2105555 |
| [64] | Z. Sasanian, R. Wille, and D.M. Miller, Realizing reversible circuits using a new class of quantum gates, In: Proceedings of the 49th Annual Design Automation Conference, pp. 36-41. ACM (2012) · Zbl 1237.81050 |
| [65] | Golubitsky, O., Maslov, D.: A study of optimal 4-bit reversible toffoli circuits and their synthesis. IEEE Trans. Comput. 61(9), 1341-1353 (2012) · Zbl 1365.94657 · doi:10.1109/TC.2011.144 |
| [66] | Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 32(6), 818-830 (2013) · doi:10.1109/TCAD.2013.2244643 |
| [67] | Amy, M., Maslov, D., Mosca, M.: Polynomial-time t-depth optimization of Clifford circuits via matroid partitioning. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 33(10), 1476-1489 (2014) · doi:10.1109/TCAD.2014.2341953 |
| [68] | Sasamal, T.N., Singh, A.K., Mohan, A.: Reversible logic circuit synthesis and optimization using adaptive genetic algorithm. Proc. Comput. Sci. 70, 407-413 (2015) · doi:10.1016/j.procs.2015.10.054 |
| [69] | Hawash, M.M.: Methods for efficient synthesis of large reversible binary and ternary quantum circuits and applications of linear nearest neighbor model. Ph.D. dissertation, Portland State University (2013) |
| [70] | Maslov, D.: Reversible Logic Synthesis Benchmarks Page. Retrieved 28 Feb 2016, from http://webhome.cs.uvic.ca/dmaslov/ (2016) |
| [71] | Dmitri, M.: Reversible Logic Synthesis Benchmarks Page, http://webhome.cs.uvic.ca/dmaslov/. Accessed 18 Aug 2016 (2016) |
| [72] | Saeedi, M., Zamani, M.S., Sedighi, M.: Moving forward: a non-search based synthesis method toward efficient cnot-based quantum circuit synthesis algorithms. In: Proceedings of the 2008 Asia and South Pacific Design Automation Conference, pp. 83-88. IEEE Computer Society Press (2008) |
| [73] | Li, M., Zheng, Y., Hsiao, M.S., Huang, C.: Reversible logic synthesis through ant colony optimization. In: 2010 Design, Automation and Test in Europe Conference and Exhibition (DATE 2010), pp. 307-310. IEEE (2010) |
| [74] | Wille, R., Grobe, D., Dueck, G.W., Drechsler, R.: Reversible logic synthesis with output permutation. In: 2009 22nd International Conference on VLSI Design, pp. 189-194. IEEE (2009) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
