For the past few months I have had the pleasure of working closely with my colleague Erhard Aichinger on a project that he has been keeping in a lower drawer for some time. I am not sure if he planned it that way, but the project was right up my alley.

The core of the project was to take the ideas developed by Tom Toffoli in a very old paper (that I cannot point to online, it seems not to exist. Even the link from wikipedia is dead!) about reversible computation and see how we could formalise this algebraically. Switching theory and boolean algebra have been formalised in may ways, one of the most important being clone theory. Erhard was wondering whether we might find a way to do something similar with Toffoli’s work. This required a few strange starting points; luckily I seem to have the right combination of strangenesses in my head.

Reversible computation is something that I have been aware of for a long time, ever since Günter Pilz asked me whether changing a semigroup into a group (and thus a seminearring into a seminearfield) made any sense when modelling certain types of computation. It turns out that reversible computation is not only possible but actually useful, for instance as all quantum processes are reversible until the last point of measurement, so quantum computation requires the understanding of reversible computation.

The other area is clone theory, a special area of universal algebra, which is a special area of abstract algebra, which is a special area of algebra, which is a special area of pure mathematics. It also happens to be Erhard’s main area of work and he has published a few quite important papers over the years, often with our mutual colleague Peter Mayr. So that was great, having a clone theorist on hand and some experience with reversible computation, perhaps something could emerge. Clone Theory could be summarised as generalising Emil Post’s work from 1941 about all arbitrary arity mappings of the set {0,1} to itself.

It turns out that Toffoli’s work has been fundamental in a bunch of related areas, so much so that the “controlled-controlled-not” gate that he introduced in 1979 is now known as the Toffoli gate. There is a quantum version as well. As we dived into this project, we became aware that a group at MIT around Scott Aaronson, had been looking into the same area, but decided that generalising Post’s work was going to be too hard. So Scott, along with Daniel Grier and Luke Schaeffer, did a version of his original work and found some very interesting results on the structure of possible closed collections of reversible maps on {0,1}.

We did not try to extend this work, rather to look at the general situation in more detail. Perhaps we can find ways to avoid the huge amount of work they did (66 pages!) as we look at reversible mappings on higher order sets. Perhaps we can find a way to use Emil Jeřábek’s insights to make the analysis easier. We wanted to build a basis for a theory of reversible clones, or closed systems of mappings is we wanted to look at arbitrary mappings from A^m to A^n for A some finite set.

It turned out that looking at higher order base sets was the trick. On the arXiv the paper can be dived into, or one could wait for the proper publication. There are three interesting new results. One is that we can write the “wiring” of reversible gates as an algebra with a finite number of finitary operations. Which means that the lattice of subalgebras (i.e. closed systems of mappings by generation) is algebraic and thus well structured. Later in the paper we look at other forms of closure , for instance related to results about “ancilla” bits, and show that there are four distinct and relevant forms of closure, related to Toffolis notions of realisation(the three others correspond to temporary storage, strong temporary storage and general realisation). Because the generation closure is the most general closure, giving the smallest closed set, the lattices of closed sets of reversible mappings might also be algebraic lattices, which would be good. Aaronson’s work uses one of these (ancilla bits, or realisation with temporary storage). We were able to generalise Toffoli’s result about nongeneration from order 2 to arbitrary even ordered sets. But more importantly, we were able to show that for odd order sets, his result does not generalise. Four small Toffoli gates are enough to generate all reversible mappings. This is a pleasant surprise, as it indicates that odd order state sets might give us more power in creating reversible circuits.

So this work has found some surprising things and given us some results. But it also throws up a whole spectrum of other questions, which might be good to look at.

- What are the appropriate generalisations of relations as used in the clone theory Pol-Inv results? Will Lehtonen’s clusters be useful?
- Are the commutative monoid weight function introduced by Emil Jeřábek the best tool for the Pol-Inv description? These do not work outside the realm of reversible computation, but that might be fine. They are also very tempting from the “Physics of Computation” point of view – the sums of weights are a conserved quantity.
- What are the linear reversible clones? Can these be easily described, better than just including the permutation matrices? We know from clone theory that linearity can be described as the preservation of a 4-ary relation, is there something similar to be used here?
- Can we prove Aaronson et al’s observation that if a reversible clone closed under temporary storage is finitely generated, then it is generated by a single function?
- Under the operation of full composition, a reversible clone forms an inverse semigroup that is a semilattice (actually a chain isomorphic to the natural numbers) of groups. Can this observation be made use of?
- Are the lattices of closed reversible clones under the other closures also algebraic?
- Can we find a smaller generating set as hoped for in Yang, Song, Perkowski and Wu’s paper?

I feel quite happy about this project and its results. Erhard asked me to look properly at some things that had been tickling me for a while and gave some excellent comments as I wandered down that path. One can only hope that other people find it interesting as well.