Classifying reversible logic gates with ancillary bits
Advisor
Cockett, J. Robin B.Author
Comfort, Cole RobertCommittee Member
Coecke, BobGour, Gilad
Scheidler, Renate
Accessioned
2019-07-25T14:46:25ZAvailable
2019-07-25T14:46:25ZIssued
2019-07-23Date
2019-11Classification
Education--MathematicsPhysics
Computer Science
Subject
Reversiblereversible computing
quantum
quantum computing
quantum information
category theory
monoidal categories
restriction categories
categorical quantum mechanics
theoretical computer science
Metadata
Show full item record
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.Citation
Comfort, C. R. (2019). Classifying reversible logic gates with ancillary bits (Unpublished master's thesis). University of Calgary, Calgary, AB.Collections
University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.