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
Erschienen in:
Evolvable Hardware Challenges: Past, Present and the Path to a Promising Future Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits

verfasst von : Ahmed Younes

Erschienen in: Inspired by Nature

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

There have been efforts to find an automatic way to create efficient Boolean quantum circuits, because of their wide range of applications. This chapter shows how to build efficient Boolean quantum circuits. A direct synthesis method can be used to implement any Boolean function as a quantum circuit using its truth table, where the generated circuits are more efficient than ones generated using methods proposed by others. The chapter shows, using another method, that there is a direct correspondence between Boolean quantum operations and the classical Reed-Muller expansions. This relation makes it possible for the problem of synthesis and optimization of Boolean quantum circuits to be tackled within the domain of Reed-Muller logic under manufacturing constraints, for example, the interaction between qubits of the system.

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
Vorheriges Kapitel Evolution in Nanomaterio: The NASCENCE Project
Nächstes Kapitel Some Remarks on Code Evolution with Genetic Programming
Literatur
1.
Akers, S.B.: On a theory of Boolean functions. J. SIAM 7, 487–489 (1959)
2.
Akers, S.B.: Binary decision diagrams. IEEE Trans. Comput. C-27(6), 509–516 (1978)
3.
Almaini, A.: Electronic Logic Systems, chapter 12: Modulo-2 Logic Circuits, p. 470, 2nd edn. Prentice-Hall, Englewood Cliffs, NJ (1989)
4.
5.
Barenco, A., Bennett, C., Cleve, R., Divincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)CrossRef
6.
Barnum, H., Bernstein, H., Spector, L.: Quantum circuits for OR and AND of ORs. J. Phys. A: Math. Gen. 33(45), 8047–8057 (2000)CrossRefMATHMathSciNet
7.
8.
Benioff, P.: Quantum mechanical hamiltonian models of Turing machines that dissipate no energy. Phys. Rev. Lett. 48, 1581–1585 (1982)CrossRefMathSciNet
9.
10.
Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)CrossRefMATHMathSciNet
11.
Bennett, C., Bessette, F., Brassard, G., Salvail, L., Smolin, J.: Experimental quantum cryptography. J. Cryptol. 5(1), 3–28 (1992)CrossRefMATH
12.
13.
Berthiaume, A., Brassard, G.: The quantum challenge to complexity theory. In: Proceedings of the 7th IEEE Conference on Structure in Complexity Theory, pp. 132–137 (1992)
14.
Beth, T., Roetteler, M.: Quantum algorithms: applicable algebra and quantum physics. In: Quantum Information, pp. 96–150. Springer (2001)
15.
16.
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35(8), 677–691 (1986)
17.
18.
Cirac, J., Zoller, P.: Quantum computations with cold trapped ions. Phys. Rev. Lett. 74, 4091–4094 (1995)
19.
Cleve, R., Watrous, J.: Fast parallel circuit for the quantum Fourier transform. In: Proceedings of the 41th Annual Symposium on Foundations of Computer Science, p. 526 (2000)
20.
Cory, D., Fahmy, A., Havel, T.: Nuclear magnetic resonance spectroscopy: an experimentally accessible paradigm for quantum computing. In: Proceedings of the 4th Workshop on Physics and Computation, pp. 87–91 (1996)
21.
De Vos, A., Desoete, B., Janiak, F., Nogawski, A.: Control gates as building blocks for reversible computers. In: Proceedings of the 11th International Workshop on Power and Timing Modeling, Optimization and Simulation, pp. 9201–9210 (2001)
22.
23.
Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97–117 (1985)CrossRefMATHMathSciNet
24.
25.
26.
Devadas, S., Ghosh, A., Keutzer, K.: Logic Synthesis. McGraw-Hill, New York (1994)
27.
Diao, Z., Zubairy, M.S., Chen, G.: Quantum circuit design for Grover’s algorithm. Z. Naturforschung, vol. 57a, pp. 701–708 (2002)
28.
Dirac, P.: The Principles of Quantum Mechanics. Clarendon Press, Oxford (1947)MATH
29.
Divincenzo, D.: Two-bit gates are universal for quantum computation. Phys. Rev. A 51(2), 1015–1022 (1995)CrossRef
30.
Dueck, G.W., Maslov, D.: Reversible function synthesis with minimum garbage outputs. In: Proceedings of the 6th International Symposium on Representations and Methodology of Future Computing Technologies, pp. 154–161 (2003)
31.
32.
Feynman, R.: Quantum mechanical computers. Opt. News 11(2), 11–20 (1985)CrossRef
33.
Feynman, R.: Feynman Lectures on Computation. Addison-Wesley, Reading (1996)
34.
35.
36.
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp. 212–219 (1996)
37.
Gruska, J.: Quantum Computing. McGraw-Hill, London (1999)MATH
38.
Iwama, K., Kambayashi, Y., Yamashita, S.: Transformation rules for designing CNOT–based quantum circuits. In: Proceedings of the 39th Conference on Design Automation, pp. 419–424. ACM Press (2002)
39.
Keyes, R., Landauer, R.: Minimal energy dissipation in logic. IBM J. Res. Dev. 14, 152–157 (1970)CrossRef
40.
Lee, J., Kim, J., Cheong, Y., Lee, S.: A Practical Method for Constructing Quantum Combinational Logic Circuits (1999). arXiv:​9911053
41.
Lloyd, S.: A potentially realizable quantum computer. Science 261, 1569–1571 (1993)CrossRef
42.
Lloyd, S.: Almost any quantum logic gate is universal. Phys. Rev. Lett. 75(2), 346–349 (1995)CrossRef
43.
Maslov, D., Dueck, G.W.: Complexity of reversible Toffoli cascades and EXOR PLAs. In: Proceedings of the 12th International Workshop on Post-Binary ULSI Systems, pp. 17–20 (2003)
44.
Maslov, D., Dueck, G.W., Miller, D.M.: Fredkin/Toffoli templates for reversible logic synthesis. In: Proceedings of the ACM/IEEE International Conference on Computer-Aided Design, p. 256 (2003)
45.
Maslov, D., Dueck, G.W., Miller, D.M.: Simplification of Toffoli networks via templates. In: Proceedings of the 16th Symposium on Integrated Circuits and Systems Design, p. 53 (2003)
46.
Miller, D.M., Dueck, G.W.: Spectral techniques for reversible logic synthesis. In: Proceedings of the 6th International Symposium on Representations and Methodology of Future Computing Technologies, pp. 56–62 (2003)
47.
Miller, D.M., Maslov, D., Dueck, G.W.: A transformation based algorithm for reversible logic synthesis. In: Proceedings of the 40th Conference on Design Automation, pp. 318–323 (2003)
48.
Miller, J., Thomson, P.: Highly efficient exhaustive search algorithm for optimising canonical Reed-Muller expansions of Boolean functions. Int. J. Electron. 76, 37–56 (1994)CrossRef
49.
Mishchenko, A., Perkowski, M.: Logic synthesis of reversible wave cascades. In: Proceedings of International Workshop on Logic and Synthesis (2002)
50.
Moore, G.: Cramming more components onto integrated circuits. Electronics 38(8), 114–117 (1965)
51.
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK (2000)MATH
52.
Ogawa, T., Nagaoka, H.: Strong converse to the quantum channel coding theorem. IEEE Trans. Inf. Theory 45(7), 2486–2489 (1999)CrossRefMATHMathSciNet
53.
Patel, K.N., Markov, I.L., Hayes, J.P.: Efficient Synthesis of Linear Reversible Circuits (2003). arXiv:​0302002
54.
55.
Robertson, G., Miller, J., Thomson, P.: Non-exhaustive search methods and their use in the minimisation of Reed-Muller canonical expansions. Int. J. Electron. 80(1), 1–12 (1996)CrossRef
56.
Rylander, B., Soule, T., Foster, J., Alves-foss, J.: Quantum evolutionary programming. In: Proceedings of the Genetic and Evolutionary, Computation Conference, pp. 1005–1011 (2001)
57.
58.
Shende, V., Prasad, A., Markov, I., Hayes, J.: Reversible logic circuit synthesis. In: Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pp. 353–360 (2002)
59.
Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedingsof the 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE Computer Society Press (1994)
60.
Simon, D.: On the power of quantum computation. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 116–123 (1994)
61.
Spector, L., Barnum, H., Bernstein, H., Swami, N.: Finding better-than-classical quantum AND/OR algorithm using genetic programming. In: Proceedings of the Congress on Evolutionary Computation, vol. 3, pp. 2239–2246. IEEE Press (1999)
62.
Surkan, A., Khuskivadze, A.: Evolution of quantum algorithms for computer of reversible operators. In: The 2002 (NASA/DOD) Conference on Evolvable Hardware, IEEE Computer Society, pp. 186–187 (2001)
63.
Toffoli, T.: Reversible computing. In: de Bakker, W., van Leeuwen, J. (eds.), Automata, Languages and Programming, p. 632. Springer, New York (1980). Technical Memo MIT/LCS/TM-151, MIT Lab for Computer Science (unpublished)
64.
Travaglione, B.C., Nielsen, M.A., Wiseman, H.M., Ambainis, A.: ROM-based Computation: Quantum Versus Classical (2001). arXiv:​0109016
65.
Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. In: Proceedings of the London Mathematical Society, Series 2, vol. 42, pp. 230–265 (1936)
66.
Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54(1), 147–153 (1996)CrossRefMathSciNet
67.
De Vos, A., Desoete, B., Adamski, A., Pietrzak, P., Sibinski, M., Widerski, T.: Design of reversible logic circuits by means of control gates. In: Proceedings of the 10th International Workshop on Integrated Circuit Design, Power and Timing Modeling, Optimization and Simulation, pp. 255–264 (2000)
68.
Wiedemann, D.: Quantum cryptography. SIGACT News 18(2), 48–51 (1987)CrossRef
69.
Wootters, W.K., Zurek, W.H.: A single quantum cannot be cloned. Nature 299, 802 (1982)CrossRefMATH
70.
Younes, A., Miller, J.: Automated method for building CNOT based quantum circuits for Boolean functions. In: Proceedings of the 1st International Computer Engineering Conference New Technologies for the Information Society, pp. 562–565, (2004)
71.
Younes, A., Miller, J.: Representation of Boolean quantum circuits as Reed-Muller expansions. Int. J. Electron. 91(7), 431–444 (2004)CrossRef
Metadaten
Titel
Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits
verfasst von
Ahmed Younes
Copyright-Jahr
2018
Buch
Inspired by Nature

Print ISBN: 978-3-319-67996-9

Electronic ISBN: 978-3-319-67997-6

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-67997-6_5