COPLAS talk: The Category CNOT

On 22 February 2018, professor Robin Cockett, Department of Computer Science and Institute for Quantum Science and Technology, University of Calgary, Alberta, Canada will give a talk at DIKU. All are welcome. No registration required.


The Category CNOT


This talk concerns the process of finding a complete set of identities for the symmetric monoidal category, CNOT, generated by the controlled-not gate and the computational ancillae (state preparation and measurement). Surprisingly, although the controlled-not gate is a staple of reversible computation, proving that one has a complete set of identities was still an open problem.

Very central to the proof was establishing that CNOT was a discrete inverse category, a notion introduced in Brett Giles's PhD. thesis to describe reversible computing. The next step involved showing that CNOT was equivalent to the category ParIso(Tor_2) of partial isomorphisms of finitely-generated commutative non-empty torsors of characteristic 2, or equivalently the category of affine partial isomorphisms between finite-dimensional Z_2 vector spaces.

The talk will explore the development of the proof that CNOT is equivalent to ParIso(Tor_2) with an eye for the human story and minor dramas on the way.


Robin Cockett is a Professor of Computer Science at the University of Calgary in Alberta, Canada. He is particularly interested in applications of category theory to Computer Science, and in (formal) programming languages. Notably, he developed the programming language Charity (a computational realization of Cartesian categories) and co-developed the quantum programming language LPQL and the concurrent programming language MPL. Aside from his work on programming languages, he is known for his contributions to category theory, in particular with his work on linearly distributive categories, restriction categories, range categories, differential categories, and tangent categories. His most current interest is in (the foundations of) mathematical physics.