The Classification of Clifford Gates over Qubits

Understand

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.