Reversible circuit synthesis by genetic programming using dynamic gate libraries | Quantum Information Processing Skip to main content
Springer Nature Link
Log in

Reversible circuit synthesis by genetic programming using dynamic gate libraries

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

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)

    Article  ADS  Google Scholar 

  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)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  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)

    Book  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    MathSciNet  Google Scholar 

  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)

    Google Scholar 

  16. Toffoli, T.: Reversible Computing. Springer, Berlin (1980)

    Book  MATH  Google Scholar 

  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)

  18. Zakablukov, D.V.: Fast synthesis of invertible circuits based on permutation group theory. Prikl. Diskretn. Mat. 2, 101–109 (2014)

    Google Scholar 

  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)

    Article  Google Scholar 

  20. Saeedi, M., Markov, I.L.: Synthesis and optimization of reversible circuits: a survey. ACM Comput. Surv. (CSUR) 45(2), 21 (2013)

    Article  MATH  Google Scholar 

  21. Saeedi, M., Sedighi, M., Zamani, M.S.: A library-based synthesis methodology for reversible logic. Microelectron. J. 41(4), 185–194 (2010)

    Article  Google Scholar 

  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)

  24. Younes, A.: Reducing quantum cost of reversible circuits for homogeneous boolean functions. J. Circuits Syst. Comput. 19(07), 1423–1434 (2010)

    Article  Google Scholar 

  25. Mukhanov, O., et al.: Energy-effecient single UX quantum technology. IEEE Trans. Appl. Supercond. 21(3), 760–769 (2011)

    Article  ADS  Google Scholar 

  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)

    Article  Google Scholar 

  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)

  29. Bahauddin, S.M., Irfan, A.A.M.: Permutation algebra for constructing reversible circuits. J. Quantum Inf. Sci. 2(03), 61 (2012)

    Article  Google Scholar 

  30. Younes, A.: Tight bounds on the synthesis of 3-bit reversible circuits: Nr library. J. Circuits Syst. Comput. 23(03), 1450040 (2014)

    Article  Google Scholar 

  31. Zakablukov, D.: Application of Permutation group Theory in Reversible Logic Synthesis, arXiv preprint arXiv:1507.04309 (2015)

  32. Younes, A.: On the universality of n-bit reversible gate libraries. Appl. Math. Inf. Sci 9(5), 2579–2588 (2015)

    MathSciNet  Google Scholar 

  33. Zakablukov, D.: On Asymptotic Gate Complexity and Depth of Reversible Circuits Without Additional Memory, arXiv preprint arXiv:1504.06876 (2015)

  34. Arabzadeh, M., Zamani, M.S., Sedighi, M., Saeedi, M.: Depth-optimized reversible circuit synthesis. Quantum Inf. Process. 12(4), 1677–1699 (2013)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  35. Rayner, M., Newman, D.J.: On the symmetry of logic. J. Phys. A Math. Gen. 28(19), 5623 (1995)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  36. Storme, L., De Vos, A., Jacobs, G.: Group theoretical aspects of reversible logic gates. J. Univ. Comput. Sci. 5(5), 307–321 (1999)

    MATH  Google Scholar 

  37. De Vos, A.: Reversible computing. Prog. Quantum Electron. 23(1), 1–49 (1999)

    Article  ADS  Google Scholar 

  38. Al-Rabadi, A.N.: Reversible Logic Synthesis: From Fundamentals to Quantum Computing. Springer, Berlin (2012)

    MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    MATH  Google Scholar 

  51. Vatan, F., Williams, C.: Optimal quantum circuits for general two-qubit gates. Phys. Rev. A 69(3), 032315 (2004)

    Article  ADS  Google Scholar 

  52. Williams, C.P., Gray, A.G.: Automated Design of Quantum Circuits. Springer, Berlin (1999)

    Book  MATH  Google Scholar 

  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)

    MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  Google Scholar 

  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)

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

Download references

Author information

Authors and Affiliations

  1. Computer and Information Science Department, Universiti Teknologi PETRONAS, 32610, Seri Iskandar, Perak, Malaysia

    Mustapha Y. Abubakar, Low Tang Jung & Nordin Zakaria

  2. Department of Computer Science, School of Technology, Kano State Polytechnic, Kano, Nigeria

    Mustapha Y. Abubakar

  3. Mathematics and Computer Science, Alexandria University, Alexandria, Egypt

    Ahmed Younes

  4. Department of Physics, Faculty of Science, Al-Azhar University, Asyût, Egypt

    Abdel-Haleem Abdel-Aty

Authors
  1. Mustapha Y. Abubakar
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Low Tang Jung
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Nordin Zakaria
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Ahmed Younes
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Abdel-Haleem Abdel-Aty
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Abdel-Haleem Abdel-Aty.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Abubakar, M.Y., Jung, L.T., Zakaria, N. et al. Reversible circuit synthesis by genetic programming using dynamic gate libraries. Quantum Inf Process 16, 160 (2017). https://doi.org/10.1007/s11128-017-1609-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-017-1609-8

Keywords