Heunen, Chris;
Karvonen, Martti;
(2015)
Reversible Monadic Computing.
Electronic Notes in Theoretical Computer Science
, 319
pp. 217-237.
10.1016/j.entcs.2015.12.014.
Preview |
Text
Karvonen_1-s2.0-S157106611500081X-main.pdf Download (322kB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | Reversible Monadic Computing |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.entcs.2015.12.014 |
| Publisher version: | https://doi.org/10.1016/j.entcs.2015.12.014 |
| Language: | English |
| Additional information: | © 2015 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). |
| Keywords: | Frobenius monad, dagger category, reversible computing, quantum measurement |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10193415 |
Archive Staff Only
 |
View Item |
