Skip to main content
Top
Published in: Quantum Information Processing 6/2017

01-06-2017

Reversible circuit synthesis by genetic programming using dynamic gate libraries

Authors: Mustapha Y. Abubakar, Low Tang Jung, Nordin Zakaria, Ahmed Younes, Abdel-Haleem Abdel-Aty

Published in: Quantum Information Processing | Issue 6/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference 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 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.
go back to reference 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 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.
go back to reference 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)ADSCrossRef 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)ADSCrossRef
4.
go back to reference 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)ADSMathSciNetCrossRefMATH 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)ADSMathSciNetCrossRefMATH
5.
go back to reference 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) 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)
7.
go back to reference Donald, J., Jha, N.K.: Reversible logic synthesis with Fredkin and Peres gates. ACM J. Emerg. Technol. Comput. Syst. (JETC) 4(1), 2 (2008) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Kerntopf, P.: A new heuristic algorithm for reversible logic synthesis. In: Proceedings of the 41st Annual Design Automation Conference, pp. 834–837. ACM (2004) 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.
go back to reference 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) 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.
go back to reference 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 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
13.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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)
17.
go back to reference 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) 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.
go back to reference Zakablukov, D.V.: Fast synthesis of invertible circuits based on permutation group theory. Prikl. Diskretn. Mat. 2, 101–109 (2014) Zakablukov, D.V.: Fast synthesis of invertible circuits based on permutation group theory. Prikl. Diskretn. Mat. 2, 101–109 (2014)
19.
go back to reference 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)CrossRef 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)CrossRef
20.
go back to reference Saeedi, M., Markov, I.L.: Synthesis and optimization of reversible circuits: a survey. ACM Comput. Surv. (CSUR) 45(2), 21 (2013)CrossRefMATH Saeedi, M., Markov, I.L.: Synthesis and optimization of reversible circuits: a survey. ACM Comput. Surv. (CSUR) 45(2), 21 (2013)CrossRefMATH
21.
go back to reference Saeedi, M., Sedighi, M., Zamani, M.S.: A library-based synthesis methodology for reversible logic. Microelectron. J. 41(4), 185–194 (2010)CrossRef Saeedi, M., Sedighi, M., Zamani, M.S.: A library-based synthesis methodology for reversible logic. Microelectron. J. 41(4), 185–194 (2010)CrossRef
22.
go back to reference Mamun, M., Al, S., Menville, D.: Quantum Cost Optimization for Reversible Sequential Circuit, arXiv preprint arXiv:1407.7098 (2014) Mamun, M., Al, S., Menville, D.: Quantum Cost Optimization for Reversible Sequential Circuit, arXiv preprint arXiv:​1407.​7098 (2014)
23.
24.
go back to reference Younes, A.: Reducing quantum cost of reversible circuits for homogeneous boolean functions. J. Circuits Syst. Comput. 19(07), 1423–1434 (2010)CrossRef Younes, A.: Reducing quantum cost of reversible circuits for homogeneous boolean functions. J. Circuits Syst. Comput. 19(07), 1423–1434 (2010)CrossRef
25.
go back to reference Mukhanov, O., et al.: Energy-effecient single UX quantum technology. IEEE Trans. Appl. Supercond. 21(3), 760–769 (2011)ADSCrossRef Mukhanov, O., et al.: Energy-effecient single UX quantum technology. IEEE Trans. Appl. Supercond. 21(3), 760–769 (2011)ADSCrossRef
26.
go back to reference 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)CrossRef 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)CrossRef
27.
go back to reference 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) 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.
go back to reference Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, UK (2000) Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, UK (2000)
29.
go back to reference Bahauddin, S.M., Irfan, A.A.M.: Permutation algebra for constructing reversible circuits. J. Quantum Inf. Sci. 2(03), 61 (2012)CrossRef Bahauddin, S.M., Irfan, A.A.M.: Permutation algebra for constructing reversible circuits. J. Quantum Inf. Sci. 2(03), 61 (2012)CrossRef
30.
go back to reference Younes, A.: Tight bounds on the synthesis of 3-bit reversible circuits: Nr library. J. Circuits Syst. Comput. 23(03), 1450040 (2014)CrossRef Younes, A.: Tight bounds on the synthesis of 3-bit reversible circuits: Nr library. J. Circuits Syst. Comput. 23(03), 1450040 (2014)CrossRef
31.
32.
go back to reference Younes, A.: On the universality of n-bit reversible gate libraries. Appl. Math. Inf. Sci 9(5), 2579–2588 (2015)MathSciNet Younes, A.: On the universality of n-bit reversible gate libraries. Appl. Math. Inf. Sci 9(5), 2579–2588 (2015)MathSciNet
33.
go back to reference Zakablukov, D.: On Asymptotic Gate Complexity and Depth of Reversible Circuits Without Additional Memory, arXiv preprint arXiv:1504.06876 (2015) Zakablukov, D.: On Asymptotic Gate Complexity and Depth of Reversible Circuits Without Additional Memory, arXiv preprint arXiv:​1504.​06876 (2015)
34.
go back to reference Arabzadeh, M., Zamani, M.S., Sedighi, M., Saeedi, M.: Depth-optimized reversible circuit synthesis. Quantum Inf. Process. 12(4), 1677–1699 (2013)ADSMathSciNetCrossRefMATH Arabzadeh, M., Zamani, M.S., Sedighi, M., Saeedi, M.: Depth-optimized reversible circuit synthesis. Quantum Inf. Process. 12(4), 1677–1699 (2013)ADSMathSciNetCrossRefMATH
36.
go back to reference Storme, L., De Vos, A., Jacobs, G.: Group theoretical aspects of reversible logic gates. J. Univ. Comput. Sci. 5(5), 307–321 (1999)MATH Storme, L., De Vos, A., Jacobs, G.: Group theoretical aspects of reversible logic gates. J. Univ. Comput. Sci. 5(5), 307–321 (1999)MATH
37.
38.
go back to reference Al-Rabadi, A.N.: Reversible Logic Synthesis: From Fundamentals to Quantum Computing. Springer, Berlin (2012)MATH Al-Rabadi, A.N.: Reversible Logic Synthesis: From Fundamentals to Quantum Computing. Springer, Berlin (2012)MATH
39.
go back to reference 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) 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.
go back to reference 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)CrossRef 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)CrossRef
41.
go back to reference 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)CrossRef 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)CrossRef
42.
go back to reference 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)CrossRef 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)CrossRef
43.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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)CrossRef 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)CrossRef
46.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Lukac, M., Perkowski, M.: Evolving quantum circuits using genetic algorithm. In: Evolvable Hardware. Proceedings. NASA/DoD Conference on, pp. 177–185. IEEE (2002) Lukac, M., Perkowski, M.: Evolving quantum circuits using genetic algorithm. In: Evolvable Hardware. Proceedings. NASA/DoD Conference on, pp. 177–185. IEEE (2002)
49.
go back to reference 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) 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.
go back to reference Bautu, A., Bautu, E.: Quantum circuit design by means of genetic programming. Roman. Phys. 52(5–7), 697–704 (2007)MATH Bautu, A., Bautu, E.: Quantum circuit design by means of genetic programming. Roman. Phys. 52(5–7), 697–704 (2007)MATH
51.
go back to reference Vatan, F., Williams, C.: Optimal quantum circuits for general two-qubit gates. Phys. Rev. A 69(3), 032315 (2004)ADSCrossRef Vatan, F., Williams, C.: Optimal quantum circuits for general two-qubit gates. Phys. Rev. A 69(3), 032315 (2004)ADSCrossRef
52.
53.
go back to reference 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) 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.
go back to reference Spector, L.: Automatic Quantum Computer Programming: A Genetic Programming approach, vol. 7. Springer, Berlin (2006)MATH Spector, L.: Automatic Quantum Computer Programming: A Genetic Programming approach, vol. 7. Springer, Berlin (2006)MATH
55.
go back to reference 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) 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)
57.
go back to reference 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)CrossRef 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)CrossRef
58.
go back to reference 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)CrossRef 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)CrossRef
59.
go back to reference 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)CrossRef 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)CrossRef
60.
go back to reference Wille, R., Saeedi, M., Drechsler, R.: Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost. arXiv preprint arXiv:1004.4609 (2010) Wille, R., Saeedi, M., Drechsler, R.: Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost. arXiv preprint arXiv:​1004.​4609 (2010)
61.
go back to reference 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) 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.
go back to reference 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)MathSciNetMATH 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)MathSciNetMATH
63.
go back to reference 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)CrossRef 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)CrossRef
64.
go back to reference 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) 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.
go back to reference Golubitsky, O., Maslov, D.: A study of optimal 4-bit reversible toffoli circuits and their synthesis. IEEE Trans. Comput. 61(9), 1341–1353 (2012)MathSciNetCrossRef Golubitsky, O., Maslov, D.: A study of optimal 4-bit reversible toffoli circuits and their synthesis. IEEE Trans. Comput. 61(9), 1341–1353 (2012)MathSciNetCrossRef
66.
go back to reference 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)CrossRef 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)CrossRef
67.
go back to reference 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)CrossRef 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)CrossRef
68.
go back to reference 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)CrossRef 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)CrossRef
69.
go back to reference 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) 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)
72.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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)
Metadata
Title
Reversible circuit synthesis by genetic programming using dynamic gate libraries
Authors
Mustapha Y. Abubakar
Low Tang Jung
Nordin Zakaria
Ahmed Younes
Abdel-Haleem Abdel-Aty
Publication date
01-06-2017
Publisher
Springer US
Published in
Quantum Information Processing / Issue 6/2017
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-017-1609-8

Other articles of this Issue 6/2017

Quantum Information Processing 6/2017 Go to the issue