Reversible monadic computing
arXiv:1505.04330 · doi:10.1016/j.entcs.2015.12.014
Abstract
We extend categorical semantics of monadic programming to reversible computing, by considering monoidal closed dagger categories: the dagger gives reversibility, whereas closure gives higher-order expressivity. We demonstrate that Frobenius monads model the appropriate notion of coherence between the dagger and closure by reinforcing Cayley's theorem; by proving that effectful computations (Kleisli morphisms) are reversible precisely when the monad is Frobenius; by characterizing the largest reversible subcategory of Eilenberg-Moore algebras; and by identifying the latter algebras as measurements in our leading example of quantum computing. Strong Frobenius monads are characterized internally by Frobenius monoids.
arXiv comment19 pages
References in corpus (13)
- A survey of graphical languages for monoidal categories
- Fundamentals of Quantum Information Theory
- Handling Algebraic Effects
- Quipper: A Scalable Quantum Programming Language
- Categorical formulation of quantum algebras
- A new description of orthogonal bases
- Geometry of abstraction in quantum computation
- Relative Frobenius algebras are groupoids
- Involutive Categories and Monoids, with a GNS-correspondence
- Frobenius algebras and ambidextrous adjunctions
- Category Theory Using String Diagrams
- Abstract Scalars, Loops, and Free Traced and Strongly Compact Closed Categories
- Relating toy models of quantum computation: comprehension, complementarity and dagger mix autonomous categories