  The teleportation model of quantum computation introduced by Gottesman and
Chuang (1999) motivated the development of the Clifford hierarchy. Despite its
intrinsic value for quantum computing, the widespread use of magic state
distillation, which is closely related to this model, emphasizes the importance
of comprehending the hierarchy. There is currently a limited understanding of
the structure of this hierarchy, apart from the case of diagonal unitaries (Cui
et al., 2017; Rengaswamy et al. 2019). We explore the structure of the second
and third levels of the hierarchy, the first level being the ubiquitous Pauli
group, via the Weyl (i.e., Pauli) expansion of unitaries at these levels. In
particular, we characterize the support of the standard Clifford operations on
the Pauli group. Since conjugation of a Pauli by a third level unitary produces
traceless Hermitian Cliffords, we characterize their Pauli support as well.
Semi-Clifford unitaries are known to have ancilla savings in the teleportation
model, and we explore their Pauli support via symplectic transvections.
Finally, we show that, up to multiplication by a Clifford, every third level
unitary commutes with at least one Pauli matrix. This can be used inductively
to show that, up to a multiplication by a Clifford, every third level unitary
is supported on a maximal commutative subgroup of the Pauli group.
Additionally, it can be easily seen that the latter implies the generalized
semi-Clifford conjecture, proven by Beigi and Shor (2010). We discuss potential
applications in quantum error correction and the design of flag gadgets.
