[Alta-Logic] Peripatetic Seminar Friday 11:00 in ICT 616

[Matthew Burke]

Please note the changes in time, day and location for the next
peripatetic seminar.

Speaker: Cole Comfort

Time and Location: 11:00 Friday Apr 20 in ICT 616

Title: A Complete Classification of the Toffoli Gate with Ancillary bits
(second attempt)

Abstract: We provide a complete set of identities for the symmetric
monoidal category, TOF, generated by the Toffoli gate and computational
ancillary bits. We do so by demonstrating that the functor which
evaluates circuits on total points is an equivalence into the full
subcategory of sets and partial isomorphisms with objects finite powers
of the two element set. The structure of the proof builds on and follows
the proof of Cockett et al. which provided a full set of identities for
the cnot gate with computational ancillary bits. Thus, first it is shown
that TOF is a discrete inverse category in which all of the identities
for the cnot gate hold; and then a normal form for the restriction
idempotents is constructed which corresponds precisely to subobjects of
the total points of TOF. This is then used to show that TOF is
equivalent to the full subcategory of sets and partial isomorphisms in
which objects have cardinality 2^n for some n in N.

http://peripatetic-seminar.cpsc.ucalgary.ca/wp/