Classifying reversible logic gates with ancillary bits
Date
2019-07-23
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this thesis, two models of reversible computing are classified, and the relation of reversible computing to quantum computing is explored. First, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the controlled-not gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between non-empty finitely-generated commutative torsors of characteristic 2. Next, a finite, complete set of identities is given for the symmetric monoidal category generated by the computational ancillary bits along with the Toffoli gate. In doing so, it is proven that this category is equivalent to the category of partial isomorphisms between finite powers of the two element set. The relation between reversible and quantum computing is also explored. In particular, the category with the controlled-not gate as a generator is extended to be complete for the real stabilizer fragment of quantum mechanics. This is performed by translating the identities to and from the angle-free fragment of the ZX-calculus, and showing that these translations are inverse to each other.
Description
Keywords
Reversible, reversible computing, quantum, quantum computing, quantum information, category theory, monoidal categories, restriction categories, categorical quantum mechanics, theoretical computer science
Citation
Comfort, C. R. (2019). Classifying reversible logic gates with ancillary bits (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.