Abstract
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversiblecomputing analogue of Post's lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits.
Our theorem implies a lineartime algorithm (which we have implemented), that takes as input the truth tables of reversible gates G and H, and that decides whether G generates H. Previously, this problem was not even known to be decidable (though with effort, one can derive from abstract considerations an algorithm that takes triplyexponential time). The theorem also implies that any nbit reversible circuit can be "compressed" to an equivalent circuit, over the same gates, that uses at most 2^{n}poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every nondegenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an "encoded subspace."
Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on nbit strings (as the Toffoli gate does); no transformations; all transformations that preserve Hamming weight (as the Fredkin gate does); all transformations that preserve Hamming weight mod k for some k; all affine transformations (as the ControlledNOT gate does); all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Prior to this work, it was not even known that every class was finitely generated. Ruling out the possibility of additional classes, not in the list, requires involved arguments about polynomials, lattices, and Diophantine equations.
BibTeX  Entry
@InProceedings{aaronson_et_al:LIPIcs:2017:8173,
author = {Scott Aaronson and Daniel Grier and Luke Schaeffer},
title = {{The Classification of Reversible Bit Operations}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {23:123:34},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8173},
URN = {urn:nbn:de:0030drops81737},
doi = {10.4230/LIPIcs.ITCS.2017.23},
annote = {Keywords: Reversible computation, Reversible gates, Circuit synthesis, Gate classification, Boolean logic, Post’s lattice}
}
Keywords: 

Reversible computation, Reversible gates, Circuit synthesis, Gate classification, Boolean logic, Post’s lattice 
Collection: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

28.11.2017 