Cole Comfort

Date: November 17, 2017

Time: 11:15

Location: ICT 616


Title: A Complete Classification of the Toffoli Gate with Ancillary bits
The Toffoli gate is a universal gate for classical reversible computation.  This means that if we are allowed to fix the values of certain inputs and outputs (called ancillary bits), we can simulate any Boolean function from \mathbb{Z}_2^n \to \mathbb{Z}_2^m with a circuit from n\to m+k wires consisting only of Toffoli gates (with k extra ignored outputs).

Iwama found a complete set of identities for circuits solely consisting of Toffoli gates.  I present a complete set of identities for the symmetric monoidal category generated by the Toffoli gate and ancillary bits.  I also provide a normal form for these circuits and prove an equivalence of categories into a subcategory of \mathsf{PInj}