[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Compositional Reversible Computation

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

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14680))

Included in the following conference series:

  • 214 Accesses

Abstract

Reversible computing is motivated by both pragmatic and foundational considerations arising from a variety of disciplines. We take a particular path through the development of reversible computation, emphasizing compositional reversible computation. We start from a historical perspective, by reviewing those approaches that developed reversible extensions of \(\lambda \)-calculi, Turing machines, and communicating process calculi. These approaches share a common challenge: computations made reversible in this way do not naturally compose locally.

We then turn our attention to computational models that eschew the detour via existing irreversible models. Building on an original analysis by Landauer, the insights of Bennett, Fredkin, and Toffoli introduced a fresh approach to reversible computing in which reversibility is elevated to the status of the main design principle. These initial models are expressed using low-level bit manipulations, however.

Abstracting from the low-level of the Bennett-Fredkin-Toffoli models and pursuing more intrinsic, typed, and algebraic models, naturally leads to rig categories as the canonical model for compositional reversible programming. The categorical model reveals connections to type isomorphisms, symmetries, permutations, groups, and univalent universes. This, in turn, paves the way for extensions to reversible programming based on monads and arrows. These extensions are shown to recover conventional irreversible programming, a variety of reversible computational effects, and more interestingly both pure (measurement-free) and measurement-based quantum programming.

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
$34.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
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    As noted earlier, Toffoli only proved this for finite sets. We thank Tom Leinster for the following neat proof for infinite sets. In a category with products, every morphism \(f :A \rightarrow B\) factors as a split monic \((1,f) :A \rightarrow A \times B\) followed by a product projection \(A \times B \rightarrow B\). But in \(\textbf{Set}\), split monics are exactly the same as injections, which are coproduct injections up to an isomorphism.

References

  1. Aharonov, D.: A simple proof that Toffoli and Hadamard are quantum universal (2003). arXiv:quant-ph/0301040

  2. Andrés-Martínez, P., Heunen, C., Kaarsgaard, R.: Universal properties of partial quantum maps (2022). arXiv:2206.04814

  3. Aubert, C.: The correctness of concurrencies in (reversible) concurrent calculi. J. Log. Algebraic Methods Program. 100924 (2023). https://doi.org/10.1016/j.jlamp.2023.100924

  4. Axelsen, H.B.: Clean translation of an imperative reversible programming language. In: Knoop, J. (ed.) CC 2011. LNCS, vol. 6601, pp. 144–163. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19861-8_9

    Chapter  Google Scholar 

  5. Axelsen, H.B.: Private communication (2015)

    Google Scholar 

  6. Baez, J.C., Dolan, J.: From finite sets to Feynman diagrams (2000). arXiv:000413

  7. Baker, H.G.: NREVERSAL of fortune—the thermodynamics of garbage collection. In: Bekkers, Y., Cohen, J. (eds.) IWMM 1992. LNCS, vol. 637, pp. 507–524. Springer, Heidelberg (1992). https://doi.org/10.1007/BFb0017210

    Chapter  Google Scholar 

  8. Bennett, C.H.: Logical reversibility of computation. IBM J. Res. Dev. 17(6), 525–532 (1973). https://doi.org/10.1147/rd.176.0525

    Article  MathSciNet  Google Scholar 

  9. Bérut, A., Arakelyan, A., Petrosyan, A., Ciliberto, S., Dillenschneider, R., Lutz, E.: Experimental verification of Landauer’s principle linking information and thermodynamics. Nature 483(7388), 187–189 (2012). https://doi.org/10.1038/nature10872

    Article  Google Scholar 

  10. Cardelli, L., Zavattaro, G.: On the computational power of biochemistry. In: Horimoto, K., Regensburger, G., Rosenkranz, M., Yoshida, H. (eds.) AB 2008. LNCS, vol. 5147, pp. 65–80. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85101-1_6

    Chapter  Google Scholar 

  11. Carette, J., Heunen, C., Kaarsgaard, R., Sabry, A.: With a few square roots, quantum computing is as easy as \(\Pi \). Proc. ACM Program. Lang. 8(POPL), 546–574 (2024)

    Google Scholar 

  12. Carette, J., James, R.P., Sabry, A.: Embracing the laws of physics: three reversible models of computation. Adv. Comput. 126, 15–63 (2022). https://doi.org/10.1016/bs.adcom.2021.11.009, https://www.sciencedirect.com/science/article/pii/S0065245821000838

  13. Carette, J., Sabry, A.: Computing with semirings and weak rig groupoids. In: Thiemann, P. (ed.) ESOP 2016. LNCS, vol. 9632, pp. 123–148. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49498-1_6

    Chapter  Google Scholar 

  14. Carette, J., Heunen, C., Kaarsgaard, R., Sabry, A.: The quantum effect: a recipe for QuantumPi (2023). arXiv:2302.01885

  15. Choudhury, V., Karwowski, J., Sabry, A.: Symmetries in reversible programming: from symmetric rig groupoids to reversible programming languages. Proc. ACM Program. Lang. 6(POPL) (2022). https://doi.org/10.1145/3498667

  16. Church, A.: A set of postulates for the foundation of logic. Ann. Math. 33(2), 346–366 (1932). http://www.jstor.org/stable/1968337

  17. Danos, V., Krivine, J.: Reversible communicating systems. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 292–307. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28644-8_19

    Chapter  Google Scholar 

  18. Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 1–12. Springer, Heidelberg (2006). https://doi.org/10.1007/11787006_1

    Chapter  Google Scholar 

  19. Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21(3), 219–253 (1982). https://doi.org/10.1007/BF01857727

    Article  MathSciNet  Google Scholar 

  20. Glück, R., Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing. In: Kameyama, Y., Stuckey, P.J. (eds.) FLOPS 2004. LNCS, vol. 2998, pp. 291–306. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24754-8_21

    Chapter  Google Scholar 

  21. Glück, R., Yokoyama, T.: Reversible computing from a programming language perspective. Theoret. Comput. Sci. 953, 113429 (2023). https://doi.org/10.1016/j.tcs.2022.06.010, https://www.sciencedirect.com/science/article/pii/S0304397522003619

  22. Heunen, C.: On the functor \(\ell ^{2}\). In: Coecke, B., Ong, L., Panangaden, P. (eds.) Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky. LNCS, vol. 7860, pp. 107–121. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38164-5_8

    Chapter  Google Scholar 

  23. Heunen, C., Kaarsgaard, R.: Bennett and Stinespring, together at last. In: Proceedings 18th International Conference on Quantum Physics and Logic (QPL 2021). Electronic Proceedings in Theoretical Computer Science, vol. 343, pp. 102–118. OPA (2021). https://doi.org/10.4204/EPTCS.343.5

  24. Heunen, C., Kaarsgaard, R.: Quantum information effects. Proc. ACM Program. Lang. 6(POPL), 1–27 (2022)

    Google Scholar 

  25. Heunen, C., Kaarsgaard, R., Karvonen, M.: Reversible effects as inverse arrows. In: Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV). Electronic Notes in Theoretical Computer Science, vol. 341, pp. 179–199. Elsevier (2018)

    Google Scholar 

  26. Heunen, C., Karvonen, M.: Monads on dagger categories. Theory Appl. Categories 31, 1016–1043 (2016)

    MathSciNet  Google Scholar 

  27. Heunen, C., Vicary, J.: Categories for Quantum Theory. Oxford University Press, Oxford (2019)

    Book  Google Scholar 

  28. Hoare, C.A.R.: Communicating sequential processes. Commun. ACM 21(8), 666–677 (1978). https://doi.org/10.1145/359576.359585

    Article  Google Scholar 

  29. Hughes, J.: Programming with arrows. In: Vene, V., Uustalu, T. (eds.) AFP 2004. LNCS, vol. 3622, pp. 73–129. Springer, Heidelberg (2005). https://doi.org/10.1007/11546382_2

    Chapter  Google Scholar 

  30. Huot, M., Staton, S.: Quantum channels as a categorical completion. In: Proceedings of the ACM/IEEE Symposium on Logic in Computer Science, vol. 35, pp. 1–13 (2019)

    Google Scholar 

  31. Huot, M., Staton, S.: Universal properties in quantum theory. In: Selinger, P., Chiribella, G. (eds.) Proceedings of the 15th International Conference on Quantum Physics and Logic (QPL 2018). Electronic Proceedings in Theoretical Computer Science, vol. 287, pp. 213–224. Open Publishing Association (2018).https://doi.org/10.4204/EPTCS.287.12

  32. Jacobs, B., Heunen, C., Hasuo, I.: Categorical semantics for Arrows. J. Funct. Program. 19(3–4), 403–438 (2009). https://doi.org/10.1017/S0956796809007308

    Article  MathSciNet  Google Scholar 

  33. James, R.P., Sabry, A.: Information effects. In: POPL 2012: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of programming languages, pp. 73–84. ACM (2012). https://doi.org/10.1145/2103656.2103667

  34. Kaarsgaard, R., Glück, R.: A categorical foundation for structured reversible flowchart languages: soundness and adequacy. Log. Methods Comput. Sci. 14(3) (2018)

    Google Scholar 

  35. Kaarsgaard, R.: The logic of reversible computing: theory and practice. Ph.D. thesis, Department of Computer Science, University of Copenhagen (2018)

    Google Scholar 

  36. Kastl, J.: Algebraische Modelle, Kategorien und Gruppoide, Studien zur Algebra und ihre Anwendungen, vol. 7, chap. Inverse categories, pp. 51–60. Akademie-Verlag, Berlin (1979)

    Google Scholar 

  37. Kelly, G.M.: Coherence theorems for lax algebras and for distributive laws. In: Kelly, G.M. (ed.) Category Seminar. LNM, vol. 420, pp. 281–375. Springer, Heidelberg (1974). https://doi.org/10.1007/BFb0063106

    Chapter  Google Scholar 

  38. Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5(3), 183–191 (1961). https://doi.org/10.1147/rd.53.0183

    Article  MathSciNet  Google Scholar 

  39. Laplaza, M.L.: Coherence for distributivity. In: Kelly, G.M., Laplaza, M., Lewis, G., Mac Lane, S. (eds.) Coherence in Categories. LNM, vol. 281, pp. 29–65. Springer, Heidelberg (1972). https://doi.org/10.1007/BFb0059555

    Chapter  Google Scholar 

  40. Lecerf, Y.: Machines de Turing reversibles. Compt. Rendus hebdomadaires seances l’acad. sci. 257, 2597–2600 (1963)

    Google Scholar 

  41. Leinster, T.: Basic Category Theory. Cambridge University Press, Cambridge (2014)

    Book  Google Scholar 

  42. Ma, X., Huang, J., Lombardi, F.: A model for computing and energy dissipation of molecular QCA devices and circuits. J. Emerg. Technol. Comput. Syst. 3(4) (2008). https://doi.org/10.1145/1324177.1324180

  43. Mac Lane, S.: Natural associativity and commutativity. Rice Univ. Stud. 49(4) (1963)

    Google Scholar 

  44. Macii, E., Poncino, M.: Exact computation of the entropy of a logic circuit. In: Proceedings of the Sixth Great Lakes Symposium on VLSI, pp. 162–167 (1996). https://doi.org/10.1109/GLSV.1996.497613

  45. McCarthy, J.: The inversion of functions defined by Turing machines. In: C.E. Shannon, J.M. (ed.) Automata Studies, Annals of Mathematical Studies, pp. 177–181. No. 34. Princeton University Press (1956)

    Google Scholar 

  46. Milner, R.: A Calculus of Communicating Systems. Lecture Notes in Computer Science, vol. 92. Springer, Heidelberg (1980). https://doi.org/10.1007/3-540-10235-3

  47. Milner, R.: Functions as processes. Math. Struct. Comput. Sci. 2(2), 119–141 (1992). https://doi.org/10.1017/S0960129500001407

    Article  MathSciNet  Google Scholar 

  48. Moggi, E.: Notions of computations and monads. Inf. Comput. 93, 55–92 (1991)

    Article  MathSciNet  Google Scholar 

  49. Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2002)

    Google Scholar 

  50. Phillips, I., Ulidowski, I.: Reversing algebraic process calculi. In: Aceto, L., Ingólfsdóttir, A. (eds.) FoSSaCS 2006. LNCS, vol. 3921, pp. 246–260. Springer, Heidelberg (2006). https://doi.org/10.1007/11690634_17

    Chapter  Google Scholar 

  51. Sabelfeld, A., Myers, A.: Language-based information-flow security. IEEE J. Sel. Areas Commun. 21(1), 5–19 (2003). https://doi.org/10.1109/JSAC.2002.806121

    Article  Google Scholar 

  52. Shi, Y.: Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Info. Comput. 3(1), 84–92 (2003)

    MathSciNet  Google Scholar 

  53. Stinespring, W.F.: Positive functions on C*-algebras. Proc. Am. Math. Soc. 6(2), 211–216 (1955). https://doi.org/10.2307/2032342

    Article  MathSciNet  Google Scholar 

  54. Thomsen, M.K., Kaarsgaard, R., Soeken, M.: Ricercar: a language for describing and rewriting reversible circuits with Ancillae and its permutation semantics. In: Krivine, J., Stefani, J.-B. (eds.) RC 2015. LNCS, vol. 9138, pp. 200–215. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20860-2_13

    Chapter  Google Scholar 

  55. Toffoli, T.: Reversible computing. In: de Bakker, J., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 632–644. Springer, Heidelberg (1980). https://doi.org/10.1007/3-540-10003-2_104

    Chapter  Google Scholar 

  56. van Tonder, A.: A lambda calculus for quantum computation. SIAM J. Comput. 33(5), 1109–1135 (2004). https://doi.org/10.1137/S0097539703432165

    Article  MathSciNet  Google Scholar 

  57. Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. s2-42(1), 230–265 (1937). https://doi.org/10.1112/plms/s2-42.1.230, https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230

  58. Yanofsky, N., Mannucci, M.A.: Quantum Computing for Computer Scientists. Cambridge University Press, Cambridge (2008)

    Book  Google Scholar 

  59. Zelkowitz, M.V.: Reversible execution. Commun. ACM 16(9), 566 (1973). https://doi.org/10.1145/362342.362360

    Article  Google Scholar 

  60. Zeng, H., Ellis, C.S., Lebeck, A.R., Vahdat, A.: Ecosystem: managing energy as a first class operating system resource. In: Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS X, pp. 123–132. Association for Computing Machinery, New York (2002). https://doi.org/10.1145/605397.605411

Download references

Acknowledgments

This material is based upon work supported by the National. Science Foundation under Grant No. 1936353.

Author information

Authors and Affiliations

  1. McMaster University, Hamilton, ON, Canada

    Jacques Carette

  2. University of Edinburgh, Edinburgh, UK

    Chris Heunen

  3. University of Southern Denmark, Odense, Denmark

    Robin Kaarsgaard

  4. Indiana University, Bloomington, IN, USA

    Amr Sabry

Authors
  1. Jacques Carette
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chris Heunen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robin Kaarsgaard
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Amr Sabry
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amr Sabry .

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Copenhagen, Copenhagen Ø, Denmark

    Torben Ægidius Mogensen

  2. Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland

    Łukasz Mikulski

Ethics declarations

Disclosure of Interests

The authors have no competing interests to declare that are relevant to the content of this article.

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Carette, J., Heunen, C., Kaarsgaard, R., Sabry, A. (2024). Compositional Reversible Computation. In: Mogensen, T.Æ., Mikulski, Ł. (eds) Reversible Computation. RC 2024. Lecture Notes in Computer Science, vol 14680. Springer, Cham. https://doi.org/10.1007/978-3-031-62076-8_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-62076-8_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-62075-1

  • Online ISBN: 978-3-031-62076-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation