**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:

- sets with disjoint union (the
*basic case*);
- vector spaces with direct sum (the
*linear case*);
- sets with cartesian product (the
*classical case*);
- 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.