  We examine the following problem: given a collection of Clifford gates,
describe the set of unitaries generated by circuits composed of those gates.
Specifically, we allow the standard circuit operations of composition and
tensor product, as well as ancillary workspace qubits as long as they start and
end in states uncorrelated with the input, which rule out common "magic state
injection" techniques that make Clifford circuits universal. We show that there
are exactly 57 classes of Clifford unitaries and present a full classification
characterizing the gate sets which generate them. This is the first attempt at
a quantum extension of the classification of reversible classical gates
introduced by Aaronson et al., another part of an ambitious program to classify
all quantum gate sets.
  The classification uses, at its center, a reinterpretation of the tableau
representation of Clifford gates to give circuit decompositions, from which
elementary generators can easily be extracted. The 57 different classes are
generated in this way, 30 of which arise from the single-qubit subgroups of the
Clifford group. At a high level, the remaining classes are arranged according
to the bases they preserve. For instance, the CNOT gate preserves the X and Z
bases because it maps X-basis elements to X-basis elements and Z-basis elements
to Z-basis elements. The remaining classes are characterized by more subtle
tableau invariants; for instance, the T_4 and phase gate generate a proper
subclass of Z-preserving gates.
