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.