Primitive gates and relations for classical and quantum boolean circuits

by Yves Lafont

Monoidal categories are algebraic models of computation with two compositions: a sequential one and a parallel one. There are four main examples:

  1. sets with disjoint union (the basic case);
  2. vector spaces with direct sum (the linear case);
  3. sets with cartesian product (the classical case);
  4. vector spaces with tensor product (the quantum case).
My aim is to find presentations by generators and relations for the reversible classical case (corresponding to reversible boolean circuits) and for the unitary quantum case (corresponding to quantum boolean circuits). In both cases, we only know about generators (corresponding to primitive gates), but I will give examples of presentation by generators and relations for simpler cases : the reversible linear case and the orthogonal linear case. The material for this talk comes mainly from my paper Towards an Algebraic Theory of Boolean Circuits, to appear in Journal of Pure and Applied Algebra.