A classification of reversible bit and stabilizer operations

This thesis is an exposition of a classification of classical reversible gates acting on bits in terms of the reversible transformations they generate, which was recently completed by the author, Scott Aaronson, and Luke Schaeffer. In particular, we present those portions of the classification which were the main contributions of the author. Most importantly, this thesis contains the proof that every non-affine gate generates a Fredkin gate, which was one of the main technical hurdles in completing the classification. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical logic from the 1940s, where we allow arbitrary ancilla bits to be used in the computation provided they return to their initial configuration at the end of the computation. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. This thesis also gives preliminary results for the classification of stabilizer gates, which have garnered much attention due to their role in unifying many of the known quantum error-correcting codes. In the stabilizer setting, we generalize the classical model to allow the use of arbitrary stabilizer ancillas and show that this leads to several nonintuitive results. In particular, we show that the CNOT and Hadamard gates suffice to generate all stabilizer operations (whereas the phase gate is required in a more group theoretic setting); present a complete classification of the "classical" stabilizer operations; and give exact generating sets for the one-qubit stabilizer operations.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Grier, Daniel

Advisor dc:contributor.advisor

• Scott Aaronson.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/99863

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99863