[Alta-Logic] peripatetic seminar tomorrow

[Jonathan Gallagher]

See http://peripatetic-seminar.cpsc.ucalgary.ca/wp/?event=cole-comfort
for details about tomorrow's talk.

The peripatetic seminar will meet:
Where: ICT 616
When: Friday, November 17, 2017 at 11:15
Why:
Cole Comfort is speaking

Title: A Complete Classification of the Toffoli Gate with Ancillary bits

Abstract:

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 \emph{and ancillary bits}.
I also provide a normal form for these circuits and prove an equivalence of
categories into a subcategory of $\mathsf{PInj}$
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.ucalgary.ca/pipermail/alta-logic-l/attachments/20171116/997650eb/attachment.html