Cockett, J. Robin B.Comfort, Cole Robert2019-07-252019-07-252019-07-23Comfort, C. R. (2019). Classifying reversible logic gates with ancillary bits (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.http://hdl.handle.net/1880/110665In 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.engUniversity 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.Reversiblereversible computingquantumquantum computingquantum informationcategory theorymonoidal categoriesrestriction categoriescategorical quantum mechanicstheoretical computer scienceEducation--MathematicsPhysicsComputer Sciencemaster thesis10.11575/PRISM/36765