SpringerLink
Log in

Enumeration of Reversible Functions and Its Application to Circuit Complexity

  • Conference paper
  • First Online:
Reversible Computation (RC 2016)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 9720))

Included in the following conference series:

  • 706 Accesses

Abstract

We review combinational results to enumerate and classify reversible functions and investigate the application to circuit complexity. In particularly, we consider the effect of negating and permuting input and output variables and the effect of applying linear and affine transformations to inputs and outputs. We apply the results to reversible circuits and prove that minimum circuit realizations of functions in the same equivalence class differ at most in a linear number of gates in presence of negation and permutation and at most in a quadratic number of gates in presence of linear and affine transformations.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Thailand)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Thailand)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 49.99
Price excludes VAT (Thailand)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Andrews, G.E.: The Theory of Partitions. Cambridge University Press, Cambridge (1984)

    Book  MATH  Google Scholar 

  2. Ashenhurst, R.L.: The application of counting techniques. In: Proceedings of the ACM National Meeting, pp. 293–305 (1952)

    Google Scholar 

  3. Beth, T., Rötteler, M.: Quantum algorithms: applicable algebra and quantum physics. In: Springer Tracts in Modern Physics, vol. 173, pp. 96–150 (2001)

    Google Scholar 

  4. De Bruijn, N.G.: Generalization of Pólya’s fundamental theorem in enumerative combinational analysis. Konikl. Nederl. Akademie Van Wetenschappen A 52(2), 59–69 (1959)

    MATH  Google Scholar 

  5. Draper, T.G.: Nonlinear complexity of Boolean permutations. Ph.D. thesis, University of Maryland (2009)

    Google Scholar 

  6. 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 

  7. Harrison, M.A.: Combinational problems in Boolean algebras and applications to the theory of switching. Ph.D. thesis, University of Michigan (1963)

    Google Scholar 

  8. Harrison, M.A.: The number of classes of invertible Boolean functions. J. ACM 10(1), 25–28 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  9. Harrison, M.A.: The number of equivalence classes of Boolean functions under groups containing negation. IEEE Trans. Electron. Comput. 12, 559–561 (1963)

    Article  MATH  Google Scholar 

  10. Harrison, M.A.: The number of transitivity sets of Boolean functions. J. Soc. Appl. Ind. Math. 11, 806–828 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  11. Harrison, M.A.: On the classification of Boolean functions by the general linear and affine groups. J. Soc. Appl. Ind. Math. 12, 285–299 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  12. Lorens, C.S.: Invertible Boolean functions. Technical report 21, Space-General Corporation, El Monte, California, Research Memorandum (1962)

    Google Scholar 

  13. Lorens, C.S.: Invertible Boolean functions. IEEE Trans. Electron. Comput. 13, 529–541 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  14. Pólya, G.: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und Chemische Verbindungen. Acta Math. 68, 145–253 (1937)

    Article  MathSciNet  MATH  Google Scholar 

  15. Primenko, É.A.: Equivalence classes of invertible Boolean functions. Cybernetics 20(6), 771–776 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  16. Slepian, D.: On the number of symmetry types of Boolean functions of \(n\) variables. Can. J. Math. 5, 185–193 (1953)

    Article  MathSciNet  MATH  Google Scholar 

  17. Soeken, M., Thomsen, M.K.: White dots do matter: rewriting reversible logic circuits. In: International Conference on Reversible Computation, pp. 196–208 (2013)

    Google Scholar 

  18. Toffoli, T.: Reversible computing. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 632–644. Springer, Heidelberg (1980)

    Chapter  Google Scholar 

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

    Article  Google Scholar 

Download references

Acknowledgments

This research was supported by H2020-ERC-2014-ADG 669354 CyberCare and by the European COST Action IC 1405 ‘Reversible Computation’.

Author information

Authors and Affiliations

  1. Integrated Systems Laboratory, EPFL, Lausanne, Switzerland

    Mathias Soeken & Giovanni De Micheli

  2. Cyber-Physical Systems, DFKI GmbH, Bremen, Germany

    Nabila Abdessaied

Authors
  1. Mathias Soeken
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nabila Abdessaied
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giovanni De Micheli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mathias Soeken .

Editor information

Editors and Affiliations

  1. National Institute of Informatics, Tokyo, Japan

    Simon Devitt

  2. University of Bologna/Inria, Bologna, Italy

    Ivan Lanese

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this paper

Cite this paper

Soeken, M., Abdessaied, N., De Micheli, G. (2016). Enumeration of Reversible Functions and Its Application to Circuit Complexity. In: Devitt, S., Lanese, I. (eds) Reversible Computation. RC 2016. Lecture Notes in Computer Science(), vol 9720. Springer, Cham. https://doi.org/10.1007/978-3-319-40578-0_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-40578-0_19

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-40577-3

  • Online ISBN: 978-3-319-40578-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation