Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 6/2017

01.06.2017

Reversible circuit synthesis by genetic programming using dynamic gate libraries

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

Erschienen in: Quantum Information Processing | Ausgabe 6/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Good and asymptotically good quantum codes derived from algebraic geometry
Nächster Artikel The excitonic qubit coupled with a phonon bath on a star graph: anomalous decoherence and coherence revivals

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Literatur
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)ADSCrossRef
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)ADSMathSciNetCrossRefMATH
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.
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)MathSciNet
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.
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)
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)CrossRef
20.
Saeedi, M., Markov, I.L.: Synthesis and optimization of reversible circuits: a survey. ACM Comput. Surv. (CSUR) 45(2), 21 (2013)CrossRefMATH
21.
Saeedi, M., Sedighi, M., Zamani, M.S.: A library-based synthesis methodology for reversible logic. Microelectron. J. 41(4), 185–194 (2010)CrossRef
22.
Mamun, M., Al, S., Menville, D.: Quantum Cost Optimization for Reversible Sequential Circuit, arXiv preprint arXiv:​1407.​7098 (2014)
23.
24.
Younes, A.: Reducing quantum cost of reversible circuits for homogeneous boolean functions. J. Circuits Syst. Comput. 19(07), 1423–1434 (2010)CrossRef
25.
Mukhanov, O., et al.: Energy-effecient single UX quantum technology. IEEE Trans. Appl. Supercond. 21(3), 760–769 (2011)ADSCrossRef
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)CrossRef
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)CrossRef
30.
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.
Younes, A.: On the universality of n-bit reversible gate libraries. Appl. Math. Inf. Sci 9(5), 2579–2588 (2015)MathSciNet
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)ADSMathSciNetCrossRefMATH
35.
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
37.
38.
Al-Rabadi, A.N.: Reversible Logic Synthesis: From Fundamentals to Quantum Computing. Springer, Berlin (2012)MATH
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)CrossRef
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)CrossRef
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)CrossRef
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)CrossRef
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
51.
Vatan, F., Williams, C.: Optimal quantum circuits for general two-qubit gates. Phys. Rev. A 69(3), 032315 (2004)ADSCrossRef
52.
Williams, C.P., Gray, A.G.: Automated Design of Quantum Circuits. Springer, Berlin (1999)CrossRefMATH
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
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.
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)CrossRef
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)CrossRef
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)CrossRef
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)MathSciNetMATH
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)CrossRef
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)MathSciNetCrossRef
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)CrossRef
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)CrossRef
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)CrossRef
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.
71.
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)
Metadaten
Titel
Reversible circuit synthesis by genetic programming using dynamic gate libraries
verfasst von
Mustapha Y. Abubakar
Low Tang Jung
Nordin Zakaria
Ahmed Younes
Abdel-Haleem Abdel-Aty
Publikationsdatum
01.06.2017
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 6/2017
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-017-1609-8

Weitere Artikel der Ausgabe 6/2017

Quantum Information Processing 6/2017 Zur Ausgabe

OriginalPaper

Analysis of various factors affecting the non-Markovian dynamics associated with a hierarchical environment based on collision model

OriginalPaper

Quantum arithmetic with the quantum Fourier transform

OriginalPaper

Mutually unbiased maximally entangled bases in

OriginalPaper

Quantum image encryption scheme with iterative generalized Arnold transforms and quantum image cycle shift operations

OriginalPaper

Quantum load balancing in ad hoc networks

OriginalPaper

Controller-independent bidirectional quantum direct communication

Neuer Inhalt

    Bildnachweise