††thanks: Most of this work was conducted when N.R. was with the Department of
Electrical and Computer Engineering, Duke University, NC, USA

# Un-Weyl-ing the Clifford Hierarchy

Tefjol Pllaha  Department of Communications and Networking, Aalto University,
Finland<EMAIL_ADDRESS>Narayanan Rengaswamy  Department of Electrical
and Computer Engineering, University of Arizona, Tucson, AZ, USA
<EMAIL_ADDRESS>Olav Tirkkonen  Department of Communications and
Networking, Aalto University, Finland<EMAIL_ADDRESS>Robert
Calderbank  Department of Electrical and Computer Engineering, Duke
University, NC, USA<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction

Quantum computing provides a fundamentally new approach to computation by
exploiting the laws of quantum mechanics that govern our universe. In this
computational model, a quantum circuit consists of a sequence of operations
each of which is either a _quantum gate_ , characterized by a unitary matrix,
or a _quantum measurement_ , characterized by a Hermitian matrix (i.e., an
_observable_) [23]. So, a _universal_ quantum computer must be capable of
implementing _arbitrary_ unitary operations and measuring any Hermitian
operator on a given set of $m$ qubits. In 1999, Gottesman and Chuang
demonstrated that such universal quantum computing can be performed just by
using the quantum teleportation protocol if one has access to certain standard
resources — Bell-state preparation, Bell-basis measurements, and arbitrary
single-qubit rotations [17]. They defined the _Clifford hierarchy_ as part of
their proof, and this has proven to be a useful characterization of a large
set of unitary operations, both in theory and practice. In fact, in their
teleportation model of computation, the level of a unitary in the hierarchy
can be interpreted as a measure of complexity of implementing it. Furthermore,
this model is closely related to the currently widespread scheme of distilling
“magic” states and injecting them via teleportation-like methods in order to
fault-tolerantly execute unitary operations on qubits encoded in a quantum
error-correcting code [4, 3]. Hence, it is very important to understand the
structure of this hierarchy since it has important implications for fault-
tolerant quantum computing.

The first level of the hierarchy is the _Pauli_ (or _Heisenberg-Weyl_) group
and the second level is the _Clifford_ group, which is defined as the
_normalizer_ of the Pauli group in the unitary group. Subsequent levels
${\mathcal{C}}^{(k)}$ of the hierarchy, for $k\geq 2$, are defined recursively
as those unitaries that map Pauli matrices to ${\mathcal{C}}^{(k-1)}$ under
conjugation [17] (see (27) for the precise definition). While the first two
levels form groups, it is known that the higher levels are only finite sets of
unitary matrices (up to overall phases) and that even when
$k\rightarrow\infty$, the hierarchy does not encompass all unitary matrices
(see Example 2). Furthermore, each level is closed under left or right
multiplication by Cliffords [35].

It is well-known that the Pauli matrices form an orthonormal basis for all
square matrices under the Hilbert-Schmidt inner product [16]. Therefore, a
natural question to consider is to determine the Pauli (i.e., Weyl) expansion
of all unitaries in the Clifford hierarchy. It is reasonable to expect that
the Pauli expansion of elements at a level provides insight into the structure
of the hierarchy. Indeed, a subset of the current authors recently identified
a special set of diagonal unitary matrices in the hierarchy, called _Quadratic
Form Diagonal (QFD)_ gates, and produced formulae for their action on Pauli
matrices [28]. In subsequent work, they considered QFD gates constructed as
tensor products of integer powers of the “${\mathbf{T}}$” gate,
${\mathbf{T}}:=\text{diag}\left(1,\exp\left(\frac{i\pi}{4}\right)\right)$.
There they examined the result of conjugating Pauli matrices by such gates,
and fully characterized the Pauli expansion of the (Clifford) result. Then
they used this characterization to understand when such a physical operation
preserves the code subspace of a _stabilizer_ quantum error-correcting code
[27, 29]. This is fundamental because such codes are necessary to make the
quantum computer tolerate noise, and all operations on the encoded information
have to be performed by such codespace-preserving physical fault-tolerant
operations. Furthermore, for universal quantum computation we need to
implement at least one non-Clifford gate, and the ${\mathbf{T}}$ gate is one
of the easiest non-Clifford gates to engineer. As a general recipe, one could
replace this (tensor product) gate with any high fidelity lab operation and
attempt to repeat this process to understand required code structure.

The Heisenberg-Weyl expansion considered in this paper is intimately connected
with the Wigner functions [32] via the Fourier transform. The discrete
counterparts are explored in [33, 15, 18]. These insights have played an
important role in the simulation and general understanding of magic states, as
well as with non-stabilizer resources [31].

In this paper, we make contributions towards a few related questions about the
hierarchy. First, surprisingly, the Pauli support (i.e., the Pauli matrices
with non-zero coefficients in the Pauli expansion) of even the well-known
Clifford group operations remains unknown. (Note that conjugating a Pauli
matrix by the transversal ${\mathbf{T}}$ gate produces a Clifford gate, so the
aforementioned result already calculates the Pauli expansion of certain types
of Cliffords.) Hence, we study the support of the “standard” Clifford
operations that correspond to the standard Clifford gate-set consisting of
Hadamard, Phase, Controlled-NOT (CNOT), and Controlled-$Z$ (CZ) gates.

Second, Zeng et al. [35] considered certain operations called _semi-Clifford_
unitaries in the hierarchy [19], which have the advantage that they require
fewer ancillae than general unitaries in the teleportation model of Gottesman
and Chuang [36]. They also showed that any semi-Clifford ${\mathbf{U}}$ can be
expressed as ${\mathbf{U}}={\mathbf{G}}_{1}{\mathbf{D}}{\mathbf{G}}_{2}$,
where ${\mathbf{D}}$ is diagonal and ${\mathbf{G}}_{1},{\mathbf{G}}_{2}$ are
Clifford operators. Cui et al. [14] have recently characterized the diagonal
unitaries in the Clifford hierarchy. We prove a general result that provides
an exact decomposition of any semi-Clifford operation in terms of diagonal
gates and physical permutation operators composed of CNOTs and Pauli $X$’s.
Thus, when combined with [14] and our contribution of characterizing the Pauli
support of standard Cliffords, this essentially produces the Weyl expansion of
semi-Cliffords.

Third, Zeng et al. conjectured in the above paper that all unitaries in
${\mathcal{C}}^{(3)}$ are semi-Clifford and all unitaries in
${\mathcal{C}}^{(k)}$ are _generalized_ semi-Clifford for any $k$. While a
semi-Clifford operation maps, by conjugation, a maximal commutative subgroup
(MCS) of the Pauli group to another MCS of the Paulis, a generalized semi-
Clifford operation maps the _span_ (i.e., complex linear combination) of a MCS
to the span of another MCS. It is well-known that for $m=1,2$ qubits all
unitaries are semi-Clifford, and for $m=3$ qubits the third level is semi-
Clifford, so these conjectures are for $k=3$ for all $m>3$ and for $k\geq 4$
for all $m\geq 3$, respectively. Gottesman and Mochon have provided a
counterexample for ${\mathcal{C}}^{(3)}$ that disproves the semi-Clifford
conjecture [34]111The authors of [28] were unaware of this result, and they
regret reporting that this conjecture remained open.. Subsequently, Beigi and
Shor [1] proved that all unitaries in ${\mathcal{C}}^{(3)}$ are generalized
semi-Clifford operations, thereby settling the conjecture for $k=3$. In this
paper, we prove the stronger result that for any unitary ${\mathbf{C}}$ from
${\mathcal{C}}^{(3)}$, there exists a Clifford ${\mathbf{G}}$ such that
${\mathbf{G}}{\mathbf{C}}$ is supported on a MCS of the Pauli group. Our proof
uses a much simpler induction argument based on the fact that any third level
unitary must map (under conjugation) at least one Pauli to some other Pauli.

Finally, the third level of the hierarchy is of particular interest since any
third level gate enables universal quantum computation when combined with the
Clifford group [17, 2]. When a ${\mathcal{C}}^{(3)}$ gate acts by conjugation
on a Pauli matrix, the result is a Hermitian Clifford, one example being the
aforementioned case of choosing a ${\mathcal{C}}^{(3)}$ operation that is a
tensor product of integer powers of ${\mathbf{T}}$. It is well-known that
Clifford transvections (that is, square roots of Hermitian Pauli matrices; see
(32)) form a different generating set for all Cliffords, compared to the
standard Clifford gate set mentioned earlier [9, 24, 20]. We prove a necessary
and sufficient condition for the Paulis involved in the transvection
decomposition of an arbitrary Hermitian Clifford operator. Since expanding the
product of transvections provides the Pauli expansion of these Hermitian
Cliffords, this can potentially be applied to extend the aforementioned result
on characterizing stabilizer codes that support transversal ${\mathbf{T}}$
gates to other gates from ${\mathcal{C}}^{(3)}$.

As a different application, _flag gadgets_ have recently become popular as a
near-term method to detect correlated faults in circuits [11, 12, 13, 10, 30].
The idea is to introduce a multi-qubit Pauli measurement before and after the
circuit, using one or more ancilla qubits, such that the extra gadget acts
trivially in the case of no errors but catches catastrophic errors otherwise.
A key requirement to construct flag gadgets for a specific application circuit
is to determine the best Pauli measurement to apply before the circuit and
identify the result of “propagating” the Pauli through the circuit, i.e.,
determine the result of conjugating the Pauli by the circuit. The simplest
case is to use a Pauli operator that commutes with the circuit. For this
purpose, any Pauli in the centralizer/dual of the support (of the
circuit/unitary) would suffice. Hence, our aforesaid results on characterizing
Pauli supports can be applied to determine the Paulis that commute with the
corresponding circuit. In particular, since flag gadgets are generally applied
only to Clifford circuits, our result that any ${\mathcal{C}}^{(3)}$ element
is supported on a MCS of the Paulis, up to multiplication by a Clifford,
provides a way to determine a Pauli that commutes with a non-Clifford element.
Therefore, this insight could be used to design flag gadgets beyond Clifford
(subsections of) circuits.

##  2 Preliminaries

###  2.1 The Binary Symplectic Group

We will denote by $\mathrm{GL}(n)$ and $\mathrm{Sym}(n)$ the groups of
$n\times n$ invertible and symmetric matrices over the binary field
${\mathbb{F}}_{2}$, respectively. Addition in ${\mathbb{F}}_{2}$ will be
denoted by $\oplus$. The  _binary symplectic group_ $\mbox{\rm
Sp}(2m)\subset\mathrm{GL}(2m)$ is the set of $2m\times 2m$ binary matrices
that preserve the  _symplectic inner product_ in ${\mathbb{F}}_{2}^{2m}$:

$\mbox{$\langle{\,{({\mathbf{a}},{\mathbf{b}})}\,}|\,{({\mathbf{c}},{\mathbf{d}})}\,\rangle_{\rm
s}$}={\mathbf{a}}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}\oplus{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}=({\mathbf{a}},{\mathbf{b}})\Omega({\mathbf{c}},{\mathbf{d}})\mbox{\rm${}^{\scriptsize{\text{t}}}$},$
(1)

where

$\Omega=\mbox{$\left[\\!\\!\begin{array}[]{cc}{\textbf{0}_{m}}&{{\mathbf{I}}_{m}}\\\
{{\mathbf{I}}_{m}}&{\textbf{0}_{m}}\end{array}\\!\\!\right]$},$ (2)

A matrix
${\mathbf{F}}=\mbox{$\left[\\!\\!\begin{array}[]{cc}{{\mathbf{A}}}&{{\mathbf{B}}}\\\
{{\mathbf{C}}}&{{\mathbf{D}}}\end{array}\\!\\!\right]$}\in\mbox{\rm Sp}(2m)$
satisfies
${\mathbf{F}}\Omega{\mathbf{F}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}=\Omega$,
which in turn is equivalent with
${\mathbf{A}}{\mathbf{B}}\mbox{\rm${}^{\scriptsize{\text{t}}}$},{\mathbf{C}}{\mathbf{D}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}\in\mathrm{Sym}(m)$
and
${\mathbf{A}}{\mathbf{D}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}\oplus{\mathbf{B}}{\mathbf{C}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}={\mathbf{I}}_{m}$.

In $\mbox{\rm Sp}(2m)$ we distinguish two subgroups:

$\displaystyle S_{D}$
$\displaystyle:=\left\\{{\mathbf{F}}_{D}({\mathbf{P}})=\mbox{$\left[\\!\\!\begin{array}[]{cc}{{\mathbf{P}}}&{\textbf{0}_{m}}\\\
{\textbf{0}_{m}}&{{\mathbf{P}}^{-}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}\end{array}\\!\\!\right]$}\,\,\middle|\,\,{\mathbf{P}}\in\mathrm{GL}(m)\right\\}$
(5) $\displaystyle\cong\mathrm{GL}(m),$ $\displaystyle S_{U}$
$\displaystyle:=\left\\{{\mathbf{F}}_{U}({\mathbf{S}})=\mbox{$\left[\\!\\!\begin{array}[]{cc}{{\mathbf{I}}_{m}}&{{\mathbf{S}}}\\\
{\textbf{0}_{m}}&{{\mathbf{I}}_{m}}\end{array}\\!\\!\right]$}\,\,\middle|\,\,{\mathbf{S}}\in\mathrm{Sym}(m)\right\\}$
(8) $\displaystyle\cong\mathrm{Sym}(m).$

Then every ${\mathbf{F}}\in\mbox{\rm Sp}(2m)$ can be _Bruhat-decomposed_ [22,
25] as

${\mathbf{F}}={\mathbf{F}}_{D}({\mathbf{P}}_{1}){\mathbf{F}}_{U}({\mathbf{S}}_{1}){\mathbf{F}}_{\Omega}(r){\mathbf{F}}_{U}({\mathbf{S}}_{2}){\mathbf{F}}_{D}({\mathbf{P}}_{2}),$
(9)

where

${\mathbf{F}}_{\Omega}(r)=\mbox{$\left[\\!\\!\begin{array}[]{cc}{{\mathbf{I}}_{m|-r}}&{{\mathbf{I}}_{m|r}}\\\
{{\mathbf{I}}_{m|r}}&{{\mathbf{I}}_{m|-r}}\end{array}\\!\\!\right]$},$ (10)

with ${\mathbf{I}}_{m|r}$ being the block matrix with ${\mathbf{I}}_{r}$ in
upper left corner and 0 elsewhere, and
${\mathbf{I}}_{m|-r}={\mathbf{I}}_{m}-{\mathbf{I}}_{m|r}$. Here $r=\mbox{{\rm
rank\,}}({\mathbf{C}})$. The semidirect product $S$ of $S_{D}$ and $S_{U}$
corresponds to $r=0$, that is, symplectic matrices with ${\mathbf{C}}={\bf
0}$. Let $\widetilde{S}$ be the subgroup of $S$ consisting of matrices
${\mathbf{F}}_{D}({\mathbf{P}}){\mathbf{F}}_{U}({\mathbf{S}})$ with
${\mathbf{P}}$ upper triangular. Then $\widetilde{S}$ has size
$2^{m(m-1)/2}\cdot 2^{m(m+1)/2}=2^{m^{2}}$ and is a 2-Sylow subgroup of
$\mbox{\rm Sp}(2m)$ that contains $S_{U}$.

Another type of decomposition of $\mbox{\rm Sp}(2m)$ can be achieved via
_symplectic transvections_
${\mathbf{T}}_{\mathbf{v}}:={\mathbf{I}}_{2m}+\Omega{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}{\mathbf{v}},\,{\mathbf{v}}\in{\mathbb{F}}_{2}^{2m}$.
Such matrix acts on ${\mathbb{F}}_{2}^{2m}$ as
${\mathbf{x}}\longmapsto{\mathbf{x}}+\mbox{$\langle{\,{{\mathbf{v}}}\,}|\,{{\mathbf{x}}}\,\rangle_{\rm
s}$}{\mathbf{v}}$, and thus ${\mathbf{T}}^{2}_{\mathbf{v}}={\mathbf{I}}_{2m}$.
In general, ${\mathbf{F}}\in\mbox{\rm Sp}(2m)$ is said to be an _involution_
if ${\mathbf{F}}^{2}={\mathbf{I}}_{2m}$ and is said to be _hyperbolic_ if
$\mbox{$\langle{\,{{\mathbf{v}}}\,}|\,{{\mathbf{v}}{\mathbf{F}}}\,\rangle_{\rm
s}$}=0$ for all ${\mathbf{v}}\in{\mathbb{F}}_{2}^{2m}$. It is well-known that
symplectic transvections generate $\mbox{\rm Sp}(2m)$ [9, 24, 20]. It is shown
there that a non-hyperbolic involution can be written as product of $r$
transvections
${\mathbf{T}}_{{\mathbf{v}}_{1}},\ldots,{\mathbf{T}}_{{\mathbf{v}}_{r}}$,
where
$r=2m-\dim(\mathrm{Fix}({\mathbf{F}}))=\dim({\mathrm{Res}}({\mathbf{F}}))$ and

$\displaystyle\mathrm{Fix}({\mathbf{F}})$
$\displaystyle:=\ker({\mathbf{I}}\oplus{\mathbf{F}}):=\\{{\mathbf{v}}\in{\mathbb{F}}_{2}^{2m}\mid{\mathbf{v}}={\mathbf{v}}{\mathbf{F}}\\},$
(11) $\displaystyle{\mathrm{Res}}({\mathbf{F}})$ $\displaystyle:=\mbox{\rm
rs}\,({\mathbf{I}}\oplus{\mathbf{F}}):=\\{{\mathbf{v}}\oplus{\mathbf{v}}{\mathbf{F}}\mid{\mathbf{v}}\in{\mathbb{F}}_{2}^{2m}\\}.$
(12)

Throughout the paper $\mbox{\rm rs}\,(\bullet)$ will denote the row space of a
matrix. Note here that, by definition, $\mathrm{Fix}({\mathbf{F}})$ and
${\mathrm{Res}}({\mathbf{F}})$ are dual of each other. The vectors
${\mathbf{v}}_{1},\ldots,{\mathbf{v}}_{r}\in{\mathrm{Res}}({\mathbf{F}})$ must
be independent, in which case we say that corresponding transvections are
independent. On the other hand, a hyperbolic involution can be written as a
product of $r+1$ transvections ($r$ as above), $r$ of which are independent
and the additional one is dependent of the others. We will see that the
_residue_ space ${\mathrm{Res}}({\mathbf{F}})$ of a symplectic ${\mathbf{F}}$
is intimately connected with the support (37) of the corresponding Clifford
${\mathbf{G}}$. On the other hand, the _fixed_ space
$\mathrm{Fix}({\mathbf{F}})$ being the dual of ${\mathrm{Res}}({\mathbf{F}})$
is intimately connected with the Paulis that commute with ${\mathbf{G}}$.
Transvections are the simplest form of involutions in $\mbox{\rm Sp}(2m)$ and
will play a central role throughout the paper for the simple reason that they
correspond to square roots of Hermitian Paulis; see (32) and (33).

###  2.2 Quantum Computation

Fix $N=2^{m}$. The standard basis vectors of ${\mathbb{C}}^{N}$ will be
indexed by binary vectors and denoted as kets, that is,
${\mathbf{e}}_{\mathbf{v}}=|{\mathbf{v}}\rangle,{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}$,
will have 1 in the position indexed by ${\mathbf{v}}$ and 0 else. The
_Heisenberg-Weyl_ group is defined as

${\mathcal{H}}{\mathcal{W}}_{N}:=\\{i^{k}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\mid{\mathbf{a}},{\mathbf{b}}\in{\mathbb{F}}_{2}^{m},k\in{\mathbb{Z}}_{4}\\}\subset{\mathbb{U}}(N),$
(13)

where

${\mathbf{D}}({\mathbf{a}},{\mathbf{b}}):|{\mathbf{v}}\rangle\longrightarrow(-1)^{{\mathbf{b}}{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|{\mathbf{v}}\oplus{\mathbf{a}}\rangle.$
(14)

We will denote by
${\mathcal{P}}{\mathcal{H}}{\mathcal{W}}_{N}:={\mathcal{H}}{\mathcal{W}}_{N}/\\{\pm{\mathbf{I}}_{N},\pm
i{\mathbf{I}}_{N}\\}$ the  _projective_ Heisenberg-Weyl group. Directly by
definition, we have

${\mathbf{D}}({\mathbf{a}},{\mathbf{b}}){\mathbf{D}}({\mathbf{c}},{\mathbf{d}})=(-1)^{{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{D}}({\mathbf{a}}\oplus{\mathbf{c}},{\mathbf{b}}\oplus{\mathbf{d}}).$
(15)

We will also define
${\mathbf{E}}({\mathbf{a}},{\mathbf{b}}):=i^{{\mathbf{a}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})$,
which constitute the Hermitian matrices in ${\mathcal{H}}{\mathcal{W}}_{N}$.
If follows by (15) that such matrices satisfy

${\mathbf{E}}({\mathbf{a}},{\mathbf{b}}){\mathbf{E}}({\mathbf{c}},{\mathbf{d}})=i^{{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}({\mathbf{a}}+{\mathbf{c}},{\mathbf{b}}+{\mathbf{d}}),$
(16)

where we view all binary vectors as integer vectors and operations are done
modulo 4; see [28, Rem. 1] for the meaning of
${\mathbf{E}}({\mathbf{a}},{\mathbf{b}})$ with
$({\mathbf{a}},{\mathbf{b}})\in{\mathbb{Z}}_{4}^{2m}$. If the arithmetic of
the arguments of operators ${\mathbf{E}}({\mathbf{a}},{\mathbf{b}})$ were to
be done modulo 2 one would have

$\displaystyle{\mathbf{E}}({\mathbf{a}},{\mathbf{b}}){\mathbf{E}}({\mathbf{c}},{\mathbf{d}})$
$\displaystyle=(-1)^{\scriptsize\mbox{$\langle{\,{({\mathbf{a}},{\mathbf{b}})}\,}|\,{({\mathbf{c}},{\mathbf{d}})}\,\rangle_{\rm
s}$}}{\mathbf{E}}({\mathbf{c}},{\mathbf{d}}){\mathbf{E}}({\mathbf{a}},{\mathbf{b}})$
(17)
$\displaystyle=i^{{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}({\mathbf{a}}+{\mathbf{c}},{\mathbf{b}}+{\mathbf{d}})$
(18)
$\displaystyle=i^{{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}({\mathbf{a}}+{\mathbf{c}},({\mathbf{b}}\oplus{\mathbf{d}})+2({\mathbf{b}}\ast{\mathbf{d}}))$
(19)
$\displaystyle=i^{{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}(-1)^{({\mathbf{a}}+{\mathbf{c}})({\mathbf{b}}\ast{\mathbf{d}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}(({\mathbf{a}}\oplus{\mathbf{c}})+2({\mathbf{a}}\ast{\mathbf{c}}),{\mathbf{b}}\oplus{\mathbf{d}})$
(20)
$\displaystyle=i^{{\mathbf{b}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}(-1)^{({\mathbf{a}}\oplus{\mathbf{c}})({\mathbf{b}}\ast{\mathbf{d}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}+({\mathbf{b}}\oplus{\mathbf{d}})({\mathbf{a}}\ast{\mathbf{c}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}({\mathbf{a}}\oplus{\mathbf{c}},{\mathbf{b}}\oplus{\mathbf{d}}).$
(21)

Above, the asterisk stands for the coordinate-wise product. We see that binary
arithmetic only ever introduces an additional sign. Thus when the sign is not
relevant (e.g., (29)) we will stick to binary arithmetic.

######  Remark 1.

From (15) we have that ${\mathbf{D}}({\mathbf{a}},{\mathbf{b}})$ and
${\mathbf{D}}({\mathbf{c}},{\mathbf{d}})$ commute iff
$\mbox{$\langle{\,{({\mathbf{a}},{\mathbf{b}})}\,}|\,{({\mathbf{c}},{\mathbf{d}})}\,\rangle_{\rm
s}$}=0$, and otherwise they anticommute. Similarly, (16) implies
${\mathbf{E}}({\mathbf{a}},{\mathbf{b}}){\mathbf{E}}({\mathbf{c}},{\mathbf{d}})=\pm{\mathbf{E}}({\mathbf{a}}+{\mathbf{c}},{\mathbf{b}}+{\mathbf{d}})$
if
$\mbox{$\langle{\,{({\mathbf{a}},{\mathbf{b}})}\,}|\,{({\mathbf{c}},{\mathbf{d}})}\,\rangle_{\rm
s}$}=0$ and
${\mathbf{E}}({\mathbf{a}},{\mathbf{b}}){\mathbf{E}}({\mathbf{c}},{\mathbf{d}})=\pm
i{\mathbf{E}}({\mathbf{a}}+{\mathbf{c}},{\mathbf{b}}+{\mathbf{d}})$ otherwise.

A  _stabilizer_ is a commutative subgroup of ${\mathcal{H}}{\mathcal{W}}_{N}$
generated by Hermitian matrices of form
$\pm{\mathbf{E}}({\mathbf{a}},{\mathbf{b}})$ that does not contain
$-{\mathbf{I}}_{N}$. Thus either ${\mathbf{E}}$ or $-{\mathbf{E}}$ belong to a
stabilizer, but not both. We will write
$S={\mathbf{E}}({\mathbf{A}},{\mathbf{B}})$ if the stabilizer $S$ is generated
by
${\mathbf{E}}({\mathbf{a}}_{1},{\mathbf{b}}_{1}),\ldots{\mathbf{E}}({\mathbf{a}}_{k},{\mathbf{b}}_{k})$,
where ${\mathbf{A}}$ and ${\mathbf{B}}$ are $k\times m$ matrices obtained by
stacking ${\mathbf{a}}_{i}$’s and ${\mathbf{b}}_{i}$’s. Since $S$ is abelian,
the matrix ${\mathbf{C}}=({\mathbf{A}}\,\,{\mathbf{B}})$ satisfies
${\mathbf{C}}\Omega{\mathbf{C}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}={\bf
0}$, and thus the row space of ${\mathbf{C}}$ is a self-orthogonal (isotropic)
subspace of ${\mathbb{F}}_{2}^{2m}$, with respect to the symplectic inner
product. A  _maximal stabilizer_ , or a  _maximal commutative subgroup_ (MCS)
is a stabilizer of size $2^{m}$. Of particular interest are MCSs

$\displaystyle X_{N}$ $\displaystyle={\mathbf{E}}({\mathbf{I}}_{m},{\bf
0}_{m})=\\{{\mathbf{E}}({\mathbf{a}},{\bf
0})\mid{\mathbf{a}}\in{\mathbb{F}}_{2}^{m}\\},$ (22) $\displaystyle Z_{N}$
$\displaystyle={\mathbf{E}}({\bf 0}_{m},{\mathbf{I}}_{m})=\\{{\mathbf{E}}({\bf
0},{\mathbf{b}})\mid{\mathbf{b}}\in{\mathbb{F}}_{2}^{m}\\}.$ (23)

We will refer to their elements as _X stabilizers_ and _Z stabilizers_ ,
respectively. Naturally, we identify $X$ stabilizers with vectors
$({\mathbf{a}},{\bf 0})\in{\mathbb{F}}_{2}^{2m}$ and $Z$ stabilizers with
vectors $({\bf 0},{\mathbf{b}})\in{\mathbb{F}}_{2}^{2m}$.

Let $S$ be a stabilizer group of size $2^{k}$. For $\varepsilon\in\\{1,-1\\}$,
the complex vector space

${\mathcal{F}}_{\varepsilon}(S):=\\{v\in{\mathbb{C}}^{N}\mid{\mathbf{E}}v=\varepsilon
v\text{ for all }{\mathbf{E}}\in S\\}$ (24)

has dimension $2^{m-k}$. In literature, ${\mathcal{F}}_{+}(S)$ is known as the
$[\\![m,m-k]\\!]$ _stabilizer code associated to $S$_ [23], which encodes
$m-k$ _logical_ qubits to $m$ _physical_ qubits. It follows that a MCS $S$
defines a $[\\![m,0]\\!]$ stabilizer code, that is,
$\dim({\mathcal{F}}_{\varepsilon}(S))=1$. For this reason
$|\psi_{\varepsilon}\rangle:={\mathcal{F}}_{\varepsilon}(S)$ is called a
_stabilizer state_. Let
$S=\langle{\mathbf{E}}_{1},\ldots,{\mathbf{E}}_{k}\rangle$ be the stabilizer
group generated by the commuting Hermitian Paulis
$\\{{\mathbf{E}}_{1},\ldots,{\mathbf{E}}_{k}\\}$. For
${\mathbf{d}}\in{\mathbb{F}}_{2}^{k}$, we will denote
$S_{\mathbf{d}}:=\langle(-1)^{d_{1}}{\mathbf{E}}_{1},\ldots,(-1)^{d_{k}}{\mathbf{E}}_{k}\rangle$.
Then

$\Pi_{\mathbf{d}}:=\prod_{n=1}^{k}\frac{{\mathbf{I}}_{N}+(-1)^{d_{n}}{\mathbf{E}}_{n}}{2}=\frac{1}{2^{k}}\sum_{{\mathbf{E}}\in
S_{\mathbf{d}}}{\mathbf{E}}$ (25)

is a projection onto ${\mathcal{F}}_{+}(S_{\mathbf{d}})$, which in turn gives
a _resolution_ of the identity [23, Sec. 10.5]:

$\sum_{{\mathbf{d}}\in{\mathbb{F}}_{2}^{k}}\Pi_{\mathbf{d}}={\mathbf{I}}_{N}.$
(26)

###  2.3 The Clifford Hierarchy

The  _Clifford hierarchy_ $\\{{\mathcal{C}}^{(k)},k\geq 1\\}$ is defined
recursively, where the first level is the Heisenberg-Weyl group, and higher
levels are defined by

${\mathcal{C}}^{(k)}=\\{{\mathbf{U}}\in{\mathbb{U}}(N)\mid{\mathbf{U}}{\mathcal{H}}{\mathcal{W}}_{N}{\mathbf{U}}^{\dagger}\subset{\mathcal{C}}^{(k-1)}\\}.$
(27)

By definition, the  _Clifford group_ $\mbox{${\rm Cliff\\!}$}_{N}$ is the
second level of the hierarchy up to overall phases, that is $\mbox{${\rm
Cliff\\!}$}_{N}:={\mathcal{C}}^{(2)}/{\mathbb{U}}(1)$. The following example
shows that the Clifford hierarchy does not exhaust ${\mathbb{U}}(N)$ and also
motivates the Weyl expansion.

######  Example 2.

Set
${\mathbf{E}}_{1}={\mathbf{E}}(010,010),{\mathbf{E}}_{2}={\mathbf{E}}(011,001),{\mathbf{E}}_{3}={\mathbf{E}}(001,111),{\mathbf{E}}_{4}={\mathbf{E}}(101,011)$.
Then
${\mathbf{W}}=({\mathbf{E}}_{1}+{\mathbf{E}}_{2}+{\mathbf{E}}_{3}+{\mathbf{E}}_{4})/2$
is easily seen to be outside of $\mbox{${\rm Cliff\\!}$}_{N}$. Further, set
${\mathbf{E}}={\mathbf{E}}(100,000)$. We have
${\mathbf{W}}{\mathbf{E}}{\mathbf{W}}^{\dagger}={\mathbf{E}}_{3}{\mathbf{W}}{\mathbf{E}}$
and
$({\mathbf{E}}_{3}{\mathbf{W}}{\mathbf{E}}){\mathbf{E}}({\mathbf{E}}_{3}{\mathbf{W}}{\mathbf{E}})^{\dagger}=-{\mathbf{E}}{\mathbf{E}}_{3}{\mathbf{W}}$.
Thus, since multiplication by Paulis (or even Cliffords) preserves the level,
iterative conjugation cannot bring ${\mathbf{E}}$ up to the same level as
${\mathbf{W}}$.

Let $\\{{\mathbf{e}}_{1},\ldots,{\mathbf{e}}_{2m}\\}$ be the standard basis of
${\mathbb{F}}_{2}^{2m}$, and consider ${\mathbf{G}}\in\mbox{${\rm
Cliff\\!}$}_{N}$. Let ${\mathbf{c}}_{i}\in{\mathbb{F}}_{2}^{2m}$ be such that

${\mathbf{G}}{\mathbf{E}}({\mathbf{e}}_{i}){\mathbf{G}}^{\dagger}=\pm{\mathbf{E}}({\mathbf{c}}_{i}).$
(28)

Then the matrix ${\mathbf{F}}_{{\mathbf{G}}}$ whose $i$th row is
${\mathbf{c}}_{i}$ is a symplectic matrix such that

${\mathbf{G}}{\mathbf{E}}({\mathbf{c}}){\mathbf{G}}^{\dagger}=\pm{\mathbf{E}}({\mathbf{c}}{\mathbf{F}}_{{\mathbf{G}}})$
(29)

for all ${\mathbf{c}}\in{\mathbb{F}}_{2}^{2m}$. We thus have a group
homomorphism

$\Phi:\mbox{${\rm Cliff\\!}$}_{N}\longrightarrow\mbox{\rm
Sp}(2m),\,{\mathbf{G}}\longmapsto{\mathbf{F}}_{{\mathbf{G}}}.$ (30)

In addition, $\Phi$ is surjective with kernel
$\ker\Phi={\mathcal{P}}{\mathcal{H}}{\mathcal{W}}_{\\!N}$ [26], and thus
$\mbox{${\rm
Cliff\\!}$}_{N}/{\mathcal{P}}{\mathcal{H}}{\mathcal{W}}_{N}\cong\mbox{\rm
Sp}(2m)$.

Given the decomposition (9), one is naturally interested on preimages of
respective symplectic matrices via $\Phi$. Namely, the unitary matrices

$\displaystyle{\mathbf{G}}_{D}({\mathbf{P}})$
$\displaystyle:=|{\mathbf{v}}\rangle\longmapsto|{\mathbf{v}}{\mathbf{P}}\rangle,$
$\displaystyle{\mathbf{G}}_{U}({\mathbf{S}})$
$\displaystyle:=\textup{diag}\left(i^{{{\mathbf{v}}{\mathbf{S}}{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}\mod
4}\right)_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}},$ (31)
$\displaystyle{\mathbf{G}}_{\Omega}(r)$
$\displaystyle:=({\mathbf{H}}_{2})^{\otimes r}\otimes{\mathbf{I}}_{2^{m-r}},$

where ${\mathbf{H}}_{2}$ is the $2\times 2$ Hadamard matrix, correspond to
${\mathbf{F}}_{D}({\mathbf{P}}),{\mathbf{F}}_{U}({\mathbf{S}}),$ and
${\mathbf{F}}_{\Omega}(r)$, respectively [6]. Strictly speaking, a preimage
$\Phi^{-1}({\mathbf{F}})$ is meant up to ${\mathcal{H}}{\mathcal{W}}_{N}$ (and
up to a eighth root of unity which we have disregarded throughout [7]).

######  Remark 3.

Since $\Phi$ is a homomorphism we have that
$\Phi({\mathbf{G}}^{\dagger})={\mathbf{F}}_{\mathbf{G}}^{-1}$. It follows that
if ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$ is Hermitian then
${\mathbf{F}}_{\mathbf{G}}$ is a symplectic involution. Conversely, if
${\mathbf{F}}$ is a symplectic involution then
${\mathbf{G}}=\Phi^{-1}({\mathbf{F}})$ satisfies
${\mathbf{G}}^{2}\in{\mathcal{H}}{\mathcal{W}}_{N}$.

We will call ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$ a _Clifford
transvection_ if $\Phi({\mathbf{G}})$ is a symplectic transvection. For
${\mathbf{v}}\in{\mathbb{F}}_{2}^{2m}$ define222Note that
$({\mathbf{I}}_{N}+i^{\lambda}{\mathbf{E}}({\mathbf{v}}))/\sqrt{2}$ is unitary
iff $\lambda=1,3$, and otherwise it is a projection.

$\displaystyle{\mathbf{G}}_{\mathbf{v}}:=\frac{{\mathbf{I}}_{N}\pm
i{\mathbf{E}}({\mathbf{v}})}{\sqrt{2}}.$ (32)

For ${\mathbf{W}}\in{\mathcal{H}}{\mathcal{W}}_{N}$ we have

$\displaystyle{\mathbf{G}}_{\mathbf{v}}{\mathbf{W}}{\mathbf{G}}_{\mathbf{v}}^{\dagger}=\begin{cases}{\mathbf{W}},&\text{
if
}{\mathbf{W}}{\mathbf{E}}({\mathbf{v}})={\mathbf{E}}({\mathbf{v}}){\mathbf{W}},\\\
\mp i{\mathbf{W}}{\mathbf{E}}({\mathbf{v}}),&\text{ if
}{\mathbf{W}}{\mathbf{E}}({\mathbf{v}})=-{\mathbf{E}}({\mathbf{v}}){\mathbf{W}}.\end{cases}$
(33)

It follows that $\Phi({\mathbf{G}}_{\mathbf{v}})={\mathbf{T}}_{\mathbf{v}}$,
and any Clifford transvection is of this form (up to
${\mathcal{H}}{\mathcal{W}}_{N}$).

In addition, we mentioned that $\mbox{\rm Sp}(2m)$ is generated by
transvections, thus ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$ is a product
of Clifford transvections. We have proved the following.

######  Proposition 4.

Any Clifford matrix ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$ can be
written as

${\mathbf{G}}={\mathbf{E}}_{0}\prod_{n=1}^{k}\frac{{\mathbf{I}}_{N}+i{\mathbf{E}}_{n}}{\sqrt{2}}=\frac{{\mathbf{E}}_{0}}{\sqrt{|S|}}\sum_{{\mathbf{E}}\in
S}\alpha_{\mathbf{E}}{\mathbf{E}},$ (34)

where
${\mathbf{E}}_{0}\in{\mathcal{H}}{\mathcal{W}}_{N},S=\langle{\mathbf{E}}_{1},\ldots,{\mathbf{E}}_{k}\rangle$,
and $\alpha_{\mathbf{E}}\in{\mathbb{C}}$.

One of the goals of this paper is to determine the $\alpha_{\mathbf{E}}$’s
produced by Clifford matrices. In particular we will see that if
${\mathbf{E}}_{1},\ldots,{\mathbf{E}}_{k}$ are independent then
$\alpha_{\mathbf{E}}\in\\{\pm 1,\pm i\\}$; see (67)-(68). If ${\mathbf{G}}$ is
Hermitian then ${\mathbf{F}}_{\mathbf{G}}$ is an involution, and thus
$k\in\\{r,r+1\\}$ where $r=2m-\dim(\mathrm{Fix}({\mathbf{F}}_{\mathbf{G}}))$
with at least $r$ transvections being independent.

##  3 Support of the Clifford Group

The set
${\mathcal{E}}_{N}=\\{{\mathbf{E}}({\mathbf{c}})\mid{\mathbf{c}}\in{\mathbb{F}}_{2}^{2m}\\}$
is an orthonormal basis for the vector space ${\mathcal{M}}_{N}({\mathbb{C}})$
of $N\times N$ complex matrices with respect to the Hermitian inner product

$\mbox{$\langle\,{{\mathbf{M}}}\,|\,{{\mathbf{N}}}\,\rangle$}:=\frac{1}{N}\mbox{\rm
Tr}({\mathbf{M}}^{\dagger}{\mathbf{N}}).$ (35)

Thus any matrix ${\mathbf{M}}\in{\mathcal{M}}_{N}({\mathbb{C}})$ is a linear
combination

${\mathbf{M}}=\sum_{{\mathbf{c}}\in{\mathbb{F}}_{2}^{2m}}\alpha_{{\mathbf{c}}}{\mathbf{E}}({\mathbf{c}}),\quad\alpha_{\mathbf{c}}=\mbox{$\langle\,{{\mathbf{E}}({\mathbf{c}})}\,|\,{{\mathbf{M}}}\,\rangle$}\in{\mathbb{C}}.$
(36)

We are interested in sums of Pauli matrices that yield Clifford matrices. The
_support_ of ${\mathbf{M}}\in{\mathcal{M}}_{N}({\mathbb{C}})$ as in (36) with
respect to ${\mathcal{E}}_{N}$ is defined as

$\displaystyle\mbox{\rm supp}({\mathbf{M}})$
$\displaystyle:=\\{{\mathbf{E}}({\mathbf{c}})\in{\mathcal{H}}{\mathcal{W}}_{\\!N}\mid\alpha_{\mathbf{c}}\neq
0\\}$ (37)
$\displaystyle\cong\\{{\mathbf{c}}\in{\mathbb{F}}_{2}^{2m}\mid\alpha_{\mathbf{c}}\neq
0\\}.$ (38)

When dealing with the support, we will conveniently switch between the two
equivalent definitions. Thus ${\mathbf{E}}({\mathbf{c}})\in\mbox{\rm
supp}({\mathbf{M}})$ iff $\mbox{\rm
Tr}({\mathbf{M}}^{\dagger}{\mathbf{E}}({\mathbf{c}}))\neq 0$. We say in this
case that ${\mathbf{M}}$ is _supported_ on $\mbox{\rm supp}({\mathbf{M}})$.

######  Remark 5.

  * (1)

Since ${\mathbf{E}}({\mathbf{c}})$ differs from ${\mathbf{D}}({\mathbf{c}})$
only by a factor $i^{k}$ we see that $\mbox{\rm
Tr}({\mathbf{M}}^{\dagger}{\mathbf{E}}({\mathbf{c}}))\neq 0$ iff $\mbox{\rm
Tr}({\mathbf{M}}^{\dagger}{\mathbf{D}}({\mathbf{c}}))\neq 0$. Thus, to avoid
the additional scaling factor, we will use matrices
${\mathbf{D}}({\mathbf{c}})$ when computing supports/traces.

  * (2)

It follows directly by the definition of support and (15) that the support of
${\mathbf{M}}{\mathbf{D}}({\mathbf{x}})$ (or
${\mathbf{D}}({\mathbf{x}}){\mathbf{M}}$) is just the translate
$\\{{\mathbf{x}}\\}+\mbox{\rm supp}({\mathbf{M}})$ for all
${\mathbf{x}}\in{\mathbb{F}}_{2}^{2m}$.

It is clear that ${\mathcal{H}}{\mathcal{W}}_{N}$ is supported on singletons.
It follows that a unitary ${\mathbf{M}}$ is a Clifford matrix iff
${\mathbf{M}}{\mathbf{E}}{\mathbf{M}}^{\dagger}$ is supported on a singleton
for all ${\mathbf{E}}\in{\mathcal{H}}{\mathcal{W}}_{N}$. On the other hand,
for ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$, we have $|\mbox{\rm
supp}({\mathbf{M}})|=2$ iff ${\mathbf{G}}$ is a Clifford transvection (up to
${\mathcal{H}}{\mathcal{W}}_{N}$). In general, we have the following immediate
consequence of Proposition 4.

######  Corollary 6.

Any Clifford matrix ${\mathbf{G}}$ is supported either on a group $S$ or on a
coset ${\mathbf{E}}_{0}S$ depending on whether ${\mathbf{G}}$ has trace or
not.

###### Proof.

Observe that ${\mathbf{E}}\in{\mathcal{H}}{\mathcal{W}}_{N}$ is traceless
unless ${\mathbf{E}}={\mathbf{I}}_{N}$. Thus, for ${\mathbf{G}}$ as in (34) we
have that $\mbox{\rm Tr}({\mathbf{G}})\neq 0$ iff ${\mathbf{E}}_{0}\in S$. It
also follows that $\mbox{\rm supp}({\mathbf{G}})={\mathbf{E}}_{0}S$. ∎

######  Remark 7.

One can easily construct non-Clifford matrices supported on a subgroup. For
instance, it follows easily from Proposition 13 that ${\mathbf{T}}^{\otimes
m}$ is supported on the subspace $\\{{\bf 0}\\}\times{\mathbb{F}}_{2}^{m}$, or
alternatively, on the subgroup $Z_{N}$ of diagonal Paulis. Thus, Corollary 6
does not completely characterize $\mbox{${\rm Cliff\\!}$}_{N}$. In fact, for
any ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$, we have

$\displaystyle{\mathbf{E}}({\mathbf{c}})\in\mbox{\rm supp}({\mathbf{G}})$
$\displaystyle\iff\mbox{\rm
Tr}\big{(}({\mathbf{G}}{\mathbf{E}}({\mathbf{c}}){\mathbf{G}}^{\dagger}){\mathbf{G}}\big{)}\neq
0$ (39) $\displaystyle\iff\mbox{\rm
Tr}\big{(}{\mathbf{E}}({\mathbf{c}}{\mathbf{F}}_{\mathbf{G}}){\mathbf{G}}\big{)}\neq
0$ (40)
$\displaystyle\iff{\mathbf{E}}({\mathbf{c}}{\mathbf{F}}_{\mathbf{G}})\in\mbox{\rm
supp}({\mathbf{G}}),$ (41)

which implies that the support of ${\mathbf{G}}$ is an  _invariant_ subspace
of ${\mathbf{F}}_{\mathbf{G}}$.

By definition, in order to understand ${\mathbf{G}}\in\mbox{${\rm
Cliff\\!}$}_{N}$ it is sufficient to understand its action on
${\mathcal{H}}{\mathcal{W}}_{N}$, which thanks to (30) can be understood via
the action of the corresponding symplectic matrix ${\mathbf{F}}_{\mathbf{G}}$
on ${\mathbb{F}}_{2}^{2m}$. Consider the fixed space
$\mathrm{Fix}({\mathbf{F}}_{\mathbf{G}})$ from (11). Then
${\mathbf{c}}\in\mathrm{Fix}({\mathbf{F}}_{\mathbf{G}})$ iff

${\mathbf{G}}{\mathbf{E}}({\mathbf{c}}){\mathbf{G}}^{\dagger}=\pm{\mathbf{E}}({\mathbf{c}}{\mathbf{F}}_{\mathbf{G}})=\pm{\mathbf{E}}({\mathbf{c}}),$
(42)

that is, iff ${\mathbf{E}}({\mathbf{c}})$ either commutes or anticommutes with
${\mathbf{G}}$. Let us now consider the Pauli matrices that commute with
${\mathbf{G}}$, that is

$C_{\mathbf{G}}=\\{{\mathbf{c}}\in\mathrm{Fix}({\mathbf{F}}_{\mathbf{G}})\mid{\mathbf{G}}{\mathbf{E}}({\mathbf{c}}){\mathbf{G}}^{\dagger}={\mathbf{E}}({\mathbf{c}})\\}.$
(43)

It is then clear that the quotient
$\mathrm{Fix}({\mathbf{F}}_{\mathbf{G}})/C_{\mathbf{G}}$ captures the Pauli
matrices that anticommute with ${\mathbf{G}}$. We will denote by
$(\raisebox{0.86108pt}{\mbox{$\scriptscriptstyle\bullet\,$}})^{{\perp_{\rm{s}}}}$
the dual w.r.t. the symplectic inner product (1). With this notation we have
the following.

######  Proposition 8.

$\mbox{\rm supp}({\mathbf{G}})\subseteq C_{\mathbf{G}}^{{\perp_{\rm{s}}}}$.

###### Proof.

We will show the reverse inclusion of the complements. Indeed, let
${\mathbf{c}}\in{\mathbb{F}}_{2}^{2m}$ be such that ${\mathbf{c}}\notin
C_{\mathbf{G}}^{{\perp_{\rm{s}}}}$. Then, there exists ${\mathbf{v}}\in
C_{\mathbf{G}}$ such that
$\mbox{$\langle{\,{{\mathbf{c}}}\,}|\,{{\mathbf{v}}}\,\rangle_{\rm s}$}=1$. It
follows that ${\mathbf{E}}({\mathbf{v}})$ commutes with ${\mathbf{G}}$ and
anticommutes with ${\mathbf{E}}({\mathbf{c}})$. Thus

$\displaystyle\mbox{\rm
Tr}\big{(}{\mathbf{G}}{\mathbf{E}}({\mathbf{c}})\big{)}$
$\displaystyle=\mbox{\rm
Tr}\Big{(}{\mathbf{E}}({\mathbf{v}})^{\dagger}{\mathbf{E}}({\mathbf{v}}){\mathbf{G}}{\mathbf{E}}({\mathbf{c}})\Big{)}$
(44) $\displaystyle=\mbox{\rm
Tr}\Big{(}{\mathbf{E}}({\mathbf{v}})^{\dagger}{\mathbf{G}}{\mathbf{E}}({\mathbf{v}}){\mathbf{E}}({\mathbf{c}})\Big{)}$
(45) $\displaystyle=-\mbox{\rm
Tr}\Big{(}{\mathbf{E}}({\mathbf{v}})^{\dagger}{\mathbf{G}}{\mathbf{E}}({\mathbf{c}}){\mathbf{E}}({\mathbf{v}})\Big{)}$
(46) $\displaystyle=-\mbox{\rm
Tr}\big{(}{\mathbf{G}}{\mathbf{E}}({\mathbf{c}})\big{)},$ (47)

which in turn implies $\mbox{\rm
Tr}({\mathbf{G}}{\mathbf{E}}({\mathbf{c}}))=0$, and hence
${\mathbf{c}}\notin\mbox{\rm supp}({\mathbf{G}})$. ∎

Next, we completely characterize the supports of standard Clifford matrices
(2.3) in terms of the invariants (11)-(12) of the defining symplectic
matrices.

######  Proposition 9.

The support of standard Clifford matrices introduced in (2.3) satisfies the
following:

  * (1)

$\mbox{\rm
supp}({\mathbf{G}}_{D}({\mathbf{P}}))={\mathrm{Res}}({\mathbf{P}}^{-1})\times\mathrm{Fix}({\mathbf{P}})^{\perp}={\mathrm{Res}}({\mathbf{P}}^{-1})\times{\mathrm{Res}}({\mathbf{P}})$.

  * (2)

Let ${\mathbf{S}}\in\mathrm{Sym}(m)$ and
$W=\ker({\mathbf{S}})=\\{{\mathbf{w}}\in{\mathbb{F}}_{2}^{m}\mid{\mathbf{w}}{\mathbf{S}}={\bf
0}\\}$. If $\mbox{\rm Tr}({\mathbf{G}}_{U}({\mathbf{S}}))\neq 0$ then
$\mbox{\rm supp}({\mathbf{G}}_{U}({\mathbf{S}}))=\\{{\bf 0}\\}\times
W^{\perp}$. Otherwise ${\mathbf{G}}_{U}({\mathbf{S}})$ is supported on a coset
of $\\{{\bf 0}\\}\times W^{\perp}$. As a consequence, the support of diagonal
Cliffords is completely characterized by the row/column space of the
associated symmetric ${\mathbf{S}}$.

  * (3)

Let $D_{r}=\\{({\mathbf{x}},{\bf 0}_{m-r},{\mathbf{x}},{\bf
0}_{m-r})\mid{\mathbf{x}}\in{\mathbb{F}}_{2}^{r}\\}\subset{\mathbb{F}}_{2}^{2m}$.
Then $\mbox{\rm supp}({\mathbf{G}}_{\Omega}(r))=({\bf 1}_{r},{\bf
0}_{2m-r})\oplus D_{r}$, where ${\bf 1}_{r}$ denotes the all ones vector of
size $r$. As a consequence, partial Hadamard matrices
${\mathbf{G}}_{\Omega}(r)$ are supported on a coset of
${\mathrm{Res}}({\mathbf{F}}_{\Omega}(r))$.

###### Proof.

(1) By definition we have
${\mathbf{G}}_{D}({\mathbf{P}})=\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}|{\mathbf{v}}{\mathbf{P}}\rangle\langle{\mathbf{v}}|$.
Thus, for ${\mathbf{G}}={\mathbf{G}}_{D}({\mathbf{P}})$ we have

$\displaystyle{\mathbf{G}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})=$
$\displaystyle\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}|{\mathbf{v}}{\mathbf{P}}\rangle\langle{\mathbf{v}}|\sum_{{\mathbf{w}}\in{\mathbb{F}}_{2}^{m}}(-1)^{{\mathbf{w}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|{\mathbf{w}}\oplus{\mathbf{a}}\rangle\langle{\mathbf{w}}|$
(48) $\displaystyle=$
$\displaystyle\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}(-1)^{{\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|({\mathbf{v}}\oplus{\mathbf{a}}){\mathbf{P}}\rangle\langle{\mathbf{v}}|.$
(49)

For ${\mathbf{a}}\in{\mathbb{F}}_{2}^{m}$ we will denote
$\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})=\\{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}\mid{\mathbf{v}}\oplus{\mathbf{v}}{\mathbf{P}}={\mathbf{a}}{\mathbf{P}}\\}$.
With this notation we have

$\mbox{\rm
Tr}\big{(}{\mathbf{G}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\big{)}=\sum_{{\mathbf{v}}\in\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})}(-1)^{{\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}.$
(50)

Since $\mathrm{Fix}({\mathbf{P}})$ is a subspace of ${\mathbb{F}}_{2}^{m}$ we
have that ${\mathbf{D}}(\textbf{0},{\mathbf{b}})\in\mbox{\rm
supp}({\mathbf{G}})$ iff ${\mathbf{b}}\in\mathrm{Fix}({\mathbf{P}})^{\perp}$.
On the other hand, for
${\mathbf{x}}\in\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})$ we have
${\mathbf{x}}\oplus\mathrm{Fix}({\mathbf{P}})=\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})$.
Indeed, the forward containment is trivial and equality follows due to equal
cardinalities. Thus, if
$\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})\neq\emptyset$, we have that
${\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\in\mbox{\rm supp}({\mathbf{G}})$ iff
${\mathbf{b}}\in\mathrm{Fix}({\mathbf{P}})^{\perp}$. Next, recall the subspace
${\mathrm{Res}}({\mathbf{P}})$ from (12). We have that
$\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})\neq\emptyset$ iff
${\mathbf{a}}\in{\mathrm{Res}}({\mathbf{P}}^{-1})$. We conclude that
${\mathbf{G}}_{D}({\mathbf{P}})$ is supported on
${\mathrm{Res}}({\mathbf{P}}^{-1})\times\mathrm{Fix}({\mathbf{P}})^{\perp}\subset{\mathbb{F}}_{2}^{2m}$.
Then by definition
$\mathrm{Fix}({\mathbf{P}})^{\perp}={\mathrm{Res}}({\mathbf{P}})$.

(2) Let ${\mathbf{G}}:={\mathbf{G}}_{U}({\mathbf{S}})$. Then

$\mbox{\rm
Tr}\big{(}{\mathbf{G}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\big{)}=\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}i^{({\mathbf{v}}\oplus{\mathbf{a}}){\mathbf{S}}({\mathbf{v}}\oplus{\mathbf{a}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}+2{\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}\langle{\mathbf{v}}|{\mathbf{v}}\oplus{\mathbf{a}}\rangle.$
(51)

It follows that ${\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\in\mbox{\rm
supp}({\mathbf{G}})$ only if ${\mathbf{a}}={\bf 0}$. So from now on we fix
${\mathbf{a}}={\bf 0}$. It is shown in [8, Appendix A] that the sum in (51) is
nonzero iff

$\sum_{{\mathbf{w}}\in
W}i^{{\mathbf{w}}{\mathbf{S}}{\mathbf{w}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}+2{\mathbf{w}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}\neq
0.$ (52)

Consider the maps
$\chi_{\mathbf{S}}:{\mathbf{w}}\longmapsto{\mathbf{w}}{\mathbf{S}}{\mathbf{w}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}$
and
$\chi_{\mathbf{b}}:{\mathbf{w}}\longmapsto+2{\mathbf{w}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}$,
and put
$\chi_{{\mathbf{S}},{\mathbf{b}}}:=\chi_{\mathbf{S}}+\chi_{\mathbf{b}}$. For
${\mathbf{v}},{\mathbf{w}}\in W$ we have

$\displaystyle\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{v}}\oplus{\mathbf{w}})$
$\displaystyle=({\mathbf{v}}\oplus{\mathbf{w}}){\mathbf{S}}({\mathbf{v}}\oplus{\mathbf{w}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}+2({\mathbf{v}}\oplus{\mathbf{w}}){\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}$
(53)
$\displaystyle=({\mathbf{v}}+{\mathbf{w}}){\mathbf{S}}({\mathbf{v}}+{\mathbf{w}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}+2({\mathbf{v}}+{\mathbf{w}}){\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}\bmod
4$ (54)
$\displaystyle=\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{v}})+\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{w}})+2{\mathbf{w}}{\mathbf{S}}{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}$
(55)
$\displaystyle=\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{v}})+\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{w}})\mod
4,$ (56)

where the last equality follows by the fact that
${\mathbf{w}}{\mathbf{S}}={\bf 0}\bmod 2$. Thus the map
${\mathbf{w}}\longmapsto i^{\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{w}})}$
is a character of $W$. It follows that ${\mathbf{D}}({\bf
0},{\mathbf{b}})\in\mbox{\rm supp}({\mathbf{G}})$ iff
$\chi_{{\mathbf{S}},{\mathbf{b}}}({\mathbf{w}})=0$ for all ${\mathbf{w}}\in
W$.

By the above argument, it also follows that $\mbox{\rm Tr}({\mathbf{G}})\neq
0$ iff $\chi_{\mathbf{S}}({\mathbf{w}})=0$ for all ${\mathbf{w}}\in W$. In
this case, (52) reduces to $\sum_{{\mathbf{w}}\in
W}(-1)^{{\mathbf{w}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}\neq
0$, which holds iff ${\mathbf{b}}\in W^{\perp}$. Similarly, $\mbox{\rm
Tr}({\mathbf{G}})=0$ iff $\chi_{\mathbf{S}}$ is not the trivial map. Since
$\chi_{\mathbf{S}}$ is an even-valued linear map (mod 4) then there exists
${\mathbf{c}}$ (depending on ${\mathbf{S}}$) such that
$\chi_{\mathbf{S}}({\mathbf{w}})=2{\mathbf{w}}{\mathbf{c}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}$.
But then it is clear that $\chi_{{\mathbf{S}},{\mathbf{b}}}$ is the zero map
iff ${\mathbf{c}}\oplus{\mathbf{b}}\in W^{\perp}$ iff
${\mathbf{b}}\in{\mathbf{c}}\oplus W^{\perp}$. It follows that $\mbox{\rm
supp}({\mathbf{G}})=\\{{\bf 0}\\}\times({\mathbf{c}}\oplus W^{\perp})$ for any
such ${\mathbf{c}}$ as above.

(3) Consider ${\mathbf{G}}={\mathbf{G}}_{\Omega}(r)$ for $0\leq r\leq m$, and
let us first handle $r=m$, which corresponds to the fully occupied Hadamard
matrix in $N=2^{m}$ dimensions. In this case, we have

$\displaystyle{\mathbf{G}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})$
$\displaystyle=\frac{1}{\sqrt{N}}\sum_{{\mathbf{v}},{\mathbf{w}}}(-1)^{{\mathbf{v}}{\mathbf{w}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|{\mathbf{v}}\rangle\langle{\mathbf{w}}|\sum_{{\mathbf{x}}\in{\mathbb{F}}_{2}^{m}}(-1)^{{\mathbf{x}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|{\mathbf{x}}\oplus{\mathbf{a}}\rangle\langle{\mathbf{x}}|$
(57)
$\displaystyle=\frac{1}{\sqrt{N}}\sum_{{\mathbf{v}},{\mathbf{x}}\in{\mathbb{F}}_{2}^{m}}(-1)^{{\mathbf{v}}({\mathbf{x}}\oplus{\mathbf{a}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}+{\mathbf{x}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|{\mathbf{v}}\rangle\langle{\mathbf{x}}|.$
(58)

The above yields

$\mbox{\rm
Tr}\big{(}{\mathbf{G}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\big{)}=\frac{1}{\sqrt{N}}\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}(-1)^{{\mathbf{v}}({\mathbf{v}}\oplus{\mathbf{a}}\oplus{\mathbf{b}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}}.$
(59)

Then map
${\mathbf{v}}\longmapsto{\mathbf{v}}({\mathbf{v}}\oplus{\mathbf{a}}\oplus{\mathbf{b}})\mbox{\rm${}^{\scriptsize{\text{t}}}$}$
is additive, and it is the trivial map iff
${\mathbf{a}}\oplus{\mathbf{b}}={\bf 1}_{m}$. Thus
${\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\in\mbox{\rm supp}({\mathbf{G}})$ iff
${\mathbf{a}}+{\mathbf{b}}={\bf 1}_{m}$. It follows that $\mbox{\rm
supp}({\mathbf{G}})=({\bf 1}_{m},{\bf 0}_{m})\oplus D_{m}$. Then, for $r<m$, a
similar argument implies that
${\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\in\mbox{\rm supp}({\mathbf{G}})$ iff
${\mathbf{a}}_{1:r}+{\mathbf{b}}_{1:r}={\bf 1}_{r}$ and
${\mathbf{a}}_{r+1:m}={\mathbf{b}}_{r+1:m}={\bf 0}_{m-r}$. The proof is
concluded with the observation that
$D_{r}={\mathrm{Res}}({\mathbf{F}}_{\Omega}(r))$. ∎

######  Remark 10.

Let ${\mathbf{P}}\in\mathrm{GL}(m)$ and ${\mathbf{S}}\in\mathrm{Sym}(m)$, and
put
${\mathbf{G}}={\mathbf{G}}_{D}({\mathbf{P}}){\mathbf{G}}_{U}({\mathbf{S}})$.
Then
${\mathbf{G}}=\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}i^{{\mathbf{v}}{\mathbf{S}}{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|{\mathbf{v}}{\mathbf{P}}\rangle\langle{\mathbf{v}}|$,
which in turn yields,

$\displaystyle\mbox{\rm
Tr}\big{(}{\mathbf{G}}{\mathbf{D}}({\mathbf{a}},{\mathbf{b}})\big{)}$
$\displaystyle=\mbox{\rm
Tr}\left(\sum_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}i^{{\mathbf{v}}{\mathbf{S}}{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}+2{\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}|({\mathbf{v}}\oplus{\mathbf{a}}){\mathbf{P}}\rangle\langle{\mathbf{v}}|\right)$
(60)
$\displaystyle=\sum_{{\mathbf{v}}\in\mathrm{Fix}_{\mathbf{a}}({\mathbf{P}})}i^{{\mathbf{v}}{\mathbf{S}}{\mathbf{v}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}+2{\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}.$
(61)

Now the analysis continues as in Proposition 9(2); see also [5, Lem. 6] for
further details.

######  Example 11.

We saw from Proposition 9 that matrices ${\mathbf{G}}_{D}({\mathbf{P}})$ are
supported on a subspace/subgroup. This is of course consistent with Corollary
6 since these matrices always have trace. Indeed, entry (1,1) is always 1
since ${\bf 0}{\mathbf{P}}={\bf 0}$. The CNOT gate is of form
${\mathbf{G}}_{D}({\mathbf{P}})$ where

${\mathbf{P}}={\mathbf{P}}^{-1}=\mbox{$\left[\\!\\!\begin{array}[]{cc}{1}&{1}\\\
{0}&{1}\end{array}\\!\\!\right]$}.$ (62)

We have ${\mathrm{Res}}({\mathbf{P}}^{-1})=\\{00,01\\}$ and
$\mathrm{Fix}({\mathbf{P}})^{\perp}=\\{00,10\\}$. Thus, $\mbox{\rm supp}({\rm
CNOT})=\\{0000,0010,0100,0110\\}$, as one can directly verify. Here we have
$m=2$ and CNOT corresponds to the symplectic ${\mathbf{F}}_{{\rm
CNOT}}={\mathbf{F}}_{D}({\mathbf{P}})$, which is a hyperbolic involution with
$\mathrm{Fix}({\mathbf{F}}_{\rm CNOT})=\mbox{\rm supp}({\rm CNOT})$. Note also
that $\mathrm{Fix}({\mathbf{F}}_{\rm CNOT})=C_{\rm CNOT}$, and thus equality
in Proposition 8 can be achieved. In addition ${\mathbf{F}}_{{\rm
CNOT}}={\mathbf{T}}_{0010}{\mathbf{T}}_{0100}{\mathbf{T}}_{0110}$. On the
complex domain we have

CNOT
$\displaystyle=\frac{1-i}{\sqrt{2}}\cdot\frac{({\mathbf{I}}+i{\mathbf{E}}_{1})({\mathbf{I}}+i{\mathbf{E}}_{2})({\mathbf{I}}-i{\mathbf{E}}_{1}{\mathbf{E}}_{2})}{\sqrt{8}}$
(63)
$\displaystyle=\frac{1}{2}({\mathbf{I}}+{\mathbf{E}}_{1}+{\mathbf{E}}_{2}-{\mathbf{E}}_{1}{\mathbf{E}}_{2}),$
(64)

where
${\mathbf{E}}_{1}={\mathbf{E}}(00,10),{\mathbf{E}}_{2}={\mathbf{E}}(01,00)$.
It follows that CNOT is supported on the MCS generated by ${\mathbf{E}}_{1}$
and ${\mathbf{E}}_{2}$.

######  Example 12.

  * (1)

Let ${\mathbf{b}}\in{\mathbb{F}}_{2}^{m}$ and consider the symmetric matrix
${\mathbf{S}}_{\mathbf{b}}:={\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}{\mathbf{b}}$.
In this case $[\ker({\mathbf{S}}_{\mathbf{b}})]^{\perp}=\\{{\bf
0},{\mathbf{b}}\\}$. In addition
${\mathbf{G}}_{U}({\mathbf{S}}_{\mathbf{b}})=({\mathbf{I}}_{N}\pm
i{\mathbf{E}}({\bf 0},{\mathbf{b}}))/\sqrt{2}$.

  * (2)

Let ${\mathbf{S}}$ be a diagonal matrix with diagonal $d_{\mathbf{S}}$. Let
$r=\mbox{${\rm wt}_{\rm H}$}(d_{\mathbf{S}})$ be the number of non-zero
elements in $d_{\mathbf{S}}$. In this case ${\mathbf{F}}_{U}({\mathbf{S}})$ is
a product of transvections ${\mathbf{T}}_{{\mathbf{v}}_{n}}$ where
${\mathbf{v}}_{n}=({\bf 0},{\mathbf{b}}_{n})$ where ${\mathbf{b}}_{n}$ is the
$n$th nonzero row of ${\mathbf{S}}$. Then

${\mathbf{G}}_{U}({\mathbf{S}})=\prod_{n=1}^{r}\frac{{\mathbf{I}}_{N}+i{\mathbf{E}}({\mathbf{v}}_{n})}{\sqrt{2}},$
(65)

from which we may also conclude that $\mbox{\rm
Tr}({\mathbf{G}}_{U}({\mathbf{S}}))\neq 0$.

We end this section by computing the supports of the _local_ Clifford group
$(\mbox{${\rm Cliff\\!}$}_{2})^{\otimes m}\subset\mbox{${\rm Cliff\\!}$}_{N}$.

######  Proposition 13 (Support of local Cliffords).

Let
${\mathbf{G}}={\mathbf{G}}_{1}\otimes\cdots\otimes{\mathbf{G}}_{m}\in(\mbox{${\rm
Cliff\\!}$}_{2})^{\otimes m}$, and let $S_{i}$ be the support of
${\mathbf{G}}_{i}$ in ${\mathbb{F}}_{2}^{2}$. Then $\mbox{\rm
supp}({\mathbf{G}})=\sigma(S_{1}\times\cdots\times S_{m})$, where $\sigma$ is
the permutation
$(a_{1},b_{1},\ldots,a_{m},b_{m})\longmapsto(a_{1},\ldots,a_{m},b_{1},\ldots,b_{m})$.

###### Proof.

The result follows immediately by the fact that the trace function is
multiplicative on pure tensors. ∎

##  4 On Hermitian Clifford matrices

Hermitian Clifford matrices, on top of being interesting on their own right,
they also play a prominent role on understanding the third level of the
Clifford hierarchy ${\mathcal{C}}^{(3)}$. Indeed, by definition,
${\mathbf{C}}{\mathcal{H}}{\mathcal{W}}_{N}{\mathbf{C}}^{\dagger}\subset\mbox{${\rm
Cliff\\!}$}_{N}$ for all ${\mathbf{C}}\in{\mathcal{C}}^{(3)}$. The conjugate
action preserves traces and the Hermitian property. Thus, other than the
identity, only traceless Clifford matrices can emerge from conjugate action
with a third level matrix. With the same notation as in Proposition 4, we see
that ${\mathbf{G}}$ is traceless iff ${\mathbf{E}}_{0}\notin S$. Further,
${\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}$ must also be a Hermitian
Clifford matrix for any Hermitian Pauli matrix ${\mathbf{E}}$. The
corresponding symplectic matrix
$\Phi({\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger})$ is an involution, and
symplectic matrices emerging in this way (${\mathbf{C}}$ fixed, ${\mathbf{E}}$
varies) must commute. This fact, although elementary, is crucial because any
group of commuting involutions is conjugate333Two groups $S$ and $S^{\prime}$
are called conjugate if there exists $g$ such that $S^{\prime}=gSg^{\dagger}$.
with some subgroup of $S_{U}$ from (8). This means that, for instance, the
CNOT gate (or any Clifford matrix of form ${\mathbf{G}}_{D}({\mathbf{P}})$)
cannot emerge from a third level action, despite ${\mathbf{F}}_{\rm CNOT}$
being a symplectic involution; see also Example 11.

We have mentioned that any Clifford matrix, is, up to a multiplication by a
Pauli, a product of transvections. We have the following structural results if
the transvections involved are independent.

######  Theorem 14.

Let ${\mathbf{E}}_{n}={\mathbf{E}}({\mathbf{c}}_{n}),n=1,\ldots,k$, be a set
of $k$ _independent_ Hermitian Pauli matrices. Let also
${\mathbf{E}}_{0}={\mathbf{E}}({\mathbf{c}}_{0})$ be a Hermitian Pauli matrix.
Then, the Clifford matrix

${\mathbf{G}}={\mathbf{E}}_{0}\prod_{n=1}^{k}\frac{1}{\sqrt{2}}({\mathbf{I}}+i{\mathbf{E}}_{n}),$
(66)

is Hermitian iff ${\mathbf{E}}_{0}$ anticommutes with all ${\mathbf{E}}_{n}$
and all ${\mathbf{E}}_{n}$ commute with each other. As a consequence, if
${\mathbf{G}}$ is Hermitian then it is also traceless.

###### Proof.

Let ${\mathbf{C}}:=({\mathbf{A}}\,\,{\mathbf{B}})$ be the $k\times 2m$ binary
matrix whose $n$th row is
${\mathbf{c}}_{n}=({\mathbf{a}}_{n},{\mathbf{b}}_{n})$. Since all the
${\mathbf{E}}_{n}$ are independent we have that $\mbox{{\rm
rank\,}}({\mathbf{C}})=k$. Using (16) we have that

$\begin{split}{\mathbf{G}}&=\frac{{\mathbf{E}}_{0}}{\sqrt{2^{k}}}\sum_{{\mathbf{d}}\in{\mathbb{F}}_{2}^{k}}i^{{\mathbf{d}}({\mathbf{I}}_{k}+\widetilde{{\mathbf{C}}}){\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}({\mathbf{d}}{\mathbf{C}}\\!\\!\\!\\!\mod
4)\\\
&=\frac{1}{\sqrt{2^{k}}}\sum_{{\mathbf{d}}\in{\mathbb{F}}_{2}^{k}}i^{{\mathbf{d}}({\mathbf{I}}_{k}+\widetilde{{\mathbf{C}}}){\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}_{0}{\mathbf{E}}({\mathbf{d}}{\mathbf{C}}\\!\\!\\!\\!\mod
4),\end{split}$ (67)

where $\widetilde{{\mathbf{C}}}$ is the $k\times k$ matrix whose $(i,j)$ entry
is
${\mathbf{a}}_{j}{\mathbf{b}}_{i}\\!\\!\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}_{i}{\mathbf{b}}_{j}\\!\\!\mbox{\rm${}^{\scriptsize{\text{t}}}$}\\!\\!\mod
4$ if $i<j$ and 0 else. If we write
${\mathbf{c}}_{0}=({\mathbf{a}}_{0},{\mathbf{b}}_{0})$, then (67) can be
further rewritten as

${\mathbf{G}}=\frac{1}{\sqrt{2^{k}}}\sum_{{\mathbf{d}}\in{\mathbb{F}}_{2}^{k}}i^{{\mathbf{d}}({\mathbf{I}}_{k}+\widetilde{{\mathbf{C}}}){\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}i^{{\mathbf{d}}{\mathbf{A}}{\mathbf{b}}_{0}\\!\\!\\!\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}_{0}{\mathbf{B}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}{\mathbf{E}}({\mathbf{d}}{\mathbf{C}}+{\mathbf{c}}_{0})$
(68)

It follows immediately that ${\mathbf{G}}$ is Hermitian iff all coefficients
in (68) are $\pm 1$.

By looking at the standard basis of ${\mathbb{F}}_{2}^{k}$, i.e.,
${\mathbf{d}}={\mathbf{e}}_{n}$, and corresponding coefficients, we see that
${\mathbf{a}}_{n}{\mathbf{b}}_{0}\\!\\!\\!\mbox{\rm${}^{\scriptsize{\text{t}}}$}\oplus{\mathbf{a}}_{0}{\mathbf{b}}_{n}\\!\\!\\!\mbox{\rm${}^{\scriptsize{\text{t}}}$}=1$
for $n=1,\ldots,k$, which in turn means that ${\mathbf{E}}_{0}$ anticommutes
with ${\mathbf{E}}_{n}$. To show that ${\mathbf{E}}_{j},{\mathbf{E}}_{n}$
commute, consider ${\mathbf{d}}$ of weight two with ones in positions $j,n$.
This corresponds to looking at the coefficient of
${\mathbf{E}}_{0}{\mathbf{E}}_{j}{\mathbf{E}}_{n}$. Because ${\mathbf{E}}_{0}$
anticommutes with both ${\mathbf{E}}_{j},{\mathbf{E}}_{n}$, the term
$i^{{\mathbf{d}}{\mathbf{A}}{\mathbf{b}}_{0}\\!\\!\\!\mbox{\rm${}^{\scriptsize{\text{t}}}$}-{\mathbf{a}}_{0}{\mathbf{B}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}$
contributes $\pm 1$ and the term
$i^{{\mathbf{d}}{\mathbf{I}}_{k}{\mathbf{d}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}}=i^{\rm
wt({\mathbf{d}})}$ contributes $-1$. Thus, the overall coefficient will be
$\pm 1$ only if ${\mathbf{E}}_{j},{\mathbf{E}}_{n}$ commute.

For the converse, one could argue similarly to show that the coefficients in
(68) are $\pm 1$. However, we point out here that the statement follows
immediately from (66).

Finally, for Hermitian ${\mathbf{G}}$ as in (66) we argued that
${\mathbf{E}}_{0}$ anticommutes with all ${\mathbf{E}}_{n}$. Thus
${\mathbf{E}}_{0}$ cannot be contained on the commutative group generated by
all ${\mathbf{E}}_{n}$. As we have mentioned earlier, this implies that
${\mathbf{G}}$ is traceless. ∎

######  Remark 15.

Recall Proposition 4 where a Clifford matrix ${\mathbf{G}}$ is written as a
generic sum of Hermitian matrices ${\mathbf{E}}$. In (68) we have explicitly
computed the coefficients $\alpha_{\mathbf{E}}$, and evidently, they are of
form $i^{Q({\mathbf{v}})},{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}$ where $Q$ is a
quadratic form $\mod 4$. This generalizes a result of [6] (see also [8]) where
the authors showed that the coefficients of  _diagonal_ Clifford matrices are
determined by a quadratic form. Indeed, diagonal Clifford matrices are of form
${\mathbf{G}}_{U}({\mathbf{S}}),{\mathbf{S}}\in\mathrm{Sym}(m)$, and we see
the aforementioned quadratic form in (51)- (52).

######  Remark 16.

If ${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$ is Hermitian, we mentioned
that the corresponding symplectic matrix ${\mathbf{F}}_{\mathbf{G}}$ must be
an involution, which we also mentioned can be written as a product of
$k\in\\{r,r+1\\}$ transvections,
$r=2m-\dim(\mathrm{Fix}({\mathbf{F}}_{\mathbf{G}}))$, where at least $r$ are
independent. Theorem 14 settles the scenario when ${\mathbf{F}}_{\mathbf{G}}$
is a product of only independent transvections. When the additional
transvection ${\mathbf{T}}_{r+1}$ is dependent of the other $r$ transvections,
then multiplying ${\mathbf{G}}={\mathbf{T}}_{1}\cdots{\mathbf{T}}_{r}$ with
${\mathbf{T}}_{r+1}$ may preserve the support of ${\mathbf{G}}$ (see Example
11) or reduce the support of ${\mathbf{G}}$. In the latter instance the
supported is reduced by half. Keeping track of the support of
${\mathbf{G}}{\mathbf{T}}_{r+1}$ becomes tedious and involves sign chasing
that depends on the commutativity relation of
${\mathbf{T}}_{1},\ldots,{\mathbf{T}}_{r}$.

##  5 On (Generalized) Semi-Clifford Matrices

For $k\geq 3$ the levels ${\mathcal{C}}^{(k)}$ of the Clifford hierarchy do
not form a group, and thus a complete characterization becomes challenging. In
[35] the authors use the notion of semi-Clifford matrices to achieve partial
results. A unitary matrix ${\mathbf{U}}\in{\mathbb{U}}(N)$ is called _semi-
Clifford_ if there exists a MCS
$S_{1}\subset{\mathcal{H}}{\mathcal{W}}_{\\!N}$ such that
$S_{2}={\mathbf{U}}S_{1}{\mathbf{U}}^{\dagger}$ is also MCS. Since the
Clifford group $\mbox{${\rm Cliff\\!}$}_{N}$ permutes stabilizers of a given
dimension, a Clifford matrix is trivially semi-Clifford. It is shown in [35]
that for $m=1,2$ qubits the Clifford hierarchy is comprised of semi-Clifford
matrices, and for $m=3$ qubits the third level ${\mathcal{C}}^{(3)}$ is
comprised of semi-Clifford matrices. Moreover, they show that for $m>2$ qubits
that there exist non semi-Clifford matrices in each level
${\mathcal{C}}^{(k)},k>3$, and conjecture that the third level
${\mathcal{C}}^{(3)}$ is comprised of semi-Cliffords for any number of qubits.
The conjecture was disproved by Gottesman and Mochon via a counterexample with
$m=7$ qubits; see [1]. On the other hand, the diagonal elements of each level,
denoted ${\mathcal{C}}^{(k)}_{d}$ do form a group [35, Prop. 4], and are
completely characterized in [14]. The QFD gates of [28] represent all 1- and
2-local diagonal gates in the hierarchy, and thus forming a particularly nice
subclass of diagonal gates.

######  Remark 17.

Multiplying by Clifford matrix preserves the levels of the hierarchy. Thus,
without loss of generality, we will consider semi-Clifford matrices (and any
matrix in the hierarchy) up to multiplication by Clifford matrices. This
enables us to adjust any semi-Clifford ${\mathbf{U}}$ matrix so that it fixes
any given given MCS $S$. Indeed, assume
${\mathbf{U}}S_{1}{\mathbf{U}}^{\dagger}=S_{2}$. Let
${\mathbf{G}}_{1},{\mathbf{G}}_{2}\in\mbox{${\rm Cliff\\!}$}_{N}$ be such that
${\mathbf{G}}_{1}S{\mathbf{G}}_{1}^{\dagger}=S_{1}$ and
${\mathbf{G}}_{2}S_{2}{\mathbf{G}}_{2}^{\dagger}=S$. Then
${\mathbf{G}}_{2}{\mathbf{U}}{\mathbf{G}}_{1}$ is a semi-Clifford matrix that
fixes $S$. As mentioned earlier, by [26, Alg. 1], there exists
${\mathbf{G}}_{3}\in\mbox{${\rm Cliff\\!}$}_{N}$ such that
${\mathbf{G}}_{3}{\mathbf{G}}_{2}{\mathbf{U}}{\mathbf{G}}_{1}$ fixes $S$
pointwise.

######  Theorem 18.

Let ${\mathbf{C}}\in{\mathcal{C}}^{(k)}$ be a unitary matrix that fixes the
group of diagonal Paulis $Z_{N}={\mathbf{E}}({\bf 0}_{m},{\mathbf{I}}_{m})$.
Then ${\mathbf{C}}={\mathbf{D}}{\mathbf{E}}({\mathbf{a}},{\bf
0}){\mathbf{G}}_{D}({\mathbf{P}})$, for some diagonal
${\mathbf{D}}\in{\mathcal{C}}_{d}^{(k)},{\mathbf{P}}\in\mathrm{GL}(m)$, and
${\mathbf{a}}\in{\mathbb{F}}_{2}^{m}$.

We will make use of the structure of first order Reed-Muller codes to prove
Theorem 18. Let
$C=\\{({\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}\\!\\!\mod
2)_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}\mid{\mathbf{b}}\in{\mathbb{F}}_{2}^{m}\\}$.
Then, the _first-order Reed-Muller_ code is the linear
$[2^{m},m+1,2^{m-1}]_{2}$-code

${\mathrm{RM}}(1,m)=C\cup\\{{\mathbf{c}}\oplus{\bf 1}\mid{\mathbf{c}}\in
C\\}.$ (69)

The automorphism group of ${\mathrm{RM}}(1,m)$ is the general affine group
${\mathrm{GA}}(m)$ of maps
${\mathbf{v}}\longmapsto{\mathbf{v}}{\mathbf{P}}\oplus{\mathbf{a}},{\mathbf{P}}\in\mathrm{GL}(m),{\mathbf{a}}\in{\mathbb{F}}_{2}^{m}$;
see [21, Chapter 13] for instance.

Proof of Theorem 18. Assume that ${\mathbf{C}}\in{\mathcal{C}}^{(k)}$ fixes
$Z_{N}$, and let $v\in{\mathbb{C}}^{N}$ be a common eigenvector of all
${\mathbf{D}}({\bf 0},{\mathbf{b}})\in Z_{N}$. Then, by assumption, we have

${\mathbf{E}}({\bf 0},{\mathbf{b}}){\mathbf{C}}v={\mathbf{C}}{\mathbf{E}}({\bf
0},{\mathbf{b}}^{\prime})v=\pm{\mathbf{C}}v,$ (70)

which in turn implies that ${\mathbf{C}}v$ is also a common eigenvector of
$Z_{N}$. Thus ${\mathbf{C}}$ maps the common eigenvector
$|{\mathbf{v}}\rangle$ to another common eigenvector which is of the form
$\alpha_{\mathbf{v}}|\pi({\mathbf{v}})\rangle$ for some
$\pi({\mathbf{v}})\in{\mathbb{F}}_{2}^{m}$ and
$\alpha_{\mathbf{v}}\in{\mathbb{C}}$. In other words, ${\mathbf{C}}$ is a
monomial map, that is ${\mathbf{C}}={\mathbf{D}}\Pi$, where ${\mathbf{D}}$ is
the diagonal matrix with entry $\alpha_{\mathbf{v}}$ in position
$\pi({\mathbf{v}})$ and $\Pi$ is the permutation
${\mathbf{v}}\longmapsto\pi({\mathbf{v}})$. The assumption
${\mathbf{C}}\in{\mathcal{C}}^{(k)}$ implies
${\mathbf{D}}\in{\mathcal{C}}^{(k)}_{d}$. By construction, the diagonals of
Paulis in $Z_{N}$ are of form
$\pm((-1)^{{\mathbf{v}}{\mathbf{b}}\mbox{\rm${}^{\scriptsize{\text{t}}}$}})_{{\mathbf{v}}\in{\mathbb{F}}_{2}^{m}}$,
and we point out that the exponents of such diagonals are precisely the
elements of ${\mathrm{RM}}(1,m)$. Thus $\Pi$ induces an isometry on
${\mathrm{RM}}(1,m)$, which as we mentioned must be an invertible affine map.
That is, $\Pi={\mathbf{E}}({\mathbf{a}},{\bf
0}){\mathbf{G}}_{D}({\mathbf{P}})$ for some diagonal
${\mathbf{P}}\in\mathrm{GL}(m)$, and ${\mathbf{a}}\in{\mathbb{F}}_{2}^{m}$. In
particular we have $\Pi\in\mbox{${\rm Cliff\\!}$}_{N}$, which along with the
assumption ${\mathbf{C}}\in{\mathcal{C}}^{(k)}$ implies
${\mathbf{D}}\in{\mathcal{C}}_{d}^{(k)}$. ∎

######  Remark 19.

In [35] it was shown that a semi-Clifford
${\mathbf{C}}\in{\mathcal{C}}_{d}^{(k)}$ is of the form
${\mathbf{C}}={\mathbf{G}}_{1}{\mathbf{D}}{\mathbf{G}}_{2}$ for some
${\mathbf{G}}_{1},{\mathbf{G}}_{2}\in\mbox{${\rm Cliff\\!}$}_{N}$ and
${\mathbf{D}}\in{\mathcal{C}}_{d}^{(k)}$. Theorem 18 further extends this
result by characterizing the Clifford matrices that appear into decomposition
of ${\mathbf{C}}$. Thus, we obtain a complete characterization of semi-
Clifford elements in the Clifford hierarchy. We believe that this result,
along with the notion of the support can be used in many applications, e.g.,
design of flag gadgets.

The argument of Theorem 18 holds in a slightly more general setting.

######  Remark 20.

  * (1)

Let ${\mathbf{C}}$ be any unitary matrix that fixes a MCS
$S=\langle{\mathbf{E}}_{1},\ldots,{\mathbf{E}}_{m}\rangle$. For
${\mathbf{d}}\in{\mathbb{F}}_{2}^{m}$ denote
$S_{\mathbf{d}}:=\langle(-1)^{d_{1}}{\mathbf{E}}_{1},\ldots,(-1)^{d_{m}}{\mathbf{E}}_{m}\rangle$,
and put ${\mathcal{F}}_{+}(S_{\mathbf{d}}):=|\psi_{\mathbf{d}}\rangle$. For
any ${\mathbf{E}}\in S_{\mathbf{d}}$ we have

${\mathbf{E}}{\mathbf{C}}|\psi_{\mathbf{d}}\rangle={\mathbf{C}}{\mathbf{E}}^{\prime}|\psi_{\mathbf{d}}\rangle=\pm{\mathbf{C}}|\psi_{\mathbf{d}}\rangle,$
(71)

and thus
${\mathbf{C}}|\psi_{\mathbf{d}}\rangle\in{\mathcal{F}}_{+}(S_{{\mathbf{d}}^{\prime}})$
for some ${\mathbf{d}}^{\prime}\in{\mathbb{F}}_{2}^{m}$. This means that
${\mathbf{C}}|\psi_{\mathbf{d}}\rangle=\lambda_{\mathbf{d}}|\psi_{{\mathbf{d}}^{\prime}}\rangle$
for some eigenvalue $\lambda_{\mathbf{d}}$. In particular, ${\mathbf{C}}$ is a
monomial matrix with respect to the eigenbasis
${\mathcal{E}}_{S}:=\\{|\psi_{\mathbf{d}}\rangle\mid{\mathbf{d}}\in{\mathbb{F}}_{2}^{m}\\}$.

  * (2)

Let ${\mathbf{C}}$ be a unitary matrix that fixes the _span_ of $Z_{N}$, that
is, ${\mathbf{C}}$ maps any diagonal to another diagonal. Then ${\mathbf{C}}$
is a monomial matrix. In particular, any semi-Clifford matrix is a monomial
matrix up to some Clifford correction; see also [35, Prop. 2].

Let ${\mathbf{C}}\in{\mathcal{C}}^{(3)}$ be such that it fixes some subgroup
$\widehat{S}$ (of ${\mathcal{H}}{\mathcal{W}}_{N}$) under conjugation; see
also Remark 17. Then, by [26, Alg. 1], there exists
${\mathbf{G}}\in\mbox{${\rm Cliff\\!}$}_{N}$, produced as a sequence of
transvections, such that $\widehat{{\mathbf{C}}}:={\mathbf{G}}{\mathbf{C}}$
fixes $\widehat{S}$ _point-wise_. Let $\widehat{S}^{{\perp_{\rm{s}}}}$ be all
the Pauli matrices that commute with elements of $\widehat{S}$. Proceeding
similarly as in the proof of Proposition 8 we have the following.

######  Proposition 21.

$\mbox{\rm
supp}(\widehat{{\mathbf{C}}})\subset\widehat{S}^{{\perp_{\rm{s}}}}$, and thus
$\mbox{\rm supp}({\mathbf{C}})\subset
S:=\\{{\mathbf{E}}{\mathbf{E}}^{\prime}\mid{\mathbf{E}}\in\mbox{\rm
supp}({\mathbf{G}}^{-1}),\,{\mathbf{E}}^{\prime}\in\widehat{S}^{{\perp_{\rm{s}}}}\\}$.

######  Corollary 22.

Let ${\mathbf{C}}$ be a unitary matrix and $S$ be a MCS. If ${\mathbf{C}}$
fixes $S$ pointwise then $\mbox{\rm supp}({\mathbf{C}})\subset S$. The
converse is also true. This property characterizes semi-Clifford matrices up
to multiplication by Clifford. In particular, as for Hermitian Clifford
matrices, we have that ${\mathbf{C}}$ is supported on a _commutative_
subgroup.

In the reminder of this section we show that Corollary 22 holds for the entire
third level ${\mathcal{C}}^{(3)}$ of the hierarchy (always up to Cliffords).
Note that this is not a trivial step because, as mentioned before, there exist
elements in ${\mathcal{C}}^{(3)}$ that are not semi-Cliffords [1].

######  Lemma 23.

For ${\mathbf{C}}\in{\mathcal{C}}^{(3)}$ there exists a Pauli
$\widetilde{{\mathbf{E}}}$ such that
${\mathbf{C}}\widetilde{{\mathbf{E}}}{\mathbf{C}}^{\dagger}$ is also a Pauli.
As a consequence, there exists a Clifford correction ${\mathbf{G}}$ such that
${\mathbf{G}}{\mathbf{C}}$ fixes (i.e., commutes with) some Pauli matrix.

###### Proof.

Let ${\mathbf{C}}\in{\mathcal{C}}^{(3)}$ and consider the map

$\varphi_{\mathbf{C}}:\left\\{\begin{array}[]{ccccc}{\mathcal{P}}{\mathcal{H}}{\mathcal{W}}_{\\!N}&\xrightarrow{\phi_{\mathbf{C}}}&\mbox{${\rm
Cliff\\!}$}_{N}&\xrightarrow{\,\,\Phi\,\,}&\mbox{\rm Sp}(2m)\\\
{\mathbf{E}}&\longmapsto&{\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}&\longmapsto&\Phi({\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger})\end{array}\right.$

where $\Phi$ is the map from (30) and
${\mathcal{P}}{\mathcal{H}}{\mathcal{W}}_{\\!N}$ is the projective form of
${\mathcal{H}}{\mathcal{W}}_{\\!N}$ that ignores phases. Then
$\ker\varphi_{\mathbf{C}}\subset{\mathcal{P}}{\mathcal{H}}{\mathcal{W}}_{\\!N}$
has size $2^{k}$ for some $k\geq 0$. So, we see that $G:=\mbox{\rm
im}\,\varphi_{\mathbf{C}}\subset\mbox{\rm Sp}(2m)$ has size $2^{2m-k}$.

Let $G$ act on ${\mathbb{F}}_{2}^{2m}\setminus\\{{\bf 0}\\}$. Since the size
of an orbit must divide the size of the group $G$, each orbit has size a power
of $2$ as well. However, since the orbits partition a set of size $2^{2m}-1$
(odd), there must exist an orbit of odd size, and that size must be $2^{0}=1$.
This means that there exists ${\bf 0}\neq{\mathbf{c}}\in{\mathbb{F}}_{2}^{2m}$
that is fixed by all symplectic matrices
$\Phi({\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger})$. The definition of
$\Phi$ yields that the Hermitian Pauli
$\widetilde{{\mathbf{E}}}:={\mathbf{E}}({\mathbf{c}})$ either commutes or
anticommutes with all ${\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}$. In
other words

$\widetilde{{\mathbf{E}}}{\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}=\alpha_{\mathbf{E}}{\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}\widetilde{{\mathbf{E}}},\quad\alpha_{\mathbf{E}}=\pm
1,$ (72)

for all Paulis ${\mathbf{E}}$. Now put
$\widetilde{{\mathbf{C}}}=\widetilde{{\mathbf{E}}}{\mathbf{C}}\widetilde{{\mathbf{E}}}$.
Let also $\sigma_{\mathbf{E}}=\pm 1$ be such that
$\widetilde{{\mathbf{E}}}{\mathbf{E}}=\sigma_{\mathbf{E}}{\mathbf{E}}\widetilde{{\mathbf{E}}}$.
We have that

$\widetilde{{\mathbf{E}}}{\mathbf{C}}=\widetilde{{\mathbf{C}}}\widetilde{{\mathbf{E}}}\text{\quad
and\quad}\widetilde{{\mathbf{E}}}{\mathbf{C}}^{\dagger}=\widetilde{{\mathbf{C}}}^{\dagger}\widetilde{{\mathbf{E}}},$
(73)

which combined with (72) yields

$\alpha_{\mathbf{E}}{\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}=\sigma_{\mathbf{E}}\widetilde{{\mathbf{C}}}{\mathbf{E}}\widetilde{{\mathbf{C}}}^{\dagger}$
(74)

for all Paulis ${\mathbf{E}}$. Now it is easy to see that
${\mathbf{C}}\widetilde{{\mathbf{C}}}^{\dagger}$ is a Pauli
${\mathbf{E}}^{\prime}$, and thus (73) implies
${\mathbf{C}}\widetilde{{\mathbf{E}}}{\mathbf{C}}^{\dagger}={\mathbf{E}}^{\prime}\widetilde{{\mathbf{E}}}$.
∎

######  Remark 24.

The proof of Lemma 23 could have been concluded using the language of
stabilizer codes. With the same notation, let $\widetilde{{\mathbf{E}}}$ be
such that it either commutes or anticommutes with all
${\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}\in\mbox{${\rm
Cliff\\!}$}_{N}$. Now consider the stabilizer group
$S=\langle\widetilde{{\mathbf{E}}}\rangle$ and the corresponding stabilizer
codes ${\mathcal{F}}_{\varepsilon}:={\mathcal{F}}_{\varepsilon}(S)$, for
$\varepsilon=\pm 1$ (see (24)). We have that
${\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}{\mathcal{F}}_{\varepsilon}=\pm{\mathcal{F}}_{\varepsilon}$
for all Paulis ${\mathbf{E}}$. In other words, for any
$v\in{\mathcal{F}}_{\varepsilon}$, we have that

$\varepsilon\widetilde{{\mathbf{E}}}\cdot{\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}v=\pm\left({\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}\cdot\varepsilon\widetilde{{\mathbf{E}}}v\right)=\pm{\mathbf{C}}{\mathbf{E}}{\mathbf{C}}^{\dagger}v$
(75)

holds for all ${\mathbf{E}}$. Next, express
${\mathbf{C}}=\sum_{\mathbf{E}}\alpha_{\mathbf{E}}{\mathbf{E}}$ and sum both
sides in (75) to obtain

$\varepsilon\widetilde{{\mathbf{E}}}\left(\sum_{\mathbf{E}}\alpha_{\mathbf{E}}{\mathbf{E}}\right)v=\varepsilon^{\prime}\left(\sum_{\mathbf{E}}\alpha_{\mathbf{E}}{\mathbf{E}}\right)v.$
(76)

In other words,
$\varepsilon\widetilde{{\mathbf{E}}}{\mathbf{C}}v=\varepsilon^{\prime}{\mathbf{C}}v$,
and thus ${\mathbf{C}}$ permutes $\\{{\mathcal{F}}_{\varepsilon}\\}$. This is
equivalent with ${\mathbf{C}}$ mapping $\widetilde{{\mathbf{E}}}$ to some
other Pauli.

Next we prove the main result about the support of gates in
${\mathcal{C}}^{(3)}$, which can then be straightforwardly used to show that
every gate in ${\mathcal{C}}^{(3)}$ is generalized semi-Clifford. Recall that
a generalized semi-Clifford matrix is a unitary matrix that maps under
conjugation the span of some MCS to the span of some other MCS.

######  Theorem 25.

Let ${\mathbf{C}}$ be a unitary matrix from ${\mathcal{C}}^{(3)}$. Then there
exists a Clifford ${\mathbf{G}}$ such that ${\mathbf{G}}{\mathbf{C}}$ is
supported on a maximal commutative subgroup of
${\mathcal{H}}{\mathcal{W}}_{\\!N}$.

###### Proof.

From Lemma 23 we know that there exists some Clifford ${\mathbf{H}}$ such that
${\mathbf{H}}{\mathbf{C}}$ commutes with some
${\mathbf{E}}\in{\mathcal{H}}{\mathcal{W}}_{\\!N}$. Now consider the group
$S=\langle{\mathbf{E}}\rangle$ and its normalizer in
${\mathcal{H}}{\mathcal{W}}_{\\!N}$ which we denote by
$S^{{{\perp_{\rm{s}}}}}$. Then, since ${\mathbf{H}}{\mathbf{C}}$ preserves $S$
under conjugation, it is a valid logical operator for the $[\\![m,m-1]\\!]$
stabilizer code defined by $S$, i.e., it maps code states ($+1$ eigenvectors
of ${\mathbf{E}}$) to code states. Denote this logical $(m-1)$-qubit operation
realized by ${\mathbf{H}}{\mathbf{C}}$ as
$\overline{{\mathbf{C}}}_{{\mathbf{H}}}$. Since
${\mathbf{H}}{\mathbf{C}}\in{\mathcal{C}}^{(3)}$, we know that
${\mathbf{H}}{\mathbf{C}}$ must satisfy the necessary conjugation conditions
on logical Paulis as determined by $\overline{{\mathbf{C}}}_{\mathbf{H}}$.
These conditions can only correspond to physical realizations of logical
Clifford gates (since physical Cliffords cannot realize anything above the
second level $\mbox{${\rm Cliff\\!}$}_{N}={\mathcal{C}}^{(2)}$). Hence, we
conclude that $\overline{{\mathbf{C}}}_{\mathbf{H}}\in{\mathcal{C}}^{(3)}$ (in
the logical space).

First, it has already been shown in [35] that operations in
${\mathcal{C}}^{(3)}$ are semi-Clifford for $1$ and $2$ qubits. Using
Corollary 22, this automatically means that up to some Clifford correction
such gates are supported on a MCS. Therefore, we consider the induction
hypothesis that for $(m-1)$ qubits, any ${\mathcal{C}}^{(3)}$ element is
supported on a MCS, up to multiplication by some Clifford. Applying this
hypothesis for $\overline{{\mathbf{C}}}_{{\mathbf{H}}}$ above, we see that
there exists some $(m-1)$-qubit logical Clifford
$\overline{{\mathbf{G}}}^{\prime}$ such that
$\overline{{\mathbf{G}}}^{\prime}\,\overline{{\mathbf{C}}}_{{\mathbf{H}}}$ is
supported on a MCS (of size $2^{m-1}$). Note that a logical Clifford operation
is defined by its action on logical Paulis.

Let this MCS be generated by logical $(m-1)$-qubit Paulis
$\overline{{\mathbf{E}}}_{1},\overline{{\mathbf{E}}}_{2},\ldots,\overline{{\mathbf{E}}}_{m-1}$,
and let ${\mathbf{E}}_{1},{\mathbf{E}}_{2},\ldots,{\mathbf{E}}_{m-1}\in
S^{{{\perp_{\rm{s}}}}}$ form their respective physical $m$-qubit realizations
in ${\mathcal{H}}{\mathcal{W}}_{\\!N}$. These realizations are automatically
defined once $2(m-1)$ $m$-qubit Pauli operations are chosen to be the
appropriate physical realizations of the logical $X$ and $Z$ on the $(m-1)$
logical qubits. As
$\overline{{\mathbf{G}}}^{\prime}\,\overline{{\mathbf{C}}}_{{\mathbf{H}}}$ is
supported on $\overline{{\mathbf{E}}}_{i}$’s, it clearly commutes with each
one of them. Hence, by taking ${\mathbf{G}}^{\prime}$ to be an $m$-qubit
Clifford that forms a physical realization of
$\overline{{\mathbf{G}}}^{\prime}$, we see that
${\mathbf{G}}^{\prime}({\mathbf{H}}{\mathbf{C}})$ commutes with each
${\mathbf{E}}_{i}$. Note that, by definition of realizing a logical gate, such
a ${\mathbf{G}}^{\prime}$ must preserve the stabilizer $S$, i.e., commute with
${\mathbf{E}}$, and act on ${\mathbf{E}}_{i}$ as $\overline{{\mathbf{G}}}$
acts on $\overline{{\mathbf{E}}}_{i}$.

Finally, consider the group
$\langle{\mathbf{E}},{\mathbf{E}}_{1},{\mathbf{E}}_{2},\ldots,{\mathbf{E}}_{m-1}\rangle$.
This is clearly a MCS and $({\mathbf{G}}^{\prime}{\mathbf{H}}){\mathbf{C}}$
fixes it pointwise. Therefore, by applying Corollary 22 we see that
${\mathbf{G}}{\mathbf{C}}:=({\mathbf{G}}^{\prime}{\mathbf{H}}){\mathbf{C}}$ is
supported on this MCS. This completes the induction. ∎

Lemma 23 constitutes a crucial property of the third level
${\mathcal{C}}^{(3)}$ of the Clifford hierarchy. This property is of course
exclusive to the third level because we highly rely on the fact that
$\mbox{\rm im}\,\phi_{\mathbf{C}}$ is a subgroup of $\mbox{${\rm
Cliff\\!}$}_{N}$. This in turn enables an induction argument on the number of
qubits, rather than the typical induction arguments on the levels of the
Clifford hierarchy. It is worth mentioning that the “up to Clifford” is indeed
necessary throughout the paper. For instance, with regards to Lemma 23, the
physical Clifford permutation

${\mathbf{G}}=\left[\\!\\!\begin{array}[]{cccc}1&0&0&0\\\ 0&0&0&1\\\
0&1&0&0\\\ 0&0&1&0\end{array}\\!\\!\right]$ (77)

does not fix (commute with) _any_ Pauli matrix. Similarly, one can easily
produce other instances of examples that require the “Clifford correction”.

If ${\mathbf{C}}\in{\mathcal{C}}^{(3)}$ is supported on a MCS $S$ then it
trivially fixes the span of $S$, and therefore ${\mathbf{C}}$ is a generalized
semi-Clifford matrix. The converse is not true since, for instance, even the
$\rm{CNOT}$ gate fixes $Z_{4}$ but obviously is not supported on $Z_{4}$. In
fact, any gate ${\mathbf{G}}_{D}({\mathbf{P}})$ fixes $Z_{N}$ by construction
but is not supported on $Z_{N}$ (see Proposition 9(1)).

######  Corollary 26 ([1, Thm. 1.1]).

Every ${\mathbf{C}}\in{\mathcal{C}}^{(3)}$ is a generalized semi-Clifford
matrix.

###### Proof.

By Theorem 25, there exists a Clifford correction ${\mathbf{G}}$ such that
${\mathbf{G}}{\mathbf{C}}$ is supported on a MCS $S$. Then
${\mathbf{G}}{\mathbf{C}}$ fixes the span of $S$, and ${\mathbf{C}}$ maps the
span of $S$ to the span of ${\mathbf{G}}^{\dagger}S{\mathbf{G}}$. Thus
${\mathbf{C}}$ is generalized semi-Clifford. ∎

##  6 Conclusions and Future Research

In this paper we study the Clifford hierarchy via the Pauli/Weyl
expansion/support. First, we consider the Clifford group, that is, the second
level of the hierarchy. We show that every element of the group is supported
on a subgroup of the Pauli group (or a coset, when traceless). Additionally,
we give a closed form description of the support of standard group elements,
and show that the coefficients are determined by a quadratic form modulo 4. We
argue that the Hermitian elements of the group play a prominent role on
understanding the third level of the hierarchy. For this reason, we treat them
separately, and among other things, we show that they are supported on a
_commutative_ subgroup of the Pauli group (or a coset). Next, we consider the
third level of the hierarchy. Our treatment is up to Clifford equivalence,
which, at any rate, preservers the levels of the hierarchy. We show that, up
to such equivalence, every third level matrix commutes with at least one Pauli
matrix. This constitutes the main building block of a powerful induction
argument on the number of qubits, which we use to prove that every third level
matrix, up to Clifford equivalence, is supported on a maximal commutative
subgroup of the Pauli group. We believe that such induction argument can be
further exploited in various aspects of quantum computation and quantum error-
correction.

In future research, we will consider the behaviour of the support under
elementary transformations such as multiplication and conjugation (which,
surprisingly, is unknown). This, among other things, would give a closed form
description of the support of _any_ Clifford group element. Next, with the
ultimate goal of completely characterizing the third level of the hierarchy,
we will consider the converse. That is, finding sufficient conditions under
which a unitary ${\mathbf{U}}$, supported on some MCS, belongs to the third
level. We expect the coefficients to be (scaled) eighth roots of unity that
are perhaps determined by third-order Reed-Muller codes. Finally, we will use
the structural results of this paper to develop flag gadgets for third level
operators, as well as reduce circuit complexity for these operators.

## Acknowledgements

The work of TP and OT was supported in part by the Academy of Finland under
the grant 334539. The work of NR and RC was supported in part by NSF under the
grant CCF1908730. TP and OT thank Robert Calderbank for his hospitality during
visits to Duke University.

## References

  * Beigi and Shor [2010] Salman Beigi and Peter W. Shor.  $\mathcal{C}_{3}$, semi-Clifford and generalized semi-Clifford operations.  _Quantum Info. Comput._ , 10(1):41–59, January 2010.  URL http://arxiv.org/abs/0810.5108.
  * Boykin et al. [1999] P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan.  On universal and fault-tolerant quantum computing: A novel basis and a new constructive proof of universality for Shor’s basis.  page 486, USA, 1999. IEEE Computer Society.  doi: https://doi.org/10.1109/SFFCS.1999.814621.
  * Bravyi and Haah [2012] Sergey Bravyi and Jeongwan Haah.  Magic-state distillation with low overhead.  _Phys. Rev. A_ , 86(5):052329, 2012.  doi: https://doi.org/10.1103/PhysRevA.86.052329.
  * Bravyi and Kitaev [2005] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal Clifford gates and noisy ancillas.  _Phys. Rev. A_ , 71:022316, Feb 2005.  doi: https://doi.org/10.1103/PhysRevA.71.022316.
  * [5] Robert A. Calderbank, Stephen Howard, Sina Jafarpour, and Jeremy Kent.  Sparse approximation and compressed sensing using the Reed-Muller sieve.  _Technical Report, Princeton University, TR-888-10, 2010_.  URL https://www.cs.princeton.edu/research/techreps/TR-888-10.
  * Calderbank et al. [1997] Robert A. Calderbank, Peter J. Cameron, William M. Kantor, and Jaap J. Seidel.  $\mathbb{Z}_{4}$-Kerdock codes, orthogonal spreads, and extremal Euclidean line-sets.  _Proceedings of the London Mathematical Society_ , 75(2):436–480, 1997.  doi: https://doi.org/10.1112/S0024611597000403.
  * Calderbank et al. [1998] Robert A. Calderbank, Eric M. Rains, Peter W. Shor, and Neil J. A. Sloane.  Quantum error correction via codes over ${\rm GF}(4)$.  _IEEE Trans. Inform. Theory_ , 44(4):1369–1387, 1998.  doi: https://doi.org/10.1109/18.681315.
  * Calderbank et al. [2010] Robert A. Calderbank, Stephen Howard, and Sina Jafarpour.  Construction of a large class of matrices satisfying a statistical isometry property.  In _IEEE Journal of Selected Topics in Signal Processing, Special Issue on Compressive Sensing_ , volume 4, pages 358–374, 2010.  doi: https://doi.org/10.1109/JSTSP.2010.2043161.
  * Callan [1976] David Callan.  The generation of $\mbox{\rm Sp}({\mathbb{F}}_{2})$ by transvections.  _J. Algebra_ , 42(2):378–390, 1976.  doi: https://doi.org/10.1016/0021-8693(76)90105-8.
  * Chamberland and Beverland [2018] Christopher Chamberland and Michael E. Beverland.  Flag fault-tolerant error correction with arbitrary distance codes.  _Quantum_ , 2:53, 2018.  doi: https://doi.org/10.22331/q-2019-05-20-143.
  * Chao and Reichardt [2018a] Rui Chao and Ben W Reichardt.  Quantum Error Correction with Only Two Extra Qubits.  _Phys. Rev. Lett._ , 121(5):050502, 2018a.  doi: https://doi.org/10.1103/PhysRevLett.121.050502.
  * Chao and Reichardt [2018b] Rui Chao and Ben W Reichardt.  Fault-tolerant quantum computation with few qubits.  _npj Quantum Inf._ , 4(1):42, 2018b.  doi: https://doi.org/10.1038/s41534-018-0085-z.
  * Chao and Reichardt [2020] Rui Chao and Ben W. Reichardt.  Flag fault-tolerant error correction for any stabilizer code.  _PRX Quantum_ , 1:010302, Sep 2020.  doi: https://doi.org/10.1103/PRXQuantum.1.010302.
  * Cui et al. [2017] Shawn X. Cui, Daniel Gottesman, and Anirudh Krishna.  Diagonal gates in the Clifford hierarchy.  _Phys. Rev. A_ , 95:012329, Jan 2017.  doi: https://doi.org/10.1103/PhysRevA.95.012329.
  * Gibbons et al. [2004] Kathleen S. Gibbons, Matthew J. Hoffman, and William K. Wootters.  Discrete phase space based on finite fields.  _Phys. Rev. A_ , 70:062101, Dec 2004.  doi: https://doi.org/10.1103/PhysRevA.70.062101.
  * Gottesman [1997] Daniel Gottesman.  Stabilizer codes and quantum error correction.  _PhD thesis, California Institute of Technology_ , 1997.  doi: https://doi.org/10.7907/rzr7-dt72.
  * Gottesman and Chuang [1999] Daniel Gottesman and Isaac L. Chuang.  Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.  _Nature_ , 402(6760):390–393, 1999.  doi: https://doi.org/10.1038/46503.
  * Gross [2006] David Gross.  Hudson’s theorem for finite-dimensional quantum systems.  _Journal of Mathematical Physics_ , 47(12):122107, 2006.  doi: https://doi.org/10.1063/1.2393152.
  * Gross and den Nest [2007] David Gross and Maarten Van den Nest.  The LU-LC conjecture, diagonal local operations and quadratic forms over GF(2).  _Quantum Inf. Comput._ , 8(3-4):263–281, 2007\.  URL http://arxiv.org/abs/0707.4000.
  * Koenig and Smolin [2014] Robert Koenig and John A. Smolin.  How to efficiently select an arbitrary Clifford group element.  _J. Math. Phys._ , 55(12):122202, Dec 2014.  doi: https://doi.org/10.1063/1.4903507.
  * MacWilliams and Sloane [1977] Florence J. MacWilliams and Neil J. A. Sloane.  _The theory of error-correcting codes_ , volume 16.  Elsevier, 1977.
  * Maslov and Roetteler [2018] Dmitri Maslov and Martin Roetteler.  Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations.  _IEEE Transactions on Information Theory_ , 64(7):4729–4738, 2018.  doi: https://doi.org/10.1109/TIT.2018.2825602.
  * Nielsen and Chuang [2000] Michael A. Nielsen and Isaac L. Chuang.  _Quantum computation and quantum information_.  Cambridge University Press, Cambridge, 2000.
  * O’Meara [1978] Onorato T. O’Meara.  _Symplectic groups_ , volume 16 of _Mathematical Surveys_.  American Mathematical Society, Providence, R.I., 1978.
  * Pllaha et al. [2020] Tefjol Pllaha, Olav Tirkkonen, and Robert A. Calderbank.  Reconstruction of multi-user binary subspace chirps.  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , pages 531–536, 2020.  doi: https://doi.org/10.1109/ISIT44484.2020.9174412.
  * Rengaswamy et al. [2018] Narayanan Rengaswamy, Robert A. Calderbank, Henry D. Pfister, and Swanand Kadhe.  Synthesis of logical Clifford operators via symplectic geometry.  In _2018 IEEE International Symposium on Information Theory (ISIT)_ , pages 791–795, 2018.  doi: https://doi.org/10.1109/ISIT.2018.8437652.
  * Rengaswamy et al. [2019a] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister.  On Optimality of CSS Codes for Transversal $T$.  _arXiv preprint arXiv:1910.09333_ , 2019a.  URL http://arxiv.org/abs/1910.09333.
  * Rengaswamy et al. [2019b] Narayanan Rengaswamy, Robert Calderbank, and Henry D. Pfister.  Unifying the Clifford hierarchy via symmetric matrices over rings.  _Phys. Rev. A_ , 100(2):022304, 2019b.  doi: https://doi.org/10.1103/PhysRevA.100.022304.
  * Rengaswamy et al. [2020] Narayanan Rengaswamy, Robert Calderbank, Michael Newman, and Henry D. Pfister.  Classical coding problem from transversal t gates.  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , pages 1891–1896, 2020.  doi: https://doi.org/10.1109/ISIT44484.2020.9174408.
  * Tansuwannont et al. [2020] Theerapat Tansuwannont, Christopher Chamberland, and Debbie Leung.  Flag fault-tolerant error correction, measurement, and quantum computation for cyclic Calderbank-Shor-Steane codes.  _Phys. Rev. A_ , 101(1):012342, 2020.  doi: https://doi.org/10.1103/PhysRevA.101.012342.
  * Veitch et al. [2014] Victor Veitch, S A Hamed Mousavian, Daniel Gottesman, and Joseph Emerson.  The resource theory of stabilizer quantum computation.  _New Journal of Physics_ , 16(1):013009, jan 2014\.  doi: https://doi.org/10.1088/1367-2630/16/1/013009.
  * Wigner [1932] Eugene Wigner.  On the quantum correction for thermodynamic equilibrium.  _Phys. Rev._ , 40:749–759, Jun 1932.  doi: https://doi.org/10.1103/PhysRev.40.749.
  * Wootters [2004] William K. Wootters.  Picturing qubits in phase space.  _IBM Journal of Research and Development_ , 48(1):99–110, 2004.  doi: https://doi.org/10.1147/rd.481.0099.
  * Zeng [2009] Bei Zeng.  Quantum operations and codes beyond the Stabilizer-Clifford framework.  _PhD thesis, Massachusetts Institute of Technology_ , 2009.  URL http://hdl.handle.net/1721.1/53235.
  * Zeng et al. [2008] Bei Zeng, Xie Chen, and Isaac L. Chuang.  Semi-Clifford operations, structure of $\mathcal{C}_{k}$ hierarchy, and gate complexity for fault-tolerant quantum computation.  _Phys. Rev. A_ , 77:042313, Apr 2008.  doi: https://doi.org/10.1103/PhysRevA.77.042313.
  * Zhou et al. [2000] Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang.  Methodology for quantum logic gate construction.  _Phys. Rev. A_ , 62:052316, Oct 2000.  doi: 10.1103/PhysRevA.62.052316.