Top

Published in:

2018 | OriginalPaper | Chapter

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

Author : Ahmed Younes

Published in: Inspired by Nature

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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.

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!

inform now

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!

inform now

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!

inform now

previous chapter Evolution in Nanomaterio: The NASCENCE Project

next chapter Some Remarks on Code Evolution with Genetic Programming

Akers, S.B.: On a theory of Boolean functions. J. SIAM 7, 487–489 (1959)

Akers, S.B.: Binary decision diagrams. IEEE Trans. Comput. C-27(6), 509–516 (1978)

Almaini, A.: Electronic Logic Systems, chapter 12: Modulo-2 Logic Circuits, p. 470, 2nd edn. Prentice-Hall, Englewood Cliffs, NJ (1989)

Barenco, A.: A universal two-bit gate for quantum computation. Proc. R. Soc. Lond. A 449, 679–683 (1995)CrossRefMATHMathSciNet

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

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

Benioff, P.: Quantum mechanical hamiltonian models of Turing machines. J. Stat. Phys. 29, 515–546 (1982)CrossRefMATHMathSciNet

Benioff, P.: Quantum mechanical hamiltonian models of Turing machines that dissipate no energy. Phys. Rev. Lett. 48, 1581–1585 (1982)CrossRefMathSciNet

Bennett, C.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973)CrossRefMATHMathSciNet

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.

Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411–1473 (1997)CrossRefMATHMathSciNet

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.

Braunstein, S., Fuchs, A.: A quantum analog of Huffman coding. IEEE Trans. Inf. Theory 46(4), 1644–1649 (2000)CrossRefMATHMathSciNet

16.

Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. C-35(8), 677–691 (1986)

17.

Church, A.: An unsolvable problem of elementary number theory. Am. J. Math. 58(2), 345–363 (1936)CrossRefMATHMathSciNet

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.

Deptartment of Computer Science, North Carolina State University. N.C.S.U. collaborative benchmarking laboratory. http://www.cbl.ncsu.edu/benchmarks/

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.

Deutsch, D., Barenco, A., Ekert, A.: Universality in quantum computation. Proc. R. Soc. Lond. A 449, 669–677 (1995)CrossRefMATHMathSciNet

25.

Deutsch, D., Josza, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439, 553–558 (1992)CrossRefMATHMathSciNet

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.

Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21, 467–488 (1982)CrossRefMathSciNet

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.

Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21, 219–253 (1982)CrossRefMATHMathSciNet

35.

Gershenfeld, N., Chuang, I.: Bulk spin-resonance quantum computation. Science 275, 350–356 (1997)CrossRefMATHMathSciNet

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.

Peres, A.: Reversible logic and quantum computers. Phys. Rev. A 32, 3266 (1985)CrossRefMathSciNet

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.

School of Computer Science, University of Victoria. Maslov reversible logic synthesis benchmarks. http://www.cs.uvic.ca/dmaslov/

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

Title: Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits
Author: Ahmed Younes
Publisher: Springer International Publishing
Book: Inspired by Nature
Print ISBN: 978-3-319-67996-9

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

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

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner