# The Classification of Stabilizer Operations over Qubits

Daniel Grier MIT. Email<EMAIL_ADDRESS>Supported by an NSF Graduate Research
Fellowship under Grant No. 1122374. Luke Schaeffer MIT. Email<EMAIL_ADDRESS>
###### Abstract

We present a complete classification of quantum stabilizer gates in terms of
the functions they generate assuming the ability to swap qubits and use
ancillary workspace. Because we view these stabilizer circuits as subroutines
of some general quantum computation, we insist that any ancilla qubits used
during the computation must not change in an input-dependent manner. This is
the first attempt at a quantum extension of the classification of reversible
classical gates introduced by Aaronson et al., another part of an ambitious
program to classify all quantum gate sets.

The classification uses, at its center, a reinterpretation of the tableau
representation of stabilizer gates to give circuit decompositions, from which
elementary generators can easily be extracted. There are a total of 57
different stabilizer classes generated in this way, 30 of which arise from the
single-qubit subgroups of the Clifford group. At a high level, the remaining
classes are arranged according to the bases they preserve. For instance, the
CNOT gate preserves the $X$ and $Z$ bases because it maps $X$-basis elements
to $X$-basis elements and $Z$-basis elements to $Z$-basis elements. The
remaining classes are characterized by more subtle tableau invariants; for
instance, the $\operatorname{T_{4}}$ and phase gate generate a proper subclass
of $Z$-preserving gates.

##  1 Introduction

A common thread through much of quantum computing and indeed through
computation in general is the manner in which a few elementary gates often
suffice for universal computation. Indeed, this “pervasiveness of
universality” as described in recent work of Aaronson, Grier, and Schaeffer
[3] helps to explain why a random gate on $n$ qubits suffices for universal
quantum computation. In that work, the authors give a complete classification
of _classical_ reversible gates in terms of the functions over bits they
generate. Indeed, they find that even when they restrict themselves to
classical gates, a rich structure emerges.

Of course, the ultimate goal would be a complete classification of _quantum_
gate sets based on the functions over qubits they generate. Unfortunately, the
extraordinary difficulty of this problem given the current state of
mathematics renders such a task nearly impossible. Not even a full
classification of the subgroups of a three-qubit system is known!111The
difficulty in classifying the subgroups of $\mathrm{SU}(N)$ arises not from
the infinite classes but from the finite ones. In fact, even the finite
subgroups of $\mathrm{SU}(5)$ remain unclassified. This motivates our focus on
finite, discrete classes such as the stabilizer group. This might be
surprising given how well we understand random instances and even gate sets
that contain particular gates such as CNOT [6, 19]. However, a full
classification begets a complete understanding of _all_ possible behaviors,
despite their strangeness or rarity (see, for example, the sporadic gate sets
in the lattice of Aaronson et al. [3]). Nevertheless, there has been some
recent and encouraging progress on _some_ classification problems, in
particular, on classifying Hamiltonians (which can be applied for any period
of time), rather than discrete gate sets. For instance, Bouland, Manc̆inska,
and Zhang [7] recently classified all 2-qubit commuting Hamiltonians while
Childs et al. [9] characterized all 2-qubit Hamiltonians when restricted to
circuits over two qubits. Additionally, Aaronson and Bouland [1] completed a
classification for linear optics of $2$-mode beamsplitters, which relied
heavily on the characterization [15] of the finite subgroups of
$\mathrm{SU}(3)$, underscoring the difficulty of quantum gate classification.

This paper contributes its own classification of quantum gate sets by giving a
complete classification of the so-called stabilizer gates, where we allow the
swapping of qubits and the use of ancillary workspace. To provide some
context, stabilizer gates222These gates are often called Clifford operations
in the literature due to their alternative characterization as normalizers of
the Pauli group. are a discrete set of gates generated by the CNOT gate, the
Hadamard gate, and the $\frac{\pi}{4}$-phase gate. Stabilizer circuits are
somewhat remarkable in that they may in fact be integral to our eventual
development of a _general-purpose_ quantum computer. Since quantum error
correction will likely play a large role in determining when a quantum
computer will be viable, there has been considerable research in building and
analyzing quantum error correcting codes. The stabilizer formalism arose as
powerful way of unifying the analyses of many of these codes [12], and as a
consequence, understanding the nature of the stabilizer states has been of
particular interest [11, 17].

Our model is motivated by these interests. That is, we view the application of
a stabilizer circuit as the subroutine of a general quantum computation. In
fact, the stabilizer operations are exactly those operations which can be
easily computed transversally in many fault-tolerant schemes of quantum
computing (e.g., the Shor code [20] or the [[7,1,3]] Steane code [21]). For
this reason, we insist that any ancillary qubits used during the computation
return to their initial state by the end of the computation so that the
delicate quantum coherence of the protocol is not broken. The ancilla states
of our model are very similar to the “reusable magic states” of Anderson [5].
In fact, our classification closes many of the open problems left by that
paper. Nevertheless, we regard the classification of stabilizer gates as an
interesting mathematical problem in its own right, as it exposes many of the
beautiful symmetries inherent in the subgroups of the stabilizer operations.

Because the stabilizer operations on $n$ qubits only generate a discrete,
finite set, it has always been widely assumed that they do not suffice for
universal quantum computation. Nevertheless, stabilizer gates drew attention
when Gottesman and Knill [13] showed that they could be efficiently simulated
with a classical computer. This result was surprising to many because
entanglement was traditionally thought of as a barrier to classical
simulation.

This result was subsequently improved by Aaronson and Gottesman [2], who
showed that stabilizer gates have surprisingly little computational power.
First notice that the stabilizer gates can be seen as a generalization of the
affine reversible gates [3]; $\operatorname{CNOT}$ and $\operatorname{NOT}$
are stabilizer gates, and hence all affine reversible gates are stabilizer
gates. What Aaronson and Gottesman realized is that this is not just a good
intuition for the stabilizer gates, but that stabilizer circuits are complete
for the class $\oplus\mathsf{L}$ (or _parity- $\mathsf{L}$_), for which the
complete problem is the solution of a linear system over $\mathbb{F}_{2}$.
Indeed, $\oplus\mathsf{L}$ is widely regarded to be weaker than all of
polynomial time computation. In that work, Aaronson and Gottesman proposed the
_tableau representation_ of a stabilizer gate, which we reinterpret to serve
as one of the principal components of our classification theorem. See Section
4 for those details.

###  1.1 Results

We present a full inclusion lattice of the 57 different classes of stabilizer
gates. Refer to Figure 4 for a diagram of the 30 single-qubit classes and
Figure 5 for the remaining lattice of multi-qubit gates. Notation for the
generators of the classes depicted in those diagrams is given in Section 3. We
list some highlights of the classification below:

  1. (1)

Conserved Quantities. The invariants that dictate the structure of the lattice
are most easily described by appealing to the tableau representation of a
stabilizer circuit (see Section 4). Nevertheless, there are some common themes
that persist throughout classification. One major theme is that of basis
preservation. We say that a gate “preserves” a basis if it acts as an
automorphism on the elements of that basis. For instance, the CNOT gate
preserves the $X$ and $Z$ bases, but not the $Y$ basis. There are classes
which correspond to all 8 possible ways to preserve the $X$, $Y$, and $Z$
bases. There are also classes in which each entangling operation only changes
the sign of a certain basis, such as the CSIGN gate, or classes in which each
entangling operation acts like an orthogonal transformation over the
computational basis states, such as the $\operatorname{T_{4}}$ gate (see
Section 3.2). Finally, a class can be constrained by its ability to rotate a
single qubit. See Section 6 for a more formal exposition.

  2. (2)

Finite Generation. Every class can be generated by a single gate on at most
four qubits. In fact, given a set of gates generating some class, there always
exist three gates from that set that generate the same class. Moreover, the
classification implies that the canonical set of stabilizer generators—CNOT,
Hadamard, and phase—is _not_ a minimal set of generators in our model. Indeed,
it turns out that with the aid of ancilla qubits, CNOT and Hadamard generate a
phase gate. This is well-known [4, 16], but comes as a simple consequence of
our classification theorem.

  3. (3)

Ancillas. More generally, giving a stabilizer gate access to ancillary qubits
often increases the sorts of functions it can compute. A priori, one might
suspect that extracting all functionality from a large entangling stabilizer
gate would require large highly-entangled ancilla states. Nevertheless, our
classification shows that only a constant number of one and two-qubit
ancillary states are ever needed. In fact, an even stronger result is true.
Namely, our classification holds even when we allow the ancillas to change in
an input-independent manner,333Aaronson et al. called this the “Loose Ancilla
Rule,” and it _does_ affect their classification of classical reversible
circuits. as would be natural for a stabilizer subroutine applied
unconditionally in a quantum circuit. See Section 5 for further discussion.

  4. (4)

Algorithms. Our classification implies a linear time algorithm which, given
the tableau of a gate $G$, decides which class $G$ belongs to. As a
consequence, we can identify the class for a list of tableaux (by running the
algorithm for each one, then looking up the least upper bound on our lattice
diagram), or determine whether one gate generates another (by running the
algorithm for both, and checking whether the one class contains the other). In
fact, to witness that $G$ generates some class $\mathcal{C}$ (or higher) in
the classification, one only needs to view a constant number of bits of the
tableau. These details are discussed in sections 9 and 10.

  5. (5)

Enumeration. For each class $\mathcal{C}$ and for all $n$, we give explicit
formulas for the number of gates in $\mathcal{C}$ on $n$-qubits. The
enumeration usually leads to efficient canonical forms for circuits in the
various classes. In fact, every class is exponentially smaller than any class
strictly containing it. See Appendix A for details.

  6. (6)

Sporadic Gates. The process of classification unearthed certain strange
classes, which arise from the sometimes complicated interaction of the various
invariants which might have otherwise gone overlooked. For example, there are
four classes containing the $\operatorname{T_{4}}$ gate which _require_ a
generator over at least 4 qubits. Nevertheless, the smallest generator for the
class $\left<\operatorname{T_{4}},\Gamma,\mathcal{P}\right>$ is a gate over
three qubits. We investigate such a gate in Appendix C. Interestingly, there
are no affine gate sets in the classification of classical reversible gates
which admit a generator over three bits and no smaller.

###  1.2 Proof Outline

We can break the proof into a few major steps. First, we introduce the notion
of a stabilizer tableau, a binary matrix representation of the function
computed by a circuit. We then “guess” all the classes in the classification
and designate them by their generators. An examination of the tableaux of the
gates in these classes reveals candidate invariants based on the elements of
those tableaux. We then prove that these candidate invariants are indeed
invariant under the rules of our model. That is to say, if we have two gates
whose tableaux satisfy the invariant, then the tableau of their composition
satisfies the invariant, and so on for all the other ways to build circuits
from gates—tensor products, ancillas, swapping.

At this point, we will have shown that each class has a corresponding
invariant, from which the distinctness of the classes in the lattice is
immediate. That is, for every pair of distinct classes there is a generator of
one that fails to satisfy the invariant of the other. Next, we will show that
this correspondence is bijective; that is, for each tableau invariant there is
a corresponding class whose generators generate all gates satisfying that
tableau invariant. This will have the side effect of producing canonical forms
for most of the classes in the lattice.

The challenge remains then to show that our list of classes is exhaustive.
Suppose we are given some gate set $G$. Clearly, the class generated by $G$ is
contained in some class in the lattice. Let $\mathcal{C}$ be the smallest
class containing all the gates in $G$. The hope is that we can use gates from
$G$ to give explicit circuits for the generators of $\mathcal{C}$. For each
class $\mathcal{S}\subset\mathcal{C}$, there must be some gate $g\in G$ which
is not in $\mathcal{S}$, otherwise $\mathcal{S}$ would be a smaller class
containing $G$.

The next step of the proof is to focus on some particular gate $g$, which has
failed to satisfy the invariant of $S$. The key now is the fact that from $g$
we can extract a small generator that _also_ fails to satisfy the invariant of
$S$. This is accomplished via the “universal construction” of the gate $g$,
which is a particular circuit built from $g$ and SWAP gates from which these
small generators can easily be extracted. Finally, we show that these
generators, one for each class $\mathcal{S}$ suffice to generate the class
$\mathcal{C}$ itself.

##  2 Stabilizer Formalism

The one-qubit unitary operations

$\displaystyle X$ $\displaystyle=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$
$\displaystyle Y$ $\displaystyle=\begin{pmatrix}0&-i\\\ i&0\end{pmatrix}$
$\displaystyle Z$ $\displaystyle=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$

are known as _Pauli matrices_. The Pauli matrices are all involutions
($X^{2}=Y^{2}=Z^{2}=I$), and have the following relations between them

$\displaystyle XY$ $\displaystyle=iZ$ $\displaystyle YZ$ $\displaystyle=iX$
$\displaystyle ZX$ $\displaystyle=iY$ $\displaystyle YX$ $\displaystyle=-iZ$
$\displaystyle ZY$ $\displaystyle=-iX$ $\displaystyle XZ$ $\displaystyle=-iY.$

It follows that the Pauli matrices generate a discrete group (under
multiplication), called the _Pauli group_ $\mathcal{P}$, which consists of
sixteen elements: $\\{I,X,Y,Z\\}$ with phases $\pm 1$ or $\pm i$. Then the
_Pauli group on $n$ qubits_, $\mathcal{P}_{n}$, is the set of all $n$-qubit
tensor products of elements from $\mathcal{P}$. We define a _Pauli string_ as
any element of $\mathcal{P}_{n}$ with positive phase (i.e., a tensor product
of the matrices $I,X,Y,Z$). We frequently omit the tensor product symbol from
Pauli strings and write, e.g., $P_{1}\cdots P_{n}$ where we mean
$P_{1}\otimes\cdots\otimes P_{n}$.

The _Clifford group on $n$ qubits_, $\mathcal{C}_{n}$, is the set of unitary
operations which _normalize_ $\mathcal{P}_{n}$ in the group-theoretic sense.
That is, $U\in\mathcal{C}_{n}$ if $UpU^{\dagger}\in\mathcal{P}_{n}$ for all
$p\in\mathcal{P}_{n}$. We leave it as a simple exercise to check that
$\mathcal{C}_{n}$ is indeed a group.

A _stabilizer gate_ is any unitary in $\bigcup_{n\geq 1}\mathcal{C}_{n}$. A
_stabilizer circuit_ is a quantum circuit of stabilizer gates implementing a
unitary transformation on some set of qubits, designated the _input/output
qubits_ , while preserving the state of the remaining _ancilla qubits_. We say
that a state ${\left|{\psi}\right\rangle}$ is _stabilized_ by an operation $U$
iff $U{\left|{\psi}\right\rangle}={\left|{\psi}\right\rangle}$. In other
words, ${\left|{\psi}\right\rangle}$ is in the $+1$ eigenspace of $U$. The
Pauli elements and their corresponding stabilized states are below:

${X}:{\left|{+}\right\rangle}=\frac{{\left|{0}\right\rangle}+{\left|{1}\right\rangle}}{\sqrt{2}}$ | $-{X}:{\left|{-}\right\rangle}=\frac{{\left|{0}\right\rangle}-{\left|{1}\right\rangle}}{\sqrt{2}}$
---|---
${Y}:{\left|{i}\right\rangle}=\frac{{\left|{0}\right\rangle}+i{\left|{1}\right\rangle}}{\sqrt{2}}$ | $-{Y}:{\left|{-i}\right\rangle}=\frac{{\left|{0}\right\rangle}-i{\left|{1}\right\rangle}}{\sqrt{2}}$
${Z}:{\left|{0}\right\rangle}$ | $-{Z}:{\left|{1}\right\rangle}$

We call the vectors stabilized by non-identity Pauli elements $P$ and $-P$ the
_$P$ -basis_. A _stabilizer state_ is any state $U{\left|{0\ldots
0}\right\rangle}$ where $U$ is a stabilizer circuit. For example,
${\left|{0}\right\rangle}$, ${\left|{1}\right\rangle}$,
${\left|{+}\right\rangle}$, ${\left|{-}\right\rangle}$,
${\left|{i}\right\rangle}$, and ${\left|{-i}\right\rangle}$ are the 6
stabilizer states on one qubit. Multi-qubit stabilizer states include
$\frac{1}{n}({\left|{0^{n}}\right\rangle}+{\left|{1^{n}}\right\rangle})$ and
$\sum_{x\in\\{0,1\\}^{n}}{\left|{x}\right\rangle}$. In general, stabilizer
states are of the form (unnormalized) $\sum_{x\in
A}(-1)^{q(x)}i^{\ell(x)}{\left|{x}\right\rangle}$ where $A$ is an affine space
over $\mathbb{F}_{2}$, $q(x)$ is a quadratic form, and $\ell(x)$ is a linear
form [11, 17].

##  3 Gates

Let us introduce some common stabilizer gates. We start with the single-qubit
stabilizer gates, which happen to correspond to symmetries of cube (see Figure
1) or octahedron.

###  3.1 Single-qubit Gates

Face rotations:

The Pauli matrices $X$, $Y$, and $Z$ (as gates) correspond to $180^{\circ}$
rotations about the $X$, $Y$, and $Z$ axes respectively. Similarly, we define
$\operatorname{R}_{X}$, $\operatorname{R}_{Y}$, and $\operatorname{R}_{Z}$ to
be $90^{\circ}$ rotations (in the counterclockwise direction) about their
respective axes. Formally,

$\displaystyle\operatorname{R}_{X}$ $\displaystyle=\frac{I-iX}{\sqrt{2}},$
$\displaystyle\operatorname{R}_{Y}$ $\displaystyle=\frac{I-iY}{\sqrt{2}},$
$\displaystyle\operatorname{R}_{Z}$ $\displaystyle=\frac{I-iZ}{\sqrt{2}},$

although in the case of $\operatorname{R}_{Z}$ (also known as the _phase gate_
and often denoted by $S$ or $P$), a different choice of phase is more
conventional. The clockwise rotations are then
$\operatorname{R}_{X}^{\dagger}$, $\operatorname{R}_{Y}^{\dagger}$ and
$\operatorname{R}_{Z}^{\dagger}$.

Edge rotations:

Another symmetry of the cube is to rotate one of the edges $180^{\circ}$.
Opposing edges produce the same rotation, so we have six gates:
$\theta_{X+Y}$, $\theta_{X-Y}$, $\theta_{X+Z}$, $\theta_{X-Z}$,
$\theta_{Y+Z}$, $\theta_{Y-Z}$. We define

$\displaystyle\theta_{P+Q}$ $\displaystyle=\frac{P+Q}{\sqrt{2}},$
$\displaystyle\theta_{P-Q}$ $\displaystyle=\frac{P-Q}{\sqrt{2}},$

for all Pauli matrices $P\neq Q$. Note that $\theta_{X+Z}$ is the well-known
_Hadamard gate_ , usually denoted by $H$.

Vertex rotations:

The final symmetry is a $120^{\circ}$ counterclockwise rotation around one of
the diagonals passing through opposite vertices of the cube. The cube has
eight vertices, $(\pm 1,\pm 1,\pm 1)$, and we denote the corresponding single-
qubit gates $\Gamma_{+++}$, $\Gamma_{++-}$, $\ldots$, $\Gamma_{---}$.
Algebraically, we define

$\displaystyle\Gamma_{+++}$ $\displaystyle=\frac{I-iX-iY-iZ}{2},$
$\displaystyle\Gamma_{++-}$ $\displaystyle=\frac{I-iX-iY+iZ}{2},$
$\displaystyle\vdots$ $\displaystyle\Gamma_{---}$
$\displaystyle=\frac{I+iX+iY+iZ}{2}.$

We also define $\Gamma$ (without subscripts) to be the first gate,
$\Gamma_{+++}$, since it is the most convenient; conjugation by $\Gamma$ maps
$X$ to $Y$, $Y$ to $Z$, and $Z$ to $X$.

$\operatorname{R}_{X}$$\operatorname{R}_{Y}$$\operatorname{R}_{Z}$$\Gamma_{+++}$$\Gamma_{+-+}$$\Gamma_{-++}$$\Gamma_{--+}$$\Gamma_{++-}$$\Gamma_{+--}$$\Gamma_{-+-}$$\Gamma_{---}$$\theta_{X+Y}$$\theta_{X-Y}$$\theta_{X+Z}$$\theta_{X-Z}$$\theta_{Y+Z}$$\theta_{Y-Z}$ Figure 1: Single-qubit gates as symmetries of the cube Gate | Tableau | Unitary Matrix
---|---|---
$X$ | $\left(\begin{array}[]{cc|c}1&0&0\\\ 0&1&1\end{array}\right)$ | $\left(\begin{array}[]{cc}0&1\\\ 1&0\end{array}\right)$
$Y$ | $\left(\begin{array}[]{cc|c}1&0&1\\\ 0&1&1\end{array}\right)$ | $\left(\begin{array}[]{cc}0&-i\\\ i&0\end{array}\right)$
$Z$ | $\left(\begin{array}[]{cc|c}1&0&1\\\ 0&1&0\end{array}\right)$ | $\left(\begin{array}[]{cc}1&0\\\ 0&-1\end{array}\right)$
$\operatorname{R}_{X}$ | $\left(\begin{array}[]{cc|c}1&0&0\\\ 1&1&1\end{array}\right)$ | $\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&-i\\\ -i&1\\\ \end{array}\right)$
$\operatorname{R}_{Y}$ | $\left(\begin{array}[]{cc|c}0&1&1\\\ 1&0&0\end{array}\right)$ | $\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&-1\\\ 1&1\\\ \end{array}\right)$
$\operatorname{R}_{Z}=S$ | $\left(\begin{array}[]{cc|c}1&1&0\\\ 0&1&0\end{array}\right)$ | $\frac{1-i}{\sqrt{2}}\left(\begin{array}[]{cc}1&0\\\ 0&i\end{array}\right)$
$\theta_{XZ}=\theta_{X+Z}=H$ | $\left(\begin{array}[]{cc|c}0&1&0\\\ 1&0&0\end{array}\right)$ | $\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}1&1\\\ 1&-1\end{array}\right)$
$\theta_{X-Z}$ | $\left(\begin{array}[]{cc|c}0&1&1\\\ 1&0&1\end{array}\right)$ | $\frac{1}{\sqrt{2}}\left(\begin{array}[]{cc}-1&1\\\ 1&1\end{array}\right)$
$\Gamma_{+++}=\Gamma$ | $\left(\begin{array}[]{cc|c}1&1&0\\\ 1&0&0\end{array}\right)$ | $\frac{1-i}{2}\left(\begin{array}[]{cc}1&-i\\\ 1&i\\\ \end{array}\right)$
Table 1: Single-qubit gates

###  3.2 Multi-qubit Gates

We now introduce the multi-qubit stabilizer gates relevant to the
classification. The _SWAP gate_ , for instance, which exchanges two qubits. A
more interesting example is the _controlled-NOT_ or _CNOT gate_ , and the
_generalized CNOT gates_.

A _generalized CNOT gate_ is a two-qubit stabilizer gate of the form

$C(P,Q):=\frac{I\otimes I+P\otimes I+I\otimes Q-P\otimes Q}{2},$

where $P$ and $Q$ are Pauli matrices. If the first qubit is in the $+1$
eigenspace of $P$ then $C(P,Q)$ does nothing, but if it is in the $-1$
eigenspace of $P$ then $C(P,Q)$ applies $Q$ to the second qubit. Of course,
the definition is completely symmetric, so you can also view it as applying
$P$ to the first qubit when the second qubit is in the $-1$ eigenspace of $Q$.

Observe that $C(Z,X)$ is actually the $\operatorname{CNOT}$ gate; it applies a
$\operatorname{NOT}$ gate to the second qubit when the first qubit is
${\left|{1}\right\rangle}$ and does nothing when the first qubit is
${\left|{0}\right\rangle}$. Figure 2 shows this equivalence, and illustrates
our circuit diagram notation for generalized CNOT gates. Also note that
$C(X,Z)$ is a $\operatorname{CNOT}$, but with the opposite orientation (i.e.,
the second bit controls the first). The rest of the _heterogeneous generalized
CNOT gates_ (i.e., $C(P,Q)$ where $P\neq Q$) are the natural equivalents of
$\operatorname{CNOT}$ in different bases.

$\textstyle{Z}$$\textstyle{X}$=$\textstyle{\bullet}$ Figure 2:
$\operatorname{CNOT}$ expressed as a $C(Z,X)$ gate

Similarly, $C(Z,Z)$ is better known as the _controlled-sign gate_ (denoted
$\operatorname{CSIGN}$), which flips the sign on input
${\left|{11}\right\rangle}$, but does nothing otherwise. The _homogeneous
generalized CNOT gates_ (i.e., $C(P,P)$ for some $P$) are quite different from
heterogeneous CNOT gates. For instance, when one $\operatorname{CNOT}$ targets
the control qubit of another $\operatorname{CNOT}$ then it matters which gate
is applied first. On the other hand, two $\operatorname{CSIGN}$ gates will
always commute, whether or not they have a qubit in common.

It turns out that every two-qubit stabilizer gate is equivalent to some
combination of one qubit stabilizer gates and generalized CNOT gates (see
Appendix D). Most classes of stabilizer gates are of this form, but there are
a handful of classes which require larger generators such as the
$\operatorname{T_{4}}$ gate [3, 14]. For all $k\geq 1$, we define
$\operatorname{T}_{2k}$ as the $2k$-bit classical gate that flips all bits of
the input when the parity of the input is odd and does nothing when the parity
of the input is even. In particular, $\operatorname{T}_{2}$ is the lowly SWAP
gate. Notice that $\operatorname{T}_{2k}$ is an orthogonal linear function of
the input bits. The matrix of the $\operatorname{T_{4}}$ gate (over
$\mathbb{F}_{2}$) is

$\begin{pmatrix}0&1&1&1\\\ 1&0&1&1\\\ 1&1&0&1\\\ 1&1&1&0\end{pmatrix}.$

In the quantum setting, let the $\operatorname{T}_{2k}$ gate simply apply this
transformation to the $Z$ basis vectors.

Gate | Tableau | Unitary Matrix on computational basis
---|---|---
$C(X,X)$ | $\left(\begin{array}[]{cc|cc}1&0&0&0\\\ 0&1&1&0\\\ \hline\cr 0&0&1&0\\\ 1&0&0&1\\\ \end{array}\right)$ | $\frac{1}{2}\left(\begin{array}[]{cccc}1&1&1&-1\\\ 1&1&-1&1\\\ 1&-1&1&1\\\ -1&1&1&1\end{array}\right)$
$C(Y,Y)$ | $\left(\begin{array}[]{cc|cc}1&0&1&1\\\ 0&1&1&1\\\ \hline\cr 1&1&1&0\\\ 1&1&0&1\\\ \end{array}\right)$ | $\frac{1}{2}\left(\begin{array}[]{cccc}1&-i&-i&1\\\ i&1&-1&-i\\\ i&-1&1&-i\\\ 1&i&i&1\\\ \end{array}\right)$
$C(Z,Z)=\operatorname{CSIGN}$ | $\left(\begin{array}[]{cc|cc}1&0&0&1\\\ 0&1&0&0\\\ \hline\cr 0&1&1&0\\\ 0&0&0&1\\\ \end{array}\right)$ | $\left(\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&-1\\\ \end{array}\right)$
$C(Y,X)$ | $\left(\begin{array}[]{cc|cc}1&0&1&0\\\ 0&1&1&0\\\ \hline\cr 0&0&1&0\\\ 1&1&0&1\\\ \end{array}\right)$ | $\frac{1}{2}\left(\begin{array}[]{cccc}1&1&-i&i\\\ 1&1&i&-i\\\ i&-i&1&1\\\ -i&i&1&1\\\ \end{array}\right)$
$C(Z,Y)$ | $\left(\begin{array}[]{cc|cc}1&0&1&1\\\ 0&1&0&0\\\ \hline\cr 0&1&1&0\\\ 0&1&0&1\\\ \end{array}\right)$ | $\left(\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&-i\\\ 0&0&i&0\\\ \end{array}\right)$
$C(X,Z)=\operatorname{CNOT}$ | $\left(\begin{array}[]{cc|cc}1&0&0&0\\\ 0&1&0&1\\\ \hline\cr 1&0&1&0\\\ 0&0&0&1\\\ \end{array}\right)$ | $\left(\begin{array}[]{cccc}1&0&0&0\\\ 0&0&0&1\\\ 0&0&1&0\\\ 0&1&0&0\\\ \end{array}\right)$
Table 2: Two qubit gates. The sign bits are all 0 in the above tableaux so
they are omitted.

##  4 Tableaux

Observe that the matrices $I,X,Y,Z$ are linearly independent, and therefore
form a basis for the $2\times 2$ complex matrices. It follows that
$\mathcal{P}_{n}$ spans all $2^{n}\times 2^{n}$ complex matrices. Hence, any
unitary operation on $n$ qubits can be characterized by its action on
$\mathcal{P}_{n}$. In particular, any gate is characterized by how it acts on

$p_{1}=XI\cdots I,p_{2}=ZI\cdots I,\ldots,p_{2n-1}=I\cdots IX,p_{2n}=I\cdots
IZ.$

We call this list the _Pauli basis on $n$ qubits_, since one can write any
element of $\mathcal{P}_{n}$ as a product of basis elements times a phase
($\pm 1$ or $\pm i$).

Now suppose we are given a stabilizer gate, $U\in\mathcal{C}_{n}$. By
definition, stabilizer gates will map each Pauli basis element to something in
$\mathcal{P}_{n}$, which can be written as a product of basis elements times a
phase. That is,

$Up_{j}U^{\dagger}=\alpha_{j}\prod_{k=1}^{2n}p_{k}^{M_{jk}}$

for some bits $M_{j1},\ldots,M_{j(2n)}\in\\{0,1\\}$ and some phase444Note that
the order of the terms in the product matters, since the Pauli basis elements
do not necessarily commute, so we assume the terms are in the natural order
from $p_{1}^{M_{j1}}$ up to $p_{2n}^{M_{j(2n)}}$. $\alpha_{j}\in\\{\pm 1,\pm
i\\}$. The _tableau_ for $U$ is a succinct representation for $U$ consisting
of the binary matrix $M=[M_{jk}]$, and some representation of the phases
$\alpha_{1},\ldots,\alpha_{2n}$.

It turns out that $U$ maps $p_{j}$ (or any Pauli string) to $\pm 1$ times a
Pauli string, never $\pm i$ times a Pauli string. This follows from the fact
that the square of any Pauli string is $I\cdots I$, so

$(Up_{j}U^{\dagger})^{2}=Up_{j}^{2}U^{\dagger}=U(I\cdots
I)U^{\dagger}=+I\cdots I.$

If the phase in front of the Pauli string in $Up_{j}U^{\dagger}$ were $\pm i$,
then squaring it would produce a negative phase. Therefore,
$Up_{j}U^{\dagger}$ is $\pm 1$ times a Pauli string.

Unfortunately, $\alpha_{j}$ may still be any one of $\\{\pm 1,\pm i\\}$. This
is because the product of $p_{2k-1}p_{2k}$ is $I\cdots I(XZ)I\cdots
I=-iI\cdots IYI\cdots I$, with an awkward $-i$ phase. Once we cancel the extra
factors of $i$ from $\alpha_{j}$, we are left with

$(-1)^{v_{j}}:=\alpha_{j}\prod_{k=1}^{n}(-i)^{M_{j(2k-1)}M_{j(2k)}},$

where $v_{j}\in\\{0,1\\}$ is the _phase bit for row $j$_. For example, if
$Up_{1}U^{\dagger}$ is $YI\cdots I$ then we have $M_{11}=M_{12}=1$ and
$v_{1}=0$. Then the complete tableau for $U$ is the matrix $M=[M_{jk}]$ and
the vector of bits $v=[v_{j}]$, which we typically write as

$\left(\begin{array}[]{ccc|c}M_{11}&\cdots&M_{1(2n)}&v_{1}\\\
\vdots&\ddots&\vdots&\vdots\\\
M_{(2n)1}&\cdots&M_{(2n)(2n)}&v_{2n}\end{array}\right).$

Our ordering of the basis elements (which differs from other presentations)
puts Pauli strings on the same qubit (e.g., $XI\cdots I$ and $ZI\cdots I$)
side-by-side in the matrix, so the $2\times 2$ submatrix

$\begin{pmatrix}M_{2i-1,2j-1}&M_{2i-1,2j}\\\
M_{2i,2j-1}&M_{2i,2j}\end{pmatrix}$

completely describes how the $i$th qubit of the input affects the $j$th qubit
of the output. In fact, it will be fruitful to think of the tableau as an
$n\times n$ matrix of $2\times 2$ blocks, along with a vector of $2n$ _phase
bits_. To be clear, the blocks come from $\mathsf{R}:=\mathbb{F}_{2}^{2\times
2}$, the ring of $2\times 2$ matrices over the field of two elements,
$\mathbb{F}_{2}$. Then the tableau is a matrix in $\mathsf{R}^{n\times n}$
(the $n\times n$ matrices over the ring $\mathsf{R}$), combined with a vector
of phase bits in $\mathbb{F}_{2}^{2n}$. Each row of the matrix is associated
with a pair of phase bits from the vector.

However, not every matrix in $\mathsf{R}^{n\times n}$ corresponds to a
stabilizer circuit due to unitarity constraints. To best express these
constraints, we define a unary operation ∗ on $\mathsf{R}$ such that

$\begin{pmatrix}a&b\\\ c&d\end{pmatrix}^{*}=\begin{pmatrix}d&b\\\
c&a\end{pmatrix}.$

The ∗ operator has the property that

$\begin{pmatrix}a&b\\\ c&d\end{pmatrix}\begin{pmatrix}a&b\\\
c&d\end{pmatrix}^{*}=\begin{pmatrix}a&b\\\
c&d\end{pmatrix}\begin{pmatrix}d&b\\\
c&a\end{pmatrix}=\begin{pmatrix}ad+bc&0\\\
0&ad+bc\end{pmatrix}=I\begin{vmatrix}a&b\\\ c&d\end{vmatrix}.$

Additionally,

$\displaystyle I^{*}$ $\displaystyle=I,$ $\displaystyle(M+N)^{*}$
$\displaystyle=M^{*}+N^{*},$ $\displaystyle(MN)^{*}$
$\displaystyle=N^{*}M^{*},$ $\displaystyle(M^{*})^{*}$ $\displaystyle=M,$

so ∗ makes $\mathsf{R}$ a _∗ -ring_ or _ring with involution_. We also extend
∗ to an operation on matrices (over $\mathsf{R}$) which applies ∗ to each
entry and then transposes the matrix. It turns out that a tableau represents a
unitary operation if and only if the matrix $M\in\mathsf{R}^{n\times n}$
satisfies $MM^{*}=M^{*}M=I$. This (intentionally) resembles the definition of
a unitary matrix ($UU^{\dagger}=U^{\dagger}U=I$), we will call this the
_unitarity condition_ , and it corresponds to the unitarity of $U$ as a gate,
but $M$ is certainly not a traditional complex unitary matrix (nor unitary
over some finite field with conjugation).

###  4.1 Correspondence between Gates and Tableaux

We will find it useful to switch between gates and tableaux, as one notion
often informs the other. In light of that, define $\mathcal{T}(g)$ to be the
tableau of a stabilizer gate $g$. In fact, we will use $\mathcal{M}(g)$ to
denote only the matrix part of the tableau of $g$, as the phase bits of the
tableau often prove to be irrelevant. Indeed, most non-degenerate gate sets
generate the Pauli group, which alone suffices to set the phase bits of the
tableau arbitrarily as follows: applying $X$ to qubit $j$ negates $v_{2j}$ and
applying $Z$ to qubit $j$ negates $v_{2j-1}$. Furthermore, there is a
surprising connection between individual entries of tableaux and elementary
stabilizer operations that can be extracted from them (see Section 9).

If $a\in\mathsf{R}$ is invertible, then let $\mathcal{G}(a)$ be the single-
qubit gate with $\mathcal{M}(\mathcal{G}(a))=a$ and zeros for phase bits.
These are the gates in the first row of Table 3. Let $\mathcal{G}(a,i)$ be the
gate $\mathcal{G}(a)$ applied to the $i$th qubit.

| $(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})$ | $(\begin{smallmatrix}1&0\\\ 1&1\end{smallmatrix})$ | $(\begin{smallmatrix}0&1\\\ 1&0\end{smallmatrix})$ | $(\begin{smallmatrix}1&1\\\ 0&1\end{smallmatrix})$ | $(\begin{smallmatrix}1&1\\\ 1&0\end{smallmatrix})$ | $(\begin{smallmatrix}0&1\\\ 1&1\end{smallmatrix})$
---|---|---|---|---|---|---
$(\begin{smallmatrix}0\\\ 0\end{smallmatrix})$ | $I$ | $\operatorname{R}_{X}^{\dagger}$ | $\theta_{X+Z}$ | $\operatorname{R}_{Z}$ | $\Gamma_{+++}$ | $\Gamma_{---}$
$(\begin{smallmatrix}0\\\ 1\end{smallmatrix})$ | $X$ | $\operatorname{R}_{X}$ | $\operatorname{R}_{Y}^{\dagger}$ | $\theta_{X+Y}$ | $\Gamma_{--+}$ | $\Gamma_{+-+}$
$(\begin{smallmatrix}1\\\ 0\end{smallmatrix})$ | $Z$ | $\theta_{Y+Z}$ | $\operatorname{R}_{Y}$ | $\operatorname{R}_{Z}^{\dagger}$ | $\Gamma_{-+-}$ | $\Gamma_{-++}$
$(\begin{smallmatrix}1\\\ 1\end{smallmatrix})$ | $Y$ | $\theta_{Y-Z}$ | $\theta_{X-Z}$ | $\theta_{X-Y}$ | $\Gamma_{+--}$ | $\Gamma_{++-}$
Table 3: Invertible tableau elements and the corresponding single-qubit gates
produced by the universal construction. Row of the table corresponds to the
sign bit of the row of the tableau in which the element occurs.

If $b\in\mathsf{R}$ is noninvertible, define $\operatorname{CNOT}(b,i,j)$ to
be the generalized CNOT on qubits $i$ and $j$ corresponding to the singular
matrix $b$. These are the gates in the first row of Table 4. The tableau
$\mathcal{T}(\operatorname{CNOT}(b,i,j))$ is the identity tableau except for
$b^{*}$ and $b$ in positions $(i,j)$ and $(j,i)$, respectively. We use the
circuit in Figure 3 to designate such a gate.

Element | $(\begin{smallmatrix}0&0\\\ 1&0\end{smallmatrix})$ | $(\begin{smallmatrix}1&1\\\ 1&1\end{smallmatrix})$ | $(\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix})$ |  $(\begin{smallmatrix}1&0\\\ 0&0\end{smallmatrix})$ / $(\begin{smallmatrix}0&0\\\ 0&1\end{smallmatrix})$ |  $(\begin{smallmatrix}1&0\\\ 1&0\end{smallmatrix})$ / $(\begin{smallmatrix}0&0\\\ 1&1\end{smallmatrix})$ |  $(\begin{smallmatrix}1&1\\\ 0&0\end{smallmatrix})$ / $(\begin{smallmatrix}0&1\\\ 0&1\end{smallmatrix})$
---|---|---|---|---|---|---
Gen. CNOT | $C(X,X)$ | $C(Y,Y)$ | $C(Z,Z)$ | $C(X,Z)$ | $C(Y,X)$ | $C(Z,Y)$
Table 4: Noninvertible tableau elements and the corresponding generalized CNOT
gates produced by the universal construction.

$\textstyle{\;b\;}$$\textstyle{b^{*}}$

Figure 3: Circuit diagram for $\operatorname{CNOT}(b,1,2)$ gate.

Finally, we would like to have a direct way to compose two circuits by a
simple operation on their tableaux. Suppose we wish to compute the composition
of circuits $C_{1}$ and $C_{2}$. To compute $\mathcal{T}(C_{2}\circ C_{1})$,
we must compute, for each Pauli basis element $p_{j}$, the product
$C_{2}C_{1}p_{j}C_{1}^{\dagger}C_{2}^{\dagger}$. First consider the $j$th row
of $\mathcal{T}(C_{1})$, which gives

$C_{1}p_{j}C_{1}^{\dagger}=\alpha_{j}\prod_{k=1}^{2n}p_{k}^{M_{jk}^{(1)}},$

where $M^{(1)}$ is the binary representation of $\mathcal{M}(C_{1})$, and
$\alpha_{j}$ is the phase. Similarly,

$C_{2}p_{j}C_{2}^{\dagger}=\beta_{j}\prod_{k=1}^{2n}p_{k}^{M_{jk}^{(2)}}.$

Therefore,

$\displaystyle C_{2}C_{1}p_{j}C_{1}^{\dagger}C_{2}^{\dagger}$
$\displaystyle=C_{2}\left(\alpha_{j}\prod_{k=1}^{2n}p_{k}^{M_{jk}^{(1)}}\right)C_{2}^{\dagger}=\alpha_{j}\prod_{k=1}^{2n}\left(C_{2}p_{k}^{M_{jk}^{(1)}}C_{2}^{\dagger}\right)=\alpha_{j}\prod_{k=1}^{2n}\left(\beta_{k}\prod_{\ell=1}^{2n}p_{\ell}^{M_{k\ell}^{(2)}}\right)^{M_{jk}^{(1)}}$
$\displaystyle=\alpha_{j}\prod_{k=1}^{2n}\left(\beta_{k}^{M_{jk}^{(1)}}\prod_{\ell=1}^{2n}p_{\ell}^{M_{jk}^{(1)}M_{k\ell}^{(2)}}\right)\propto\prod_{\ell=1}^{2n}\prod_{k=1}^{2n}p_{\ell}^{M_{jk}^{(1)}M_{k\ell}^{(2)}}\propto\prod_{\ell=1}^{2n}p_{\ell}^{\bigoplus_{k=1}^{2n}M_{jk}^{(1)}M_{k\ell}^{(2)}}$
$\displaystyle=\prod_{\ell=1}^{2n}p_{\ell}^{[M^{(1)}M^{(2)}]_{j\ell}}$

Notice that this implies $\mathcal{M}(C_{2}\circ
C_{1})=\mathcal{M}(C_{1})\mathcal{M}(C_{2})$. Since it is cumbersome to write
out explicitly, we did not include the exact phases in the above calculation.
Nevertheless, one can compute the phase bits by tracking the intermediate
steps in the above calculation, which includes the multiplication of Pauli
basis elements.

##  5 Classes

Informally, the class generated by a set of stabilizer gates is the collection
of stabilizer circuits which can be performed with those gates. Our goal is to
determine the set of classes and the relationships between them. We now must
lay out the precise operations we use to build circuits. Composition and
tensor product are obvious, but let us introduce and justify our rules
concerning the reordering of qubits and ancillary workspace.

First, we will always allow the swapping of qubits. This allows us to consider
gates without needing to specify the qubits on which they must be applied.
Indeed, we can relabel the input wires however we like. Secondly, we allow the
use of quantum ancillas, that is, arbitrary states that we can “hardwire” into
the computation. We only stipulate that these ancilla qubits be returned to
their initial configuration at the end of the computation.

These ancilla inputs can be viewed as the workspace of the computation. If we
allow no ancilla inputs at all then, of course, a gate set consisting of gates
over many inputs can’t possibly hope to simulate a gate over a smaller number
of qubits. Furthermore, if we want to apply a stabilizer function as a
subroutine of a general quantum computation (as we would, say, for a fault-
tolerant scheme), then we need that the ancilla states do not depend on the
input. Otherwise, they would destroy the quantum coherence of the computation.

Finally, we turn to the question of the ancillas themselves. The weakest
assumption one could make is that the ancillas are initialized to an unknown
state, which the circuit may only change temporarily. This is somewhat
artificial since we can, at the very least, initialize the workspace to the
all-zeros state. Other classifications suggest that without this assumption
the problem becomes _dramatically_ more difficult (for example, Post’s
infinite lattice collapses to a small finite one [3]). A slightly stronger
assumption would be to allow ancillas initialized to computational basis
states, but this would break symmetry by introducing a bias towards the
$Z$-basis.555We can fix the bias by allowing all single-qubit ancillary
states:
${\left|{0}\right\rangle},{\left|{1}\right\rangle},{\left|{+}\right\rangle},{\left|{-1}\right\rangle},{\left|{i}\right\rangle},{\left|{-i}\right\rangle}$.
This introduces new classes such as
$\left<\theta_{X+Z}\otimes\theta_{X+Z}\right>$, but we leave the
classification under these assumptions as an open problem.

A next natural step would be to permit ancillas initialized to arbitrary
stabilizer states. Although this would appear to be circular (i.e., stabilizer
gates are necessary to implement stabilizer states, which we then use as
ancillas in stabilizer circuits), the reusability of our ancillas implies that
even if the states are difficult to construct, at least we only have to
construct them once. Unfortunately, we are unable to complete the
classification in its entirety under this ancilla model. However, we have
reduced the problem to finding a stabilizer state which is stabilized by
$\Gamma$ and a permutation, and we conjecture that such a state exists (see
Section 11). Moreover, the conjectured classification matches the one we will
present (under a stronger ancilla model).

Finally, we arrive at our chosen model; that is, ancillas initialized to
arbitrary quantum states. A priori, these states could be arbitrarily large,
and arbitrarily complicated to construct, which is clearly undesirable. It
turns out, however, the classification only requires finitely many one or two
qubit states, in particular, the eigenstates of the single-qubit stabilizer
gates and states that are locally equivalent to the Bell state. For
comparison, we have determined the reversible gate lattice under quantum
ancillas in Appendix B, and observe that, in some cases, arbitrarily large,
entangled states are necessary.

It is worth noting that there is a long line of work showing that weak gate
sets, including stabilizer gates, are universal for quantum computation when
given access to magic states [8, 18, 20]. Importantly, magic states do not
need to be preserved after the computation, contrary to our model. Indeed, our
classification shows that arbitrary quantum states cannot boost the power of
stabilizer gates beyond the Clifford group.

One can increase the power of ancillas by letting them change over the course
of the computation, as long as the change is independent of the input (that
is, from some constant initial state to some possibly different constant final
state). Indeed, in the classification of reversible gates [3], these “loose
ancillas” collapse a few pairs of classes. Nevertheless, we show that even
with loose ancillas, our classification (as presented) still holds. When we
formally define class invariants in Section 6 (see Theorem 3 in particular),
we will see that the invariants hold under the loose quantum ancilla model,
and therefore hold for all weaker models.

Now let us formally define a _class_ $\mathcal{C}$ to be a set of stabilizer
gates satisfying the following four rules:

(1.) Composition Rule

$\mathcal{C}$ is closed under composition of gates.

(2.) Tensor Rule

$\mathcal{C}$ is closed under tensor product of gates.

(3.) Swap Rule

$\mathcal{C}$ contains the $\operatorname{SWAP}$ gate.

(4.) Ancilla Rule

$\mathcal{C}$ is closed under ancillas. More precisely, if we have a gate
$g\in\mathcal{C}$ and state ${\left|{\psi}\right\rangle}$, and there exists
$g^{\prime}$ such that
$g({\left|{x}\right\rangle}\otimes{\left|{\psi}\right\rangle})=g^{\prime}({\left|{x}\right\rangle})\otimes{\left|{\psi}\right\rangle}$
for all inputs ${\left|{x}\right\rangle}$ (up to a global phase), then
$g^{\prime}$ is a member of $\mathcal{C}$.

Let’s first see a few simple consequences of the model.

######  Proposition 1.

Let $\mathcal{C}$ be a class of stabilizer gates. Then $\mathcal{C}$ contains
the $n$ qubit identity gate for any $n$.

###### Proof.

First, $\mathcal{C}$ contains $\operatorname{SWAP}$. It follows that
$\mathcal{C}$ contains the two qubit identity gate since it is the composition
$\operatorname{SWAP}\circ\operatorname{SWAP}$. By the ancilla rule, we can
remove a qubit from the two qubit identity using _any_ one-qubit state. Hence,
the one qubit identity gate is in $\mathcal{C}$. Finally, $\mathcal{C}$ must
contain the $n$-qubit identity gate because it is the tensor product of $n$
one-qubit gates. ∎

######  Proposition 2.

Let $\mathcal{C}$ be a class of stabilizer gates. For any $g\in\mathcal{C}$,
the inverse, $g^{-1}$, belongs to $\mathcal{C}$.

###### Proof.

Consider the sequence

$g,g\circ g,g\circ g\circ g,\ldots,g^{n},\ldots.$

Since there are finitely many stabilizer gates on $n$ qubits (certainly
finitely many tableaux, and one gate per tableau), the sequence must
eventually repeat. That is, $g^{i}=g^{j}$ for some $1\leq i<j$. Since every
stabilizer gate has an inverse, we conclude that $1=g^{0}=g^{j-i}$, and hence
$g^{-1}=g^{j-i-1}$. In other words, $g^{-1}$ is a stabilizer gate, and
$g^{-1}$ is a (positive) power of $g$ and therefore in $\mathcal{C}$. ∎

The most practical way to talk about a class $\mathcal{C}$ is by its
_generators_. We say a set of gates $G$ _generates_ a class $\mathcal{C}$ if
$G\subseteq\mathcal{C}$ and every class containing $G$ also contains
$\mathcal{C}$. We introduce the notation $\left<\cdot\right>$ for the class
generated by a set of gates. Similarly, we say that $G$ generates a specific
gate $g$ if $g\in\left<G\right>$.

Our goal is therefore to identify all stabilizer gate classes, determine their
generators, and diagram the relationships between classes. As it turns out,
there are $57$ different classes, which we have split across Figure 4 (which
contains the classes with single-qubit generators) and Figure 5 (which
contains the multi-qubit classes). Each class is labelled by a set of
generators for that class, except for $\mathsf{ALL}$, the class of all
stabilizer gates; $\top$, the class of all single-qubit stabilizer gates; and
$\bot$, the class generated by the empty set. Additionally, we abbreviate some
class names in Figure 4:

  * •

$\theta_{+++}$, $\theta_{+--}$, $\theta_{-+-}$, $\theta_{--+}$ denote the
single-qubit classes containing $\Gamma_{+++}$, $\Gamma_{+--}$,
$\Gamma_{-+-}$, and $\Gamma_{--+}$ respectively, and three $\theta$ gates
each, as indicated by the gray lines.

  * •

$\theta_{xy}$ abbreviates $\theta_{x+y}$ or $\theta_{x-y}$ (it contains both)
and similarly for $\theta_{xz}$ and $\theta_{yz}$.

Some of the lines in Figure 4 are gray and dotted, not for any technical
reason, but because the lattice would be unreadable otherwise.

In Figure 5 each class includes the label of the single-qubit subgroup, even
when not all of the single-qubit generators are necessary to generate the
class. This is intended to make the relationship between the degenerate and
non-degenerate lattices clearer. For example, $\operatorname{T_{4}}$ generates
the Pauli group, $\mathcal{P}$, on its own (Lemma 11), but we label the class
$\left<\operatorname{T_{4}},\mathcal{P}\right>$ to make it clear that the
class $\left<\operatorname{T_{4}}\right>$ is above $\left<\mathcal{P}\right>$
in the lattice.

$\bot$$\top$$X$$Y$$Z$$\operatorname{R}_{X}$$\operatorname{R}_{Y}$$\operatorname{R}_{Z}$$\mathcal{P}+\operatorname{R}_{X}$$\mathcal{P}+\operatorname{R}_{Y}$$\mathcal{P}+\operatorname{R}_{Z}$$\Gamma_{--+}$$\Gamma_{-+-}$$\Gamma_{+--}$$\Gamma_{+++}$$\theta_{Y+Z}$$\theta_{Y-Z}$$\theta_{X+Z}$$\theta_{X-Z}$$\theta_{X+Y}$$\theta_{X-Y}$$\mathcal{P}$$\mathcal{P}+\Gamma$$X+\theta_{YZ}$$Y+\theta_{XZ}$$Z+\theta_{XY}$$\theta_{+++}$$\theta_{+--}$$\theta_{-+-}$$\theta_{--+}$
Figure 4: The inclusion lattice of degenerate stabilizer gate classes

$\operatorname{R}_{Z}$$\mathsf{ALL}$$\operatorname{R}_{Z}$$C(Y,X)+\mathcal{P}+\operatorname{R}_{X}$$C(Z,Y)+\mathcal{P}+\operatorname{R}_{Y}$$C(X,Z)+\mathcal{P}+\operatorname{R}_{Z}$pt$C(X,Z)+\mathcal{P}$$\operatorname{T_{4}}+\mathcal{P}+\operatorname{R}_{X}$$C(Y,X)+\mathcal{P}$$\operatorname{T_{4}}+\mathcal{P}+\operatorname{R}_{Y}$$C(Z,Y)+\mathcal{P}$$\operatorname{T_{4}}+\mathcal{P}+\operatorname{R}_{Z}$$C(X,X)+\mathcal{P}+\operatorname{R}_{X}$$C(Y,Y)+\mathcal{P}+\operatorname{R}_{Y}$$C(Z,Z)+\mathcal{P}+\operatorname{R}_{Z}$pt$C(X,X)+\mathcal{P}$$C(X,X)+\operatorname{R}_{X}$$C(X,X)+X+\theta_{YZ}$$C(Y,Y)+\mathcal{P}$$C(Y,Y)+\operatorname{R}_{Y}$$C(Y,Y)+Y+\theta_{XZ}$$C(Z,Z)+\mathcal{P}$$C(Z,Z)+\operatorname{R}_{Z}$$C(Z,Z)+Z+\theta_{XY}$$C(X,X)+X$$C(Y,Y)+Y$$C(Z,Z)+Z$pt$\operatorname{T_{4}}+\mathcal{P}+\Gamma$pt$\operatorname{T_{4}}+\mathcal{P}$
Figure 5: The inclusion lattice of non-degenerate stabilizer gate classes.
Red, green, blue denote $X$-, $Y$-, and $Z$-preserving, respectively.

##  6 Invariants

Until now, we have defined each class in terms of the generators for that
class. It turns out that each class can also be characterized as the set of
all gates satisfying a collection of invariants. Section 7 formalizes this
equivalence. This section focuses on the form of the invariants themselves.

Informally, an _invariant_ is a property of gates, readily apparent from their
tableaux, which is preserved by the circuit building operations. In other
words, if a collection of gates all satisfy a particular invariant then any
circuit constructed from those gates must also satisfy the invariant. All our
invariants are formally defined from the tableaux, but for now we give the
following informal descriptions to make the intuition for each invariant
clear.

$X$-, $Y$-, or $Z$-preserving:

We say a stabilizer gate is _$Z$ -preserving_ if it maps $Z$-basis states to
$Z$-basis states, possibly with a change of phase. The $Z$-preserving gates
include all (classical) reversible gates (e.g., $X$, $\operatorname{CNOT}$,
and $\operatorname{T_{4}}$), gates which only manipulate the sign (e.g.,
$\operatorname{R}_{Z}$ and $\operatorname{CSIGN}$), and combinations of the
two.

Symmetrically, there are $X$-preserving gates mapping $X$-basis states to
$X$-basis states, and $Y$-preserving gates gates mapping $Y$-basis states to
$Y$-basis states. Our definitions of classes, gates, invariants, etc., are
completely symmetric with respect to $X$, $Y$ and $Z$ basis, so if some gate
or class is $X$-preserving (resp. $Y$-preserving or $Z$-preserving), then
there must be a corresponding gate or class which is $Y$-preserving (resp.
$Z$-preserving or $X$-preserving). We will often appeal to this symmetry to
simplify proofs.

Note that a gate can be any combination of $X$-, $Y$-, and $Z$-preserving. For
instance, $\operatorname{T_{4}}$ is $X$-, $Y$-, and $Z$-preserving;
$\operatorname{CNOT}$ is $X$-preserving and $Z$-preserving but not
$Y$-preserving (similarly $C(X,Y)$ and $C(Y,Z)$ fail to be $Z$-preserving and
$X$-preserving respectively); $\operatorname{R}_{Z}$ is $Z$-preserving only
(similarly $\operatorname{R}_{X}$ is $X$-preserving and $\operatorname{R}_{Y}$
is $Y$-preserving); and $\Gamma$ is not $X$-, $Y$-, or $Z$-preserving.

Egalitarian

We say a gate is _egalitarian_ if it is fixed (up to a Pauli operation on each
qubit) by the aforementioned $X/Y/Z$ symmetry, that is, the symmetry arising
from conjugating all qubits by $\Gamma$ (which cycles $X$ to $Y$, $Y$ to $Z$,
and $Z$ to $X$). In particular, this implies that if egalitarian operation $U$
maps Pauli string $P$ to $Q=UPU^{\dagger}$ under conjugation, then $U$ maps
$\Gamma P\Gamma^{\dagger}$ to

$U\Gamma P\Gamma^{\dagger}U^{\dagger}\propto\Gamma U\Gamma^{\dagger}\Gamma
P\Gamma^{\dagger}\Gamma U^{\dagger}\Gamma^{\dagger}=\Gamma
UPU^{\dagger}\Gamma^{\dagger}=\Gamma Q\Gamma^{\dagger}.$

Not only are $\Gamma$ and the Pauli matrices themselves egalitarian, but so is
$\operatorname{T_{4}}$.

Degenerate:

We say a gate is _degenerate_ if each input affects only one output. More
precisely, when applying the gate to a string of Paulis, changing one Pauli in
the input will change exactly one Pauli in the output. All single-qubit gates
are degenerate, and all degenerate gates can be composed of single-qubit gates
and SWAP gates.

$X$-, $Y$-, or $Z$-degenerate:

A gate is _$Z$ -degenerate_ if it is $Z$-preserving and flipping any bit of a
classical ($Z$-basis) input to the gate causes exactly one bit of the output
to flip. The gate may or may not affect the phase. This class includes several
$Z$-preserving single qubit gates, like $\operatorname{R}_{Z}$, the Pauli
operations, and $\theta_{X+Y}$. It also includes $\operatorname{CSIGN}$
because this gate _only_ affects phase, but $\operatorname{CNOT}$ is not
$Z$-degenerate because flipping the control bit changes both outputs. Notice
that $\operatorname{CSIGN}$ is $Z$-degenerate, but not degenerate. We define
$X$-degenerate and $Y$-degenerate symmetrically.

$X$-, $Y$-, or $Z$-orthogonal:

A gate $G$ is _$Z$ -orthogonal_ if it can be built from $\operatorname{T_{4}}$
and $Z$-preserving single-qubit gates. The term “orthogonal” comes from the
fact that $\operatorname{T_{4}}$ is an orthogonal linear transformation in the
$Z$-basis, but not all $Z$-orthogonal gates are literally orthogonal
transformations in the $Z$-basis (see, for example, Lemma 11). Similarly for
$X$-orthogonal and $Y$-orthogonal.

Single Qubit Gates:

There are thirty different classes of single-qubit gates. All of these classes
are degenerate, and some can be distinguished by the other invariants above.
However, many single-qubit invariants depend on the phase bits of the tableau.
For instance, the tableau of $\theta_{X+Y}$, $\theta_{X-Y}$, and
$\operatorname{R}_{Z}$ all have the same matrix part,
$(\begin{smallmatrix}1&1\\\ 0&1\end{smallmatrix})$, but generate three
distinct classes. One can write down explicit invariants for these classes
where the phase bits are correlated to the tableau entries, but in most cases
we present a single-qubit class as a subgroup of the symmetries of the
cube/octahedron, as shown in Figure 1.

###  6.1 Formal invariants

An _invariant_ is a property of tableaux which is preserved by the four
circuit-building rules.

Swap Rule:

Every class contains the $\operatorname{SWAP}$ gate, so every invariant we
propose must be satisfied by the tableau for $\operatorname{SWAP}$.

Composition Rule:

If the invariant holds for two gates, then it must hold for their composition.
We have seen that the tableau for the composition of two gates is essentially
the matrix product of the two tableau, except for the phase bits (which are
significantly more complicated to update).

Tensor Rule:

The tensor product of two gates satisfying the invariant must also satisfy the
invariant. Note that the tableau of the tensor product is the direct sum of
the tableaux, and phase bits are inherited from the sub-tableaux in the
natural way.

Ancilla Rule:

The invariant must be preserved when some qubits are used as ancillas. It
turns out the ancilla operation reduces the tableau to a submatrix (of non-
ancilla rows and columns) and under certain conditions, the corresponding
subset of the phase bits. This is somewhat technical, so we prove it in
Theorem 3 below.

######  Theorem 3.

Let $G$ be a stabilizer gate on $n$ qubits, and suppose there exist states
${\left|{\psi}\right\rangle}$ and ${\left|{\psi^{\prime}}\right\rangle}$ such
that

$G({\left|{x}\right\rangle}\otimes{\left|{\psi}\right\rangle})=H({\left|{x}\right\rangle})\otimes{\left|{\psi^{\prime}}\right\rangle}$

for all ${\left|{x}\right\rangle}$, for some unitary $H$ on $m$-qubits. In
particular, this is true if we use the ancilla rule to reduce $G$ to $H$,
where ${\left|{\psi}\right\rangle}={\left|{\psi^{\prime}}\right\rangle}$ is
the ancilla state. Then

  1. 1.

$H$ is a stabilizer operation,

  2. 2.

$\mathcal{M}(H)$ is obtained by removing the rows and columns corresponding to
the ancilla bits from $\mathcal{M}(G)$,

  3. 3.

If every bit (in $\mathcal{M}(G)$ as a binary matrix) we remove from a row is
zero, then the phase bit for that row is the same in $\mathcal{T}(G)$ and
$\mathcal{T}(H)$.

###### Proof.

Let $P\in\mathcal{P}_{m}$. Then for all ${\left|{x}\right\rangle}$,

$G(P{\left|{x}\right\rangle}\otimes{\left|{\psi}\right\rangle})=H(P{\left|{x}\right\rangle})\otimes{\left|{\psi^{\prime}}\right\rangle}.$

On the other hand, $G$ is a stabilizer gate, so conjugating the Pauli string
$P\otimes I^{n-m}$ by $G$ produces $Q\otimes R$ for $Q\in\mathcal{P}_{m}$ and
$R\in\mathcal{P}_{n-m}$ . Equivalently,

$G(P\otimes I^{n-m})=(Q\otimes R)G.$

It follows that

$\displaystyle
H(P{\left|{x}\right\rangle})\otimes{\left|{\psi^{\prime}}\right\rangle}$
$\displaystyle=G(P{\left|{x}\right\rangle}\otimes{\left|{\psi}\right\rangle})$
$\displaystyle=(Q\otimes
R)G({\left|{x}\right\rangle}\otimes{\left|{\psi}\right\rangle})$
$\displaystyle=(Q\otimes
R)\left(H({\left|{x}\right\rangle})\otimes{\left|{\psi^{\prime}}\right\rangle}\right)$
$\displaystyle=QH({\left|{x}\right\rangle})\otimes
R{\left|{\psi^{\prime}}\right\rangle},$

so up to phase, $H(P{\left|{x}\right\rangle})=QH({\left|{x}\right\rangle})$
for all ${\left|{x}\right\rangle}$, and
${\left|{\psi^{\prime}}\right\rangle}=R{\left|{\psi^{\prime}}\right\rangle}$.
The first equation implies $HP=QH$, or $HPH^{\dagger}=Q$. Since $P$ was
arbitrary, the conjugation of a Pauli string by $H$ is always another Pauli
string, so $H$ is a stabilizer gate.

In the special case that $P$ (and therefore $P\otimes I^{n-m}$) is a Pauli
basis element, then $Q\otimes R$ is represented in row of the binary tableau
of $G$. We keep the bits representing $Q$ in the tableau for $H$, since
$HPH^{\dagger}=Q$, which is why $\mathcal{M}(H)$ is a submatrix of
$\mathcal{M}(G)$. Clearly the phase of $Q$ is the same as the phase of
$Q\otimes R$ if and only if $R$ is positive. In the special case $R=\pm
I^{n-m}$, it is easy to see that $R$ is positive, otherwise

${\left|{\psi^{\prime}}\right\rangle}=R{\left|{\psi^{\prime}}\right\rangle}=-I^{n-m}{\left|{\psi^{\prime}}\right\rangle}=-{\left|{\psi^{\prime}}\right\rangle}$

is a contradiction. Hence, the phase for the corresponding row of
$\mathcal{T}(H)$ is inherited from $\mathcal{T}(G)$. ∎

As a direct consequence of these rules, our invariants take on a distinctly
algebraic flavor. Let us consider, for the sake of illustration, invariants
that depend only on the matrix part of the tableau and ignore the phase bits.
Then an invariant is equivalent to a set of matrices closed under the four
rules above. In particular, the matrices to form a group under multiplication
as a consequence of the composition rule (and the fact that every gate has
finite order).

On the other hand, not every group of matrices will correspond to an
invariant. For instance, due to the swap rule, the group of matrices must also
be closed under arbitrary reordering the rows and columns. This eliminates,
e.g., the group of upper triangular matrices. Similarly, the ancilla rule
excludes the special orthogonal group. In the end, we are left with just two
kinds of matrix groups which lead to invariants:

Subring Invariants

Matrices with elements restricted to a particular subring of $\mathsf{R}$
(analogous to the real matrices, integer matrices, etc.)

Permutation Invariants

Permutation matrices, except where each $1$ entry can be any one of a subset
of invertible elements, and each $0$ entry comes from a collection of non-
invertible elements.

Now we are ready to present formal definitions for these invariants, and show
that they really are preserved by the circuit-building rules.

###  6.2 Subring invariants

The first kind of invariant restricts the entries of the tableau to a subring
of $\mathsf{R}$. That is, given a subring $\mathsf{S}\subseteq\mathsf{R}$, a
gate satisfies the invariant $\mathscr{I}(\mathsf{S})$ if and only if all
entries of the tableau are in $\mathsf{S}$. There are twelve classes, all near
the top of the lattice, of the form

$\mathcal{C}=\\{\text{All gates satisfying $\mathscr{I}(\mathsf{S})$}\\},$

corresponding to all 12 subrings of $\mathsf{R}$ listed below.

  * •

The entire ring, $\mathsf{R}$, is technically a subring of itself, and
$\mathscr{I}(\mathsf{R})$ is the trivial invariant satisfied by all stabilizer
gates. Notice that not _every_ matrix over $\mathsf{R}$ gives a valid tableau
because it must still be unitary.

  * •

There are four maximal proper subrings of $\mathsf{R}$:

$\displaystyle\mathsf{R}_{X}$ $\displaystyle=\\{(\begin{smallmatrix}a&0\\\
c&d\end{smallmatrix}):\\{a,c,d\\}\in\\{0,1\\}\\},$
$\displaystyle\mathsf{R}_{Y}$ $\displaystyle=\\{(\begin{smallmatrix}a&b\\\
c&d\end{smallmatrix}):\\{a,b,c,d\\}\in\\{0,1\\},a+b+c+d=0\\},$
$\displaystyle\mathsf{R}_{Z}$ $\displaystyle=\\{(\begin{smallmatrix}a&b\\\
0&d\end{smallmatrix}):\\{a,b,d\\}\in\\{0,1\\}\\},$
$\displaystyle\mathsf{R}_{E}$ $\displaystyle=\\{(\begin{smallmatrix}a&b\\\
b&a+b\end{smallmatrix}):\\{a,b\\}\in\\{0,1\\}\\}.$

Our formal definition for $Z$-preserving gates is the invariant
$\mathscr{I}(\mathsf{R}_{Z})$. The fact that the lower left entry is $0$
implies that the gate maps Pauli strings of $I$ and $Z$ to strings of $I$ and
$Z$. Hence, $Z$-basis strings are mapped to $Z$-basis strings. Similarly, the
$X$-preserving and $Y$-preserving invariants are $\mathscr{I}(\mathsf{R}_{X})$
and $\mathscr{I}(\mathsf{R}_{Y})$ respectively. The egalitarian invariant,
$\mathscr{I}(\mathsf{R}_{E})$, comes from the subring $\mathsf{R}_{E}$.

  * •

The intersection of two subrings is itself a subring, giving us exactly four
more subrings ($\mathsf{R}_{X}\cap\mathsf{R}_{Y}$,
$\mathsf{R}_{X}\cap\mathsf{R}_{Z}$, $\mathsf{R}_{Y}\cap\mathsf{R}_{Z}$, and
$\mathsf{R}_{X}\cap\mathsf{R}_{Y}\cap\mathsf{R}_{Z}$) since the intersection
of $\mathsf{R}_{E}$ with any of the others is

$\mathsf{R}_{X}\cap\mathsf{R}_{Y}\cap\mathsf{R}_{Z}=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})\\},$

the trivial ring.

  * •

Three more subrings are obtained by taking only self-conjugate elements of
$\mathsf{R}_{X}$, $\mathsf{R}_{Y}$, and $\mathsf{R}_{Z}$ respectively. An
element $(\begin{smallmatrix}a&b\\\ c&d\end{smallmatrix})$ is _self-conjugate_
if

$(\begin{smallmatrix}a&b\\\ c&d\end{smallmatrix})=(\begin{smallmatrix}a&b\\\
c&d\end{smallmatrix})^{*},$

or equivalently, $a=d$. These invariants correspond to the $X$-orthogonal
(i.e., $\left<\operatorname{T_{4}},\mathcal{P},\operatorname{R}_{X}\right>$),
$Y$-orthogonal (i.e.,
$\left<\operatorname{T_{4}},\mathcal{P},\operatorname{R}_{Y}\right>$), and
$Z$-orthogonal (i.e.,
$\left<\operatorname{T_{4}},\mathcal{P},\operatorname{R}_{Z}\right>$) classes
respectively.

######  Theorem 4.

For any subring $\mathsf{S}\subseteq\mathsf{R}$, the property
$\mathscr{I}(\mathsf{S})$ is an invariant. That is, the set of matrices over
$\mathsf{S}$ respect the circuit building operations.

###### Proof.

Every subring contains $(\begin{smallmatrix}0&0\\\ 0&0\end{smallmatrix})$ and
$(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})$ by definition, and
therefore the tableau (phase bits omitted) of the $\operatorname{SWAP}$ gate,

$\left(\begin{array}[]{cc|cc}0&0&1&0\\\ 0&0&0&1\\\ \hline\cr 1&0&0&0\\\
0&1&0&0\\\ \end{array}\right)$

satisfies $\mathscr{I}(\mathsf{S})$.

Matrix multiplication is a polynomial in the entries of the two matrices, so
composition cannot produce entries outside the subring. Similarly, combining
tableau with tensor products or reducing tableau to submatrices via ancillas
does not introduce any new ring elements; those operations only use elements
already present in the tableau. We conclude that $\mathscr{I}(\mathsf{S})$ is
an invariant for any subring $\mathsf{S}$. ∎

###  6.3 Permutation invariants

The _permutation invariants_ get their name from the matrix part of their
tableaux, which is required to have the structure of a permutation matrix.
That is, every row (or column) has exactly one element which is invertible,
and the others are non-invertible. Permutation invariants are also sensitive
to phase bits. It is natural to associate the unique invertible element in a
row with the phase bits for that row, giving the tableau of a single-qubit
gate. A permutation invariant $\mathscr{P}(G,S)$ is defined by the set of
single-qubit gates $G$ which can be obtained in this way, and the set of non-
invertible elements $S$ used to fill the rest of the tableau. In other words,
a tableau satisfies $\mathscr{P}(G,S)$ if all entries are from $S$ except
exactly one entry per row which, when combined with the phase bits for the
row, is the tableau of some gate in $G$.

Note that not all pairs of sets $(G,S)$ produce an invariant. For instance,
circuit-building operations will fail to preserve $\mathscr{P}(G,S)$ if $G$ is
not a group. The exact relationship between $G$ and $S$ required to produce an
invariant is difficult to write down. Roughly speaking, products of elements
in $S$ should be zero, products of elements in $G$ should remain in $G$, and
products between $S$ and $\mathcal{M}(G)$ should be manageable in some sense.
Theorem 5 gives a list of $\mathscr{P}(G,S)$ invariants, which will turn out
to be exhaustive by Theorem 19, the culminating theorem of this paper.

######  Theorem 5.

We prove that the following permutation invariants are indeed invariant under
the circuit-building operations.

  1. 1.

If $G$ is a group of single-qubit gates then

$\mathscr{P}(G,\\{(\begin{smallmatrix}0&0\\\ 0&0\end{smallmatrix})\\})$

is an invariant for $\left<G\right>$. All thirty degenerate classes are
characterized by invariants of this form.

  2. 2.

If $\left<X\right>\subseteq
G\subseteq\left<\mathcal{P},\operatorname{R}_{X}\right>$ is a group of single-
qubit gates then

$\mathscr{P}(G,\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&0\\\ 1&0\end{smallmatrix})\\})$

is an invariant for $\langle C(X,X),G\rangle$. These invariants characterize
the five $X$-degenerate classes.

  3. 3.

If $\left<Y\right>\subseteq
G\subseteq\left<\mathcal{P},\operatorname{R}_{Y}\right>$ is a group of single-
qubit gates then

$\mathscr{P}(G,\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&1\\\ 1&1\end{smallmatrix})\\})$

is an invariant for $\langle C(Y,Y),G\rangle$. These invariants characterize
the five $Y$-degenerate classes.

  4. 4.

If $\left<Z\right>\subseteq
G\subseteq\left<\mathcal{P},\operatorname{R}_{Z}\right>$ is a group of single-
qubit gates then

$\mathscr{P}(G,\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix})\\})$

is an invariant for $\langle C(Z,Z),G\rangle$. These invariants characterize
the five $Z$-degenerate classes.

###### Proof.

Let $\mathscr{P}(G,S)$ be one of the invariants above. Let
$M=\\{\mathcal{M}(g):g\in G\\}$ be the set of matrices from tableaux in $G$.
In all cases, $S$ contains $(\begin{smallmatrix}0&0\\\ 0&0\end{smallmatrix})$,
and $G$ contains the single-qubit identity operation,

$\left(\begin{array}[]{cc|c}1&0&0\\\ 0&1&0\end{array}\right),$

so $\operatorname{SWAP}$ satisfies the invariant. And clearly the direct sum
of two tableaux in $\mathscr{P}(G,S)$ is still in $\mathscr{P}(G,S)$ for any
$G$ and $S$.

Now consider the composition of two gates. Each entry in the tableau is a dot
product of some row from one tableau with some column from the other. Hence,
the entry is a sum of $S\times S$, $S\times M$, $M\times S$, or $M\times M$
products. Observe that the $S\times S$ products are all zero (for the
particular sets $S$ above), so we may ignore those products. Recall that the
row and column each contain exactly one entry in $M$, so depending on whether
those entries align, we get either $SM+MS\subseteq S$ or $M^{2}=M$.
Furthermore, for any row in one tableau there is exactly one column in the
other such that the invertible entries line up. Therefore, exactly one entry
in any row (or column) of the composition is in $M$ and the rest are in $S$.
Clearly the matrix part of the tableau has the correct form for the invariant.

We must also consider phase bits under composition. Recall that the phase bits
associate with the invertible entries of the matrix to produce single-qubit
gates. When we multiply two tableau, these single-qubit gates multiply to
produce elements in $G$ (since $G$ is a group), as you would expect. If the
non-invertible elements are all zero, then this is the only factor in
determining phase bits, so the invariant is preserved by composition.

Now consider the phase bits in the case where $S$ contains nonzero elements,
for instance,

$S=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix})\\}.$

Notice that in this case, both matrices in $S$ have zeros in the bottom row,
and the invertible matrices are of the form $(\begin{smallmatrix}1&a\\\
0&1\end{smallmatrix})$. Hence, every even-indexed row of the tableau (as a
binary matrix) is all zeros except for one entry. Using the method of tableau
composition in Section 4, one can easily show that for these even-indexed
rows, the phase bits are exactly what one would get by composing the
invertible elements as gates in $G$. For the other half of the rows, the non-
invertible elements may flip the phase bits. But we assume $G$ contains the
Pauli element (in this case $Z$) which flips that sign, so the invertible
elements and associated phase bits are still in $G$, therefore the invariant
is preserved. The $X$\- and $Y$-degenerate cases are similar.

Last, we show that $\mathscr{P}(G,S)$ is preserved under ancilla operations.
Recall that when we use ancillas, we remove the rows and columns corresponding
to those bits. Clearly the elements of the submatrix are still in $M$ and $S$.
There is a risk that the invertible element for some row could be in one of
the removed columns, but if the submatrix is missing an invertible element in
some row then the submatrix is not unitary and the ancilla rule must have been
misapplied. Hence, only elements in $S$ are removed in the non-ancilla part of
the tableau, and each row still contains exactly one entry in $M$.

We appeal to Theorem 3 for the phase bits. The theorem says that removing the
ancillas can only change the sign for a row if there is a nonzero entry in the
non-ancilla bits of the row that are removed. For example, if
$S=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix})\\}$
then only the top phase bit can change. But changing the top phase bit is the
same as applying a $Z$, and for this case $Z$ is assumed to be in $G$, so the
combination of the element in $M$ and the phase bits is still in $G$.
Therefore the $Z$-degenerate $\mathscr{P}(G,S)$ are invariants, and the
$X$-degenerate and $Y$-degenerate invariants follow by symmetry.

∎

##  7 Equivalence of Generator and Invariant Definitions

We have now defined each class by a set of generators, and by an invariant,
but have not yet shown that these definitions coincide. Below are a collection
of lemmas which prove this for all classes in our lattice. Note that one
direction is always trivial: it is easy to check that the generators defining
a class satisfy a particular invariant, and therefore everything they generate
(i.e., the class) must satisfy the invariant. We encourage the reader to check
these invariants against, say, the tableaux in Table 2.

For the other inclusion (i.e., every gate satisfying the invariant can be
generated by the given generators), we start with an arbitrary gate $g$
satisfying the invariant, and apply gates in the class to $g$ to simplify its
tableau step-by-step until it is the tableau of the identity operation. It
follows that $AgB=I$ for circuits $A$ and $B$ in the class, which proves
$g=A^{-1}B^{-1}$ is in the class. In many cases, the circuit derived this way
is a _canonical form_ for the gate, and can be used to count the number of
gates on $n$ qubits in a class.

Let us start with the degenerate classes.

######  Lemma 6.

Let $G$ be a group of single-qubit gates, and let $g$ be a gate satisfying the
permutation invariant $\mathscr{P}(G,\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix})\\})$. Then there is a circuit for $g$ consisting of a
permutation of the inputs followed by layer of single-qubit gates in $G$.

###### Proof.

Consider the tableau for $g$. Each row or column has exactly one invertible
element, so we can read off a permutation $\pi$ from the positions of those
elements. Apply $\operatorname{SWAP}$ gates to $g$ to remove this permutation,
and put the invertible elements on the diagonal. When we pair a diagonal
element with the phase bits for that row, we get a single-qubit gate $g_{i}$
in $G$. Applying the inverse of this gate to qubit $i$ will zero the phase
bits for that row, and make $(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})$
the diagonal entry. Once we do this for each row, we have the identity
tableau, therefore $g$ is in $\left<G\right>$ and has a circuit of the desired
form. ∎

Next, we consider the $Z$-degenerate classes and, by symmetry, the
$X$-degenerate and $Y$-degenerate classes.

######  Lemma 7.

Let $\left<Z\right>\subseteq
G\subseteq\left<\mathcal{P},\operatorname{R}_{Z}\right>$ be a subgroup of
$Z$-preserving single-qubit gates. Let $g$ be any gate satisfying the
permutation invariant $\mathscr{P}(G,\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix})\\})$.
Then there is a circuit for $g$ consisting of a layer of single-qubit gates
(from $G$), a layer of $C(Z,Z)$ gates, and a permutation.

###### Proof.

Consider the tableau of $g$. We can read off a permutation $\pi$, and a
single-qubit gate for each input. Assume we have removed those gates (i.e., we
now consider the tableau of $g\pi^{-1}g_{1}^{-1}\cdots g_{n}^{-1}$), so the
tableau has $(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})$ on the
diagonal, all other entries are either $(\begin{smallmatrix}0&1\\\
0&0\end{smallmatrix})$ or zero, and the phase bits are zero.

The non-zero, off-diagonal entries in the matrix indicate the positions of
$C(Z,Z)$ gates. Specifically, if the entry in row $i$ and column $j$ is
nonzero then there is a $C(Z,Z)$ on qubits $i$ and $j$. Note that because the
matrix part of the tableau is unitary, the symmetric entry in row $j$ and
column $i$ must also be non-zero. The remainder of the circuit consists of the
set of $C(Z,Z)$ gates indicated by the non-zero, off-diagonal entries. Notice
that $C(Z,Z)$ gates always commute, so their ordering does not matter.. ∎

Now let us consider four $Z$-preserving classes which, when we consider
symmetry (i.e., the $X$-preserving and $Y$-preserving equivalents) cover all
but two of the remaining classes.

######  Lemma 8.

Each of the classes $\left<\operatorname{T_{4}},\mathcal{P}\right>$,
$\left<\operatorname{T_{4}},\mathcal{P},\operatorname{R}_{Z}\right>$,
$\left<C(Z,X),\mathcal{P}\right>$, and
$\left<C(Z,X),\mathcal{P},\operatorname{R}_{Z}\right>$ is the set of all gates
corresponding to a subring invariant, where the subrings are

$\displaystyle\mathsf{S}_{1}$ $\displaystyle=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})\\},$
$\displaystyle\mathsf{S}_{2}$ $\displaystyle=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}),(\begin{smallmatrix}1&1\\\ 0&1\end{smallmatrix})\\},$
$\displaystyle\mathsf{S}_{3}$ $\displaystyle=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&0\\\
0&1\end{smallmatrix}),(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})\\},$
$\displaystyle\mathsf{S}_{4}$ $\displaystyle=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&0\\\
0&1\end{smallmatrix}),(\begin{smallmatrix}0&1\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\
0&1\end{smallmatrix}),(\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}),(\begin{smallmatrix}1&1\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&1\\\ 0&1\end{smallmatrix})\\}.$

###### Proof.

In all four classes, elements of the tableau are of the form
$(\begin{smallmatrix}a&b\\\ 0&d\end{smallmatrix})$. Suppose
$(\begin{smallmatrix}?&?\\\ 0&d_{1}\end{smallmatrix})$ is the $i$th entry of
some row, and $(\begin{smallmatrix}?&?\\\ 0&d_{2}\end{smallmatrix})$ is the
$j$th entry in the same row, where entries labeled by “?” are unconstrained.
If we apply a $\operatorname{CNOT}$ gate from qubit $i$ to $j$, these entries
will be of the form $(\begin{smallmatrix}?&?\\\ 0&d_{1}\end{smallmatrix})$ and
$(\begin{smallmatrix}?&?\\\ 0&d_{1}+d_{2}\end{smallmatrix})$ respectively.
That is, the bottom right bits change as though we applied the
$\operatorname{CNOT}$ gate to those bits. Since a $\operatorname{T_{4}}$ gate
can be built from $\operatorname{CNOT}$ gates, it will (similarly) affect the
bottom right bits as though we are applying a $\operatorname{T_{4}}$.

Our strategy is to use either $\operatorname{CNOT}$ or $\operatorname{T_{4}}$
gates (depending on the class) to perform Gaussian elimination on the bottom
right entries of the matrix elements. If we have access to
$\operatorname{CNOT}$ gates then we literally apply Gaussian elimination,
using $\operatorname{CNOT}$ to add one column to another, and using
$\operatorname{SWAP}$ to exchange columns.

If we only have $\operatorname{T_{4}}$ gates then we are in subring
$\mathsf{S}_{1}\subseteq\mathsf{S}_{2}$ or $\mathsf{S}_{2}$, so
$(\begin{smallmatrix}1&0\\\ 0&1\end{smallmatrix})$ and
$(\begin{smallmatrix}1&1\\\ 0&1\end{smallmatrix})$ are the only elements with
a $1$ in the bottom right position, and also the only invertible elements. It
follows that the number of bottom right bits set to $1$ in a row is the same
as the number of invertible elements, which must be odd because the matrix is
unitary. To reduce the number, we apply a $\operatorname{T_{4}}$ to three $1$
bits and a $0$ bit (note: we may add a zero bit by adding an ancilla, if
necessary), which changes the $0$ to a $1$ and the $1$’s to $0$’s, reducing
the number of $1$’s (or invertible elements) in the row by two. When there is
a single $1$ left in the row, unitarity conditions imply that it is also the
only $1$ left in that column, so we may ignore that row and column for the
moment and continue to eliminate the rest of the matrix.

Now suppose we have row reduced the matrix, using either $\operatorname{CNOT}$
or $\operatorname{T_{4}}$, so that the bottom right entry of every element is
$0$, except along the diagonal where that bit $1$. At this point, the diagonal
element is the only element in a row that can possibly be invertible,
therefore the diagonal elements are of the form $(\begin{smallmatrix}1&b\\\
0&1\end{smallmatrix})$. Similarly, unitarity conditions imply that the off-
diagonal elements are of the form $(\begin{smallmatrix}0&b\\\
0&0\end{smallmatrix})$. In other words, the remaining tableau is
$Z$-degenerate, since there is only one invertible element per row or column,
and the off-diagonal elements are in $I=\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix})\\}$. We
can use either Lemma 6 or Lemma 7 to find a circuit from the remainder, which
is in either $\left<\mathcal{P}\right>$ or
$\left<C(Z,Z),\mathcal{P},\operatorname{R}_{Z}\right>$, depending on the
class. ∎

There are only two classes remaining, $\mathsf{ALL}$ and
$\left<\operatorname{T_{4}},\mathcal{P},\Gamma\right>$, which we handle
specially. For the first, we appeal to Aaronson and Gottesman [2] who give an
explicit decomposition for any stabilizer gate into layers of
$\operatorname{CNOT}$, Hadamard ($\theta_{X+Z}$ in our notation), and phase
($\operatorname{R}_{Z}$) gates.

######  Lemma 9.

Any egalitarian gate $g$ can be constructed from $\operatorname{T_{4}}$,
$\mathcal{P}$ and $\Gamma$ gates.

###### Proof.

Egalitarian gates satisfy the invariant that all elements are in the subring

$\\{(\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}),(\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}),(\begin{smallmatrix}1&1\\\
1&0\end{smallmatrix}),(\begin{smallmatrix}0&1\\\ 1&1\end{smallmatrix}).\\}$

In fact, this subring is isomorphic to $\mathbb{F}_{4}$, so it is a field. The
unitarity of the matrix in our sense translates to unitarity as a matrix over
$\mathbb{F}_{4}$.

Like the other $\operatorname{T_{4}}$ classes, we use Gaussian elimination on
the tableau of $g$. Consider a row of the tableau. If the entry in some column
is not the identity, then apply $\Gamma$ or $\Gamma^{-1}$ to the corresponding
qubit to make it the identity. By unitarity, there are an odd number of
identity elements in the row. We may remove pairs of identity elements with a
$\operatorname{T_{4}}$, similar to Lemma 8, until there is only one left and
the rest of the row is zero. Unitarity implies the column below the identity
element is also zero, and we proceed to eliminate the rest of the tableau.
Once the matrix part of the tableau is the identity, we apply Pauli matrices
to zero out the phase bits.

We conclude that all egalitarian gates are in
$\left<\operatorname{T_{4}},\mathcal{P},\Gamma\right>$. ∎

##  8 Circuit Identities

In this section, we give necessary tools to prove that a set of gates
generates, in some sense, “all that one could hope for.” Formally, we wish to
prove that the gate set generates a particular class in the classification
lattice when it is contained in that class but fails to satisfy the invariants
of all classes below it. To this end, we give several useful circuit
identities that will be used extensively in Section 9. For instance, one can
show that any circuit on two qubits can be reduced to an equivalent circuit
containing at most one generalized CNOT gate (see Appendix D). The following
lemma gives only the aspect of that theorem that is necessary to the
classification, that is, the ability to extract single-qubit stabilizers from
the composition of generalized CNOT gates.

######  Lemma 10.

Let $P,Q,R\in\mathcal{P}$, and let $\Gamma P\Gamma^{\dagger}=Q$ and $\Gamma
Q\Gamma^{\dagger}=R$. Then

  * •

$C(P,Q)$ and $C(P,R)$ generate $\operatorname{R}_{P}$.

  * •

$C(P,P)$ and $C(P,R)$ generate $\operatorname{R}_{P}$.

  * •

$C(P,P)$ and $C(Q,R)$ generate $\Gamma$.

  * •

$C(P,P)$ and $C(Q,Q)$ generate $\theta_{P+Q}$.

###### Proof.

The first two inclusions come from the following identity, which holds
whenever $\Gamma Q\Gamma^{\dagger}=R$ (i.e. regardless of $P$):

$\textstyle{P}$$\textstyle{P}$$\textstyle{R}$$\textstyle{Q}$=$\textstyle{\operatorname{R}_{P}}$$\textstyle{P}$$\textstyle{RQ}$$\xrightarrow[\text{rule}]{\text{ancilla}}$$\textstyle{\operatorname{R}_{P}}$

Similarly, for the third identity, we get

$\textstyle{P}$$\textstyle{Q}$$\textstyle{P}$$\textstyle{P}$$\textstyle{R}$$\textstyle{P}$=$\textstyle{\times}$$\textstyle{\Gamma}$$\textstyle{\times}$$\textstyle{\Gamma^{\dagger}}$$\xrightarrow[\text{rule}]{\text{swap}}$$\textstyle{\Gamma}$$\textstyle{\Gamma^{\dagger}}$$\xrightarrow[\text{rule}]{\text{ancilla}}$$\textstyle{\Gamma}$

and for the final identity

$\textstyle{P}$$\textstyle{Q}$$\textstyle{P}$$\textstyle{P}$$\textstyle{Q}$$\textstyle{P}$=$\textstyle{\times}$$\textstyle{\theta_{P+Q}}$$\textstyle{\times}$$\textstyle{\theta_{P+Q}}$$\xrightarrow[\text{rule}]{\text{swap}}$$\textstyle{\theta_{P+Q}}$$\textstyle{\theta_{P+Q}}$$\xrightarrow[\text{rule}]{\text{ancilla}}$$\textstyle{\theta_{P+Q}}$
.

∎

It might seem strange to reduce non-degenerate gates into less powerful
single-qubit gates, but we will eventually see that single-qubit generators
are the most crucial. Once we have shown that a particular set of gates
generates all single-qubit operations, then that set of gates will generate
the class of _all_ stabilizer operations provided it contains any non-
degenerate gate. All non-degenerate gates generate at least one Pauli, often
the entire Pauli group, which is why some single-qubit classes do not appear
as the single-qubit subgroup of a non-degenerate class. For instance, consider
the CNOT gate where the first qubit controls the second qubit. If we let the
first input be ${\left|{1}\right\rangle}$, then a Pauli $X$ operation is
always applied to the second qubit. Similarly, if we let the input to the
second qubit be ${\left|{-}\right\rangle}$, then a Pauli $Z$ operation is
always applied to the first qubit. Under the ancilla rule, we now have Pauli
$X$ and $Z$ operations, so we can generate $Y$ and the entire Pauli group.
Clearly, the same is true for any heterogeneous CNOT gate. However,
surprisingly, the following lemma shows that even the $\operatorname{T_{4}}$
gate suffices to generate the entire Pauli group.

######  Lemma 11.

$\operatorname{T_{4}}$ generates the Pauli group.

###### Proof.

Consider the following two circuits:

$\textstyle{\frac{{\left|{00}\right\rangle}-{\left|{11}\right\rangle}}{\sqrt{2}}}$
$\textstyle{\operatorname{T_{4}}}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{\times}$$\textstyle{{\left|{x}\right\rangle}}$
$\textstyle{\times}$$\textstyle{(-1)^{x}{\left|{x}\right\rangle}}$

$\textstyle{\frac{{\left|{01}\right\rangle}+{\left|{10}\right\rangle}}{\sqrt{2}}}$
$\textstyle{\operatorname{T_{4}}}$$\textstyle{{\left|{+}\right\rangle}}$
$\textstyle{\times}$$\textstyle{{\left|{x}\right\rangle}}$
$\textstyle{\times}$$\textstyle{\left|{x\oplus 1}\right\rangle}$

Under the ancilla rule, the first generates a Pauli $Z$ operation while the
second generates a Pauli $X$, from which we can clearly generate the Pauli
group. ∎

There is another way to view the identity of Lemma 11 which will be useful
later. Since $\operatorname{T_{4}}$ is an affine gate over the computational
basis states, $\operatorname{T_{4}}=C_{1}C_{2}\ldots C_{n}$ where each $C_{i}$
is a CNOT gate. Furthermore, $\operatorname{T_{4}}$ and CNOT are their own
inverses, so $\operatorname{T_{4}}=C_{n}C_{n-1}\ldots C_{1}$. Finally, because
$\operatorname{T_{4}}$ is symmetric when represented as a $4\times 4$ matrix
over $\mathbb{F}_{2}$, $\operatorname{T_{4}}=C_{1}^{T}C_{2}^{T}\ldots
C_{n}^{T}$. Notice that $C_{i}^{T}$ just represents the CNOT gate $C_{i}$
where the control and target qubits are swapped. Therefore, leveraging the
well-known equivalence $\theta^{\otimes
2}_{X+Z}\circ\operatorname{CNOT}\circ\theta^{\otimes
2}_{X+Z}=\operatorname{SWAP}\circ\operatorname{CNOT}\circ\operatorname{SWAP}$
we arrive at the following consequence:666Recall that $\theta_{X+Z}$ is
commonly known as the Hadamard gate.

$\theta_{X+Z}^{\otimes 4}\operatorname{T_{4}}\theta_{X+Z}^{\otimes
4}=\operatorname{T_{4}}.$

Similarly, by straightforward calculation, we get

$\operatorname{R}_{Z}^{\otimes
4}\operatorname{T_{4}}\operatorname{R}_{Z}^{\otimes 4}=\operatorname{T_{4}}.$

It is now easy to extend old circuit identities into new ones. For instance,
conjugating the first circuit in the proof of Lemma 11 by
$\theta_{X+Z}^{\otimes 4}$ (which does not change the circuit because of the
above observations) and pushing the $\theta_{X+Z}$ gates into the inputs,
yields the second circuit. This technique is in fact very general and is used
in the proof of the lemma below.

######  Lemma 12.

$\operatorname{T_{4}}$ and $C(P,P)$ generate $\operatorname{R}_{P}$.

###### Proof.

Figure 6 shows how to generate $\operatorname{R}_{Z}$ with $C(Z,Z)$. Using the
argument by conjugation above, $\operatorname{T_{4}}$ and $C(P,P)$ generate
$\operatorname{R}_{P}$. ∎

$\textstyle{\frac{{\left|{00}\right\rangle}+i{\left|{11}\right\rangle}}{\sqrt{2}}}$
$\textstyle{\operatorname{T_{4}}}$
$\textstyle{Z}$$\textstyle{{\left|{0}\right\rangle}}$
$\textstyle{Z}$$\textstyle{\times}$$\textstyle{{\left|{x}\right\rangle}}$
$\textstyle{\times}$$\textstyle{i^{x}{\left|{x}\right\rangle}}$

Figure 6: Generating $\operatorname{R}_{Z}$ with $\operatorname{T_{4}}$ and
$C(Z,Z)$.

The following lemmas make precise our working assumption that single-qubit
gates can significantly bolster the power of non-degenerate gate sets.

######  Lemma 13.

Suppose we have any $C(P,Q)$ gate with any single-qubit gate $G$ that does not
preserve the $P$-basis and any single-qubit gate $H$ that does not preserve
the $Q$-basis. Then $\left<C(P,Q),G,H\right>=\mathsf{ALL}$.

###### Proof.

We will prove that the class $\left<C(P,Q),G,H\right>$ contains all single-
qubit gates. Then, to prove that the class generates all stabilizer
operations, it is be sufficient to show that it contains a CNOT gate. However,
since all generalized CNOT gates are conjugates of each other, this is
immediate.

First suppose $P=Q$. Since $G$ does not preserve $P$-basis, we can use $G$ to
create a $C(R,R)$ gate where $R\neq P$. By Lemma 10, we can generate a
$\theta_{P+R}$ gate. Conjugating $C(P,P)$ by $\theta_{P+R}$ on the second
qubit yields a $C(P,R)$ gate. Once again leveraging Lemma 10, $C(P,R)$ and
$C(P,P)$ generate an $\operatorname{R}_{P}$ gate. Referring to the single-
qubit lattice (see Figure 4), we see that the class
$\left<\mathcal{P},\theta_{P+R},\operatorname{R}_{P}\right>$ contains all
single-qubit gates.

Now suppose that $P\neq Q$. Once again, since $G$ does not preserve $P$-basis,
we can use $G$ to create a $C(R,Q)$ gate. If $R=Q$, then by the logic above,
we can use $H$ to generate all single qubit gates, so suppose $R\neq Q$. By
Lemma 10, we can use $C(P,Q)$ and $C(R,Q)$ to generate an
$\operatorname{R}_{Q}$ gate. Conjugating both $C(P,Q)$ and $C(R,Q)$ by $H$
appropriately, gives a $C(P,S)$ and $C(R,S)$ for some $S\neq Q$, which we can
once again generate an $\operatorname{R}_{S}$ gate. Referring to the single-
qubit lattice, we see that the class
$\left<\mathcal{P},\operatorname{R}_{S},\operatorname{R}_{Q}\right>$ contains
all single-qubit gates. ∎

######  Lemma 14.

$\operatorname{T_{4}}$ with the class of all single-qubit gates generates
$\mathsf{ALL}$.

###### Proof.

It is well known that $\operatorname{CNOT}$, $\theta_{X+Z}$, and
$\operatorname{R}_{Z}$ generate all stabilizer circuits. Therefore, it will be
sufficient to show that $\operatorname{T_{4}}$ plus all single-qubit gates
generate $\operatorname{CNOT}$. Under the ancilla rule, it is clear by Figure
7 that $\operatorname{T_{4}}$ and $\operatorname{R}_{Z}$ suffice to generate
$C(Z,Z)$. Conjugating one qubit of $C(Z,Z)$ by $\theta_{X+Z}$ yields a
$C(Z,X)=\operatorname{CNOT}$ gate, completing the proof. ∎

Figure 7: Generating $C(Z,Z)$ with $\operatorname{T_{4}}$ and
$\operatorname{R}_{Z}$.

##  9 Universal Construction

Suppose $G$ is an $n$-qubit stabilizer gate. It turns out there is a single
circuit $\mathfrak{C}(G)$, the _universal construction_ , which can help us
extract useful generators (e.g., single-qubit gates, generalized CNOTs, etc.)
from $G$. Specifically, the circuit $\mathfrak{C}(G)$ (shown in Figure 8)
applies $G$ to qubits $2$ through $n+1$, swaps qubits $1$ and $2$, then
applies $G^{-1}$ to qubits $2$ through $n+1$.

$\times$$\times$pt$\vdots$$\vdots$$\vdots$ $G$ $G^{-1}$ Figure 8: Universal
Construction $\mathfrak{C}(G)$

Note that after we apply $G$, all of the qubits but one go directly into
$G^{-1}$, which should intuitively cancel out “most” of the effect $G$ has on
those qubits, isolating the effect of $G$ on the swapped qubit. The following
theorem makes this intuition more precise.

######  Theorem 15.

Let $G$ be an $n$-qubit stabilizer gate. Then

$\mathcal{M}(\mathfrak{C}(G))=I_{n+1}+\begin{pmatrix}1\\\
v\end{pmatrix}\begin{pmatrix}1&v^{*}\end{pmatrix}$

where $v\in\mathsf{R}^{n\times 1}$ is the first column of $\mathcal{M}(G)$.

###### Proof.

Let $\mathcal{M}(G)=\left(\begin{smallmatrix}A&B\\\
C&D\end{smallmatrix}\right)$ with $A\in\mathsf{R}$,
$B\in\mathsf{R}^{1\times(n-1)}$, $C\in\mathsf{R}^{(n-1)\times 1}$, and
$D\in\mathsf{R}^{(n-1)\times(n-1)}$. Thus,

$\mathcal{M}(G)\mathcal{M}(G^{\dagger})=\begin{pmatrix}1&0\\\
0&I_{n-1}\end{pmatrix}=\begin{pmatrix}A&B\\\
C&D\end{pmatrix}\begin{pmatrix}A^{*}&C^{*}\\\
B^{*}&D^{*}\end{pmatrix}=\begin{pmatrix}AA^{*}+BB^{*}&AC^{*}+BD^{*}\\\
CA^{*}+DB^{*}&CC^{*}+DD^{*}\end{pmatrix}$

which implies

$\displaystyle\mathcal{M}(\mathfrak{C}(G))$
$\displaystyle=\begin{pmatrix}1&0&0\\\ 0&A&B\\\
0&C&D\end{pmatrix}\begin{pmatrix}0&1&0\\\ 1&0&0\\\
0&0&1\end{pmatrix}\begin{pmatrix}1&0&0\\\ 0&A^{*}&C^{*}\\\
0&B^{*}&D^{*}\end{pmatrix}=\begin{pmatrix}0&A^{*}&C^{*}\\\ A&BB^{*}&BD^{*}\\\
C&DB^{*}&DD^{*}\end{pmatrix}$ $\displaystyle=\begin{pmatrix}0&A^{*}&C^{*}\\\
A&1+AA^{*}&AC^{*}\\\
C&CA^{*}&I_{n-1}+CC^{*}\end{pmatrix}=I_{n+1}+\begin{pmatrix}1\\\ A\\\
C\end{pmatrix}\begin{pmatrix}1&A^{*}&C^{*}\end{pmatrix}.$

∎

Tableaux of the form $I_{n}+vv^{*}$ have relatively simple circuit
decompositions in terms of single-qubit generators and generalized CNOT gates,
which is formalized in the following theorem.

######  Theorem 16.

Let
$v=\\{1,a_{2},a_{3},\ldots,a_{2k},b_{1},\ldots,b_{\ell}\\}\in\mathsf{R}^{n\times
1}$ where each $a_{i}$ is invertible and each $b_{i}$ is singular, and let $C$
be a stabilizer circuit such that $\mathcal{M}(C)=I_{n}+vv^{*}$. Then $C$ is
equivalent to the circuit consisting of

  * •

a $\operatorname{T}_{2k}$ gate on the first $2k$ qubits,

  * •

conjugated by $\mathcal{G}(a_{i},i)$ for all $i$ in $\\{2,\ldots,2k\\}$,

  * •

conjugated by $\operatorname{CNOT}(b_{i},1,2k+i)$ for all
$i\in\\{1,\ldots,\ell\\}$, and

  * •

a final layer of Pauli gates (_not_ conjugated) on every qubit.

That is, $C$ is equivalent to the circuit in Figure 9.

###### Proof.

Notice first that because each $a_{i}$ is invertible, we can conjugate $C$ by
$\mathcal{G}(a_{i},i)$ for each $i\in\\{2,\ldots,2k\\}$, yielding a circuit
with the simpler tableau

$\text{Diag}(1,a_{2},\ldots,a_{2k},1,\ldots,1)(I_{n}+vv^{*})\text{Diag}(1,a_{2}^{*},\ldots,a_{2k}^{*},1,\ldots,1)=I_{n}+v^{\prime}v^{\prime*}$

where $v^{\prime}=\\{1,\ldots,1,b_{1},\ldots,b_{\ell}\\}$. Furthermore,
conjugating the circuit by the gate $\operatorname{CNOT}(b_{i},1,i+2k)$
corresponds to the simplification

$\operatorname{CNOT}(b_{i},1,i+2k)(I_{n}+v^{\prime}v^{\prime*})\operatorname{CNOT}(b_{i},1,i+2k)=I_{n}+v^{\prime\prime}v^{\prime\prime*}$

where $v^{\prime\prime}$ is equal to $v^{\prime}$ with the exception that
entry $i+2k$ is equal to zero. Repeating this procedure for each
$i\in\\{1,\ldots,\ell\\}$, we arrive at a circuit with a very simple tableau:

$I_{n}+\\{1,\ldots,1,0,\ldots,0\\}\\{1,\ldots,1,0,\ldots,0\\}^{T},$

which is exactly the tableau of a $\operatorname{T}_{2k}$ gate applied to the
first $2k$ qubits. Notice, finally, that by reversing the procedure and
applying the appropriate Pauli gates to each qubit, we can ensure that the
tableau of the decomposition is that of $\mathfrak{C}(G)$. ∎

pt$\operatorname{T}_{2k}$$b_{1}$$b_{2}$$\ldots$$b_{\ell}$$b_{\ell}$$\ldots$$b_{2}$$b_{1}$$P_{1}$$\mathcal{G}(a_{2})$$\mathcal{G}^{-1}(a_{2})$$P_{2}$$\mathcal{G}(a_{3})$$\mathcal{G}^{-1}(a_{3})$$P_{3}$$\vdots$$\vdots$$\vdots$$\mathcal{G}(a_{2k})$$\mathcal{G}^{-1}(a_{2k})$$P_{2k}$$b_{1}^{*}$$b_{1}^{*}$$P_{2k+1}$$b_{2}^{*}$$b_{2}^{*}$$P_{2k+2}$$\ddots$$\iddots$$\vdots$$b_{\ell}^{*}$$b_{\ell}^{*}$$P_{n}$
Figure 9: Decomposition of $\mathfrak{C}(G)$.

Theorem 16 leads to a clean circuit decomposition of $\mathfrak{C}(G)$. All
that is left to show is that we can actually generate each of the elementary
gates that appears in the decomposition under the ancilla rule. First, we will
need the following useful lemma, which will allow us to essentially disregard
the Pauli operators in the decomposition of the universal construction when
applying the ancilla rule.

######  Lemma 17.

Let $G$ be a gate on $n$ qubits which is stabilized by some state
${\left|{a}\right\rangle}$ on the first $k$ qubits and generates $H$ on the
remaining qubits. Furthermore, let $P$ be any gate on the first $k$ qubits.
Then $P\circ G$ generates $H\otimes H^{-1}$.

###### Proof.

By supposition we have that
$G({\left|{a}\right\rangle}\otimes{\left|{\psi}\right\rangle})={\left|{a}\right\rangle}\otimes
H{\left|{\psi}\right\rangle}$. Therefore $P\circ
G({\left|{a}\right\rangle}\otimes{\left|{\psi}\right\rangle})=P{\left|{a}\right\rangle}\otimes
H{\left|{\psi}\right\rangle}$. Now apply the inverse of $P\circ G$ to
$P{\left|{a}\right\rangle}\otimes H{\left|{\psi}\right\rangle}$ with the same
first $k$ qubits and $n-k$ new qubits. In the middle, $P$ cancels with
$P^{-1}$, and we can remove those $k$ qubits by using
${\left|{a}\right\rangle}$ as an ancilla. On the remaining qubits, we have
$H\otimes H^{-1}$. ∎

We are finally ready to prove the main theorem of this section.

######  Theorem 18.

Let $G$ be a stabilizer gate on $n$ qubits. Furthermore, let

$v=(1,a_{2},a_{3},\ldots,a_{2k},b_{1},\ldots,b_{\ell})\in\mathsf{R}^{n\times
1}$

be a vector where each $a_{i}$ is invertible and each $b_{i}$ is singular be
some row of $\mathcal{M}(G)$. Then $G$ generates a gate $\mathcal{G}$ such
that $\mathcal{M}(\mathcal{G})=a_{i}$ for each $i\in\\{2,\ldots,2k\\}$,
$\operatorname{CNOT}(b_{j})$ for all $j\in\\{1,\ldots,\ell\\}$, and
$\operatorname{T}_{2k}$ gate.

###### Proof.

From theorems 15 and 16, we know that universal construction $\mathfrak{C}(G)$
can be decomposed as shown in Figure 9. The proof will proceed in the
following manner. Starting with the decomposition of $\mathfrak{C}(G)$, we
show that it generates some elementary gate. We then use that gate to simplify
the original decomposition of $\mathfrak{C}(G)$, eventually generating all
such gates in this manner.

First notice that for some input $i\in\\{2k+1,\ldots,n\\}$, the single-qubit
stabilizer state ${\left|{b_{i}}\right\rangle}$ serves to remove the effect of
the generalized CNOT. By Lemma 17, we can remove the last $\ell$ qubits with
ancillas, at the expense of creating another (inverted) copy of the remaining
$2k$ bits. That is, we have $H\otimes H^{-1}$ where $H$ is as follows:

pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$$P_{1}$$\mathcal{G}(a_{2})$$\mathcal{G}^{-1}(a_{2})$$P_{2}$$\mathcal{G}(a_{3})$$\mathcal{G}^{-1}(a_{3})$$P_{3}$$\vdots$$\vdots$$\vdots$$\mathcal{G}(a_{2k})$$\mathcal{G}^{-1}(a_{2k})$$P_{2k}$

Now let
${\left|{\phi}\right\rangle}=\frac{{\left|{00}\right\rangle}+{\left|{11}\right\rangle}}{\sqrt{2}}$
be the Bell state on two qubits. Notice that we can use
${\left|{\phi}\right\rangle}$ as an ancilla to remove two bits from
$\operatorname{T}_{2\ell}$ (i.e., leaving a $\operatorname{T}_{2\ell-2}$).
However, the $\operatorname{T}_{2\ell}$ occurs in $H$ conjugated by single-
qubit gates, followed by Pauli operations. If we feed the state
$\mathcal{G}(a_{i},i)^{\dagger}\otimes\mathcal{G}(a_{j},j)^{\dagger}{\left|{\phi}\right\rangle}$
to bits $i$ and $j$, the single-qubit gates transform it to
${\left|{\phi}\right\rangle}$, it removes two bits from the
$\operatorname{T}_{2\ell}$, then it is transformed to
$P_{i}\mathcal{G}(a_{i},i)^{{\dagger}}\otimes
P_{j}\mathcal{G}(a_{j},j)^{\dagger}{\left|{\phi}\right\rangle}$. We can do the
exact same thing to $H^{-1}$, starting with
$P_{i}\mathcal{G}(a_{i},i)^{{\dagger}}\otimes
P_{j}\mathcal{G}(a_{j},j)^{\dagger}{\left|{\phi}\right\rangle}$ and going to
$\mathcal{G}(a_{i},i)^{{\dagger}}\otimes\mathcal{G}(a_{j},j)^{\dagger}{\left|{\phi}\right\rangle}$.
Then we swap the two states, and use the ancilla rule to remove them. The net
result is that we can remove any two qubits of $H$, as long as we remove the
same pair of qubits from $H^{-1}$.

Iterate this procedure to until $H$ has been reduced to just the first two
qubits, and so has $H^{-1}$. In particular, the $\operatorname{T}_{2\ell}$
gate in the middle is now a $\operatorname{T}_{2}$, which we observe is
actually a $\operatorname{SWAP}$ gate. From $H$, the remaining circuit is

$\textstyle{\times}$$\textstyle{P_{1}}$$\textstyle{\mathcal{G}(a_{i})}$$\textstyle{\times}$$\textstyle{\mathcal{G}^{-1}(a_{i})}$$\textstyle{P_{i}}$

and the inverse survives from $H^{-1}$. Remove the swaps, and observe that we
have ancillas to remove any of the remaining single-qubit gates, so we can
isolate each single-qubit gate, in particular
$P_{i}\circ\mathcal{G}^{-1}(a_{i})$, $P_{1}\circ\mathcal{G}^{-1}(a_{i})$ and
their inverses. From this point on, everything we do for $H$ can be repeated
for $H^{-1}$, which culminates in removing all the single-qubit gates, at
which point we can remove the extra $\operatorname{T}_{2\ell}$ gate easily.
Hence, let us ignore $H^{-1}$.

Now let us repeat the procedure above starting from the $\mathfrak{C}(G)$, but
stop short of applying the ancilla rule to qubit $2k+j$. The result is the
first circuit depicted below, which is then simplified by an application of
the swap rule, and gates $P_{i}\circ\mathcal{G}^{-1}(a_{i})$ and
$P_{1}\circ\mathcal{G}^{-1}(a_{i})$:

$\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
0.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry@@#!@\cr&&&&&&&\\\&&&&&&&\\\&&&&&&&\crcr}}}\ignorespaces{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 10.00002pt\raise
0.0pt\hbox{\hbox{\kern
3.00003pt\raise-2.00446pt\hbox{$\textstyle{b_{j}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
47.33855pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
71.75868pt\raise
0.0pt\hbox{\hbox{\kern-3.8889pt\raise-2.5pt\hbox{$\textstyle{\times}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
98.51215pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
125.26561pt\raise 0.0pt\hbox{\hbox{\kern
3.00003pt\raise-2.00446pt\hbox{$\textstyle{b_{j}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
148.18402pt\raise 0.0pt\hbox{\hbox{\kern
3.00003pt\raise-2.51443pt\hbox{$\textstyle{P_{1}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
174.79314pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
0.0pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
16.45921pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
32.91843pt\raise-26.50894pt\hbox{\hbox{\kern
3.00003pt\raise-2.5pt\hbox{$\textstyle{\mathcal{G}(a_{i})}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
71.75868pt\raise-26.50894pt\hbox{\hbox{\kern-3.8889pt\raise-2.5pt\hbox{$\textstyle{\times}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
81.7587pt\raise-26.50894pt\hbox{\hbox{\kern
3.00003pt\raise-3.06888pt\hbox{$\textstyle{\mathcal{G}^{-1}(a_{i})}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
131.72481pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
148.61938pt\raise-26.50894pt\hbox{\hbox{\kern
3.00003pt\raise-2.49333pt\hbox{$\textstyle{P_{i}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
174.79314pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
0.0pt\raise-53.66928pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
10.00002pt\raise-53.66928pt\hbox{\hbox{\kern
3.00003pt\raise-2.65584pt\hbox{$\textstyle{b_{j}^{*}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
47.33855pt\raise-53.66928pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
71.75868pt\raise-53.66928pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
98.51215pt\raise-53.66928pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
125.26561pt\raise-53.66928pt\hbox{\hbox{\kern
3.00003pt\raise-2.65584pt\hbox{$\textstyle{b_{j}^{*}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
148.27069pt\raise-53.66928pt\hbox{\hbox{\kern
3.00003pt\raise-1.94888pt\hbox{$\textstyle{P_{j}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
174.79314pt\raise-53.66928pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces}}}}\ignorespaces}\;\;\;\rightarrow\;\;\;\vbox{\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
0.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry@@#!@\cr&&&&\\\&&&&\\\&&&&\crcr}}}\ignorespaces{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 10.00002pt\raise
0.0pt\hbox{\hbox{\kern
3.00003pt\raise-2.5pt\hbox{$\textstyle{\mathcal{G}(a_{i})}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
48.84027pt\raise 0.0pt\hbox{\hbox{\kern
3.00003pt\raise-2.00446pt\hbox{$\textstyle{b_{j}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
71.75868pt\raise 0.0pt\hbox{\hbox{\kern
3.00003pt\raise-3.06888pt\hbox{$\textstyle{\mathcal{G}^{-1}(a_{i})}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
115.2656pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
0.0pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
17.96094pt\raise-26.50894pt\hbox{\hbox{\kern
3.00003pt\raise-2.00446pt\hbox{$\textstyle{b_{j}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
55.29947pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
88.51213pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
115.2656pt\raise-26.50894pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
0.0pt\raise-53.04039pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
17.96094pt\raise-53.04039pt\hbox{\hbox{\kern
3.00003pt\raise-2.65584pt\hbox{$\textstyle{b_{j}^{*}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
48.84027pt\raise-53.04039pt\hbox{\hbox{\kern
3.00003pt\raise-2.65584pt\hbox{$\textstyle{b_{j}^{*}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
80.29425pt\raise-53.04039pt\hbox{\hbox{\kern
3.00003pt\raise-1.94888pt\hbox{$\textstyle{P_{j}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
115.2656pt\raise-53.04039pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces}}}}\ignorespaces}$

Notice that the topmost qubit is stabilized by
$\mathcal{G}^{-1}(a_{i}){\left|{b_{j}}\right\rangle}$, from which we can see
that the ancilla rule immediately generates $\operatorname{CNOT}(b_{j})$.
Finally, we exploit the identity,

$T_{2k}(P\otimes I^{\otimes 2k-1})T_{2k}=I\otimes P^{\otimes 2k-1},$

which holds up to a global phase. We have the following chain of consequences.

pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$$P_{1}$$\mathcal{G}(a_{2})$$\mathcal{G}^{-1}(a_{2})$$P_{2}$$\mathcal{G}(a_{3})$$\mathcal{G}^{-1}(a_{3})$$P_{3}$$\vdots$$\vdots$$\vdots$$\mathcal{G}(a_{2k})$$\mathcal{G}^{-1}(a_{2k})$$P_{2k}$

$\rightarrow$
pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$$\mathcal{G}(a_{2})$$P_{1}$$\mathcal{G}^{-1}(a_{2})$$P_{2}$$\mathcal{G}(a_{3})$$P_{1}$$\mathcal{G}^{-1}(a_{3})$$P_{3}$$\vdots$$\vdots$$\vdots$$\vdots$$\mathcal{G}(a_{2k})$$P_{1}$$\mathcal{G}^{-1}(a_{2k})$$P_{2k}$
$\rightarrow$
pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$pt$\operatorname{T}_{2k}$

The last implication comes from the fact that we already generated
$P_{i}\circ\mathcal{G}^{-1}(a_{i})$ and $P_{1}\circ\mathcal{G}^{-1}(a_{i})$. ∎

##  10 Completing the Classification

The final step in the classification is to demonstrate that the classes we
have defined are in fact the only classes that exist.

######  Theorem 19.

Let $\mathcal{S}$ be some class in the classification, and let $G$ be a
collection of gates. Suppose $\left<G\right>\subseteq\mathcal{S}$, but
$\left<G\right>\not\subseteq\mathcal{S}^{\prime}$ for all
$\mathcal{S^{\prime}}$ below $\mathcal{S}$ in our classification. That is, for
all such $\mathcal{S}^{\prime}$ there exists a gate $g\in G$ such that
$g\notin\mathcal{S}^{\prime}$. Then $\left<G\right>=\mathcal{S}$.

###### Proof.

Let $\mathcal{C}$ be the class generated by $G$. There is a very general
strategy for proving that the given class $\mathcal{C}$ is indeed one already
stated in the classification. For each invariant described in Section 6 that
$\mathcal{C}$ fails to preserve, the universal construction generates a
(simple) gate which also fails to satisfy that invariant by Theorem 18.
Composing these gates using identities from Section 8, one can show that they
always generate some class in the classification. This would complete the
classification.

Nevertheless, we now give a complete sequence of tests to identify the class
$\mathcal{C}$. First consider the degeneracy invariant. If $\mathcal{C}$ is
degenerate, then by Lemma 6 we can decompose each gate into a circuit of
single-qubit gates and swap gates. Each single-qubit gate can be extracted
with an appropriate tensor product of single-qubit ancillas on the rest. The
question therefore reduces to the simple group-theoretic question about the
subgroups of single-qubit gates, which can be solved straightforwardly.
Therefore, assume $\mathcal{C}$ is non-degenerate.

Let us separate the remainder of the proof based on the $X$-, $Y$-,
$Z$-preserving invariant. Let $P$, $Q$, and $R$ be distinct Pauli operations.

Suppose first that $\mathcal{C}$ is $X$-, $Y$-, and $Z$-preserving. Because
every generalized CNOT gate violates one such invariant and $\mathcal{C}$ is
non-degenerate, some gate in $\mathcal{C}$ must have a tableau with multiple
invertible elements in some row. Therefore, from the universal construction we
extract a $\operatorname{T_{4}}$ gate. By Lemma 11, we have then that
$\mathcal{C}=\left<\operatorname{T_{4}},\mathcal{P}\right>$.

Suppose now that $\mathcal{C}$ is $P$\- and $Q$-preserving but not
$R$-preserving. Because $\mathcal{C}$ is non-degenerate, it must generate
either a heterogeneous CNOT gate, a homogenous CNOT gate, or a
$\operatorname{T_{4}}$ gate. We wish to show that $\mathcal{C}$ contains a
$C(P,Q)$ gate, which would imply $\mathcal{C}=\left<C(P,Q),\mathcal{P}\right>$
as desired. First notice that no homogeneous CNOT gate can be $P$\- and
$Q$-preserving. Suppose then that from the universal construction,
$\mathcal{C}$ generates a $\operatorname{T_{4}}$ gate but no $C(P,Q)$ gate.
Since $\operatorname{T_{4}}$ is $R$-preserving, there must be some single-
qubit gate from the universal construction that is not $R$-preserving but is
$P$\- and $Q$-preserving. It is straightforward to check that no such single-
qubit gate exists, which implies that $\mathcal{C}$ must contain a $C(P,Q)$
gate.

Suppose now that $\mathcal{C}$ is $P$-preserving but not $Q$\- and
$R$-preserving. This is the most involved case and will require several more
subdivisions. It will be first useful to notice that all $P$-preserving
single-qubit gates are also $P$-orthogonal. Therefore, if $\mathcal{C}$
violates the $P$-orthogonality invariant, then the universal construction must
produce some non-degenerate gate which violates $P$-orthogonality. Therefore,
$\mathcal{C}$ contains a $C(P,Q)$ gate or a $C(P,R)$ gate. If it contains both
via the universal construction, then indeed
$\mathcal{C}=\left<C(P,Q),\operatorname{R}_{P},\mathcal{P}\right>$ by Lemma
10. Otherwise, the universal construction produces some single-qubit gate
which is $P$-preserving but not $Q$\- and $R$-preserving. Since all
heterogeneous CNOT gates generate the Pauli group as well, the class of single
qubit gates must therefore contain an $\operatorname{R}_{P}$ gate.

Therefore let us now assume that $\mathcal{C}$ is $P$-orthogonal but not
$P$-degenerate. Since $\mathcal{C}$ is $P$-orthogonal, it cannot contain a
$C(P,Q)$ or $C(P,R)$. However, because $\mathcal{C}$ is $P$-preserving, it
must contain a $\operatorname{T_{4}}$ gate; otherwise it would be
$P$-degenerate. Once again, since the $\operatorname{T_{4}}$ gate generates
the Pauli group and $\mathcal{C}$ is neither $Q$\- nor $R$-preserving, the
class of single qubit gates must contain an $\operatorname{R}_{P}$ gate,
implying that
$\mathcal{C}=\left<\operatorname{T_{4}},\operatorname{R}_{P},\mathcal{P}\right>$.

Let us then assume that $\mathcal{C}$ is $P$-degenerate. Since $\mathcal{C}$
is non-degenerate, it must contain a $C(P,P)$ gate. There are five
$P$-degenerate classes, which are determined by their single-qubit subgroup.
Indeed, the five $P$-degenerate classes correspond to the five $P$-preserving
single-qubit classes containing $P$. Unlike previous cases, such a diversity
of classes exists because $C(P,P)$ does not suffice to generate the Pauli
group on its own. Once again, the universal construction allows us to extract
the $C(P,P)$ gate along with single-qubit gates which suffice to generate
every gate in $\mathcal{C}$. It is straightforward to see why the entire
single-qubit group must arise from the universal construction. If not, then
each gate in $\mathcal{C}$ could be constructed by gates in a smaller class, a
contradiction. This completes the classification of all gates that are
$P$-preserving but not $Q$\- and $R$-preserving.

Assume then that $\mathcal{C}$ is neither $P$-,$Q$-, nor $R$-preserving. If it
is egalitarian, then it must contain a $\operatorname{T_{4}}$ gate because it
is non-degenerate. Therefore it must contain a single-qubit gate that is
egalitarian, but not $P$-,$Q$-, or $R$-preserving. The only such single-qubit
class which contains the Pauli group is $\left<\Gamma,\mathcal{P}\right>$.
Therefore $\mathcal{C}=\left<\operatorname{T_{4}},\Gamma,\mathcal{P}\right>$.

Finally, let us then assume that $\mathcal{C}$ also violates the egalitarian
invariant. That is, $\mathcal{C}$ violates every invariant so should be equal
to the class of all stabilizer operations. Suppose the only non-degenerate
gate generated by the universal construction is the $\operatorname{T_{4}}$
gate. In particular, this implies that class of single-qubit gates generated
by $\mathcal{C}$ must not be $X$-, $Y$-, $Z$-preserving, nor egalitarian.
Therefore the single-qubit class of $\mathcal{C}$ must contain _all_ single-
qubit gates. Therefore by Lemma 14 we generate all stabilizer circuits.

Similarly, Lemma 10 implies that if the set of generalized CNOT gates
generated by the universal construction fails to be $P$-, $Q$-, or
$R$-preserving, then $\mathcal{C}$ generates a single-qubit gate which fails
to be $P$-, $Q$-, or $R$-preserving, respectively. Combining this fact with
Lemma 13 implies that $\mathcal{C}=\mathsf{ALL}$. ∎

######  Corollary 20.

Given any set of gates $G$, there is a subset $S\subseteq G$ of at most three
gates such that $\left<S\right>=\left<G\right>$.

###### Proof.

The result follows by a careful accounting of the gates used in the proof of
Theorem 19. We give the argument only for the degenerate classes.

Let $G$ be a set of single-qubit gates with $S\subseteq G$ and such that
$\left<S\right>=\left<G\right>$. Suppose $S=\\{g_{1},\ldots,g_{k}\\}$ with
$k>3$. We can assume that each generator in the set $S$ is not contained in
the subgroup generated by the other elements in $S$, otherwise we could remove
that generator, reducing the size of $S$. Therefore, there is an ascending
chain of subgroups $G_{0}\subset G_{1}\subset\ldots\subset G_{k}$, where
$G_{i}=\left<g_{1},\ldots,g_{i}\right>$. Observing Figure 4, the longest
ascending chain has length four, and in particular, all chains of length four
end at the class of _all_ single-qubit gates. Furthermore, that chain must
contain one of the subgroups $\left<\mathcal{P},\operatorname{R}_{X}\right>$,
$\left<\mathcal{P},\operatorname{R}_{Y}\right>$, or
$\left<\mathcal{P},\operatorname{R}_{Z}\right>$, which we can assume is
$\left<\mathcal{P},\operatorname{R}_{Z}\right>$ by symmetry.

Since not all gates in $S$ are Pauli operators, we can assume that $g_{1}$ is
not a Pauli operator. In particular,
$g_{1}\in\left<\mathcal{P},\operatorname{R}_{Z}\right>\setminus\left<\mathcal{P}\right>$.
That is, $g_{1}$ is one of $\operatorname{R}_{Z}$,
$\operatorname{R}_{Z}^{\dagger}$, $\theta_{X+Y}$, or $\theta_{X-Y}$.
Therefore, the class $G_{2}$ is either $\left<\operatorname{R}_{Z}\right>$ or
$\left<Z,\theta_{XY}\right>$. Clearly,
$g_{4}\notin\left<\mathcal{P},\operatorname{R}_{Z}\right>$ (i.e., it does not
preserve the $Z$-basis), and by a simply case analysis, it is easy to see that
$\left<g_{1},g_{2},g_{4}\right>$ is the entire class of single-qubit
operations. ∎

##  11 Open Problems

Our classification of stabilizer gates resolves an open problem of Aaronson et
al. [3], but leaves their central question, the classification of arbitrary
quantum gates, completely open. It is unclear whether there is another piece
of the full quantum gate classification that can be peeled off. Other discrete
quantum gate sets are known, but none are known to have the rich structure and
entanglement of stabilizer gates (aside from conjugated stabilizer gates). So
we ask: are there other interesting discrete gate sets, and can they be
classified like stabilizer gates?

Another source of open problems is the choice of ancilla rule. As discussed,
we permit ancillas initialized to quantum states. We have determined that the
classification continues to hold under a stabilizer ancilla model if the
following conjecture holds:

######  Conjecture 21.

For any single-qubit stabilizer gate $g$, there exists a stabilizer state
${\left|{\psi}\right\rangle}$ and circuit of $\operatorname{SWAP}$ gates $\pi$
such that $g\circ\pi{\left|{\psi}\right\rangle}={\left|{\psi}\right\rangle}$.

This is sufficient to remove single-qubit gates in situations where we would
otherwise use an eigenstate.

For many single-qubit gates, there is a trivial stabilizer state which
stabilizes it. For instance, $X$ is stabilized by ${\left|{+}\right\rangle}$,
$\operatorname{R}_{Z}$ is stabilized by ${\left|{0}\right\rangle}$, and many
other single-qubit stabilizer gates are conjugate to one of these cases. Now
consider the gate $\theta_{X+Z}$, whose eigenstates (unnormalized)
$(1\pm\sqrt{2}){\left|{0}\right\rangle}+{\left|{1}\right\rangle}$ are _not_
stabilizer states. How then, given the gate $\theta_{X+Z}\otimes\theta_{X+Z}$,
does one generate the gate $\theta_{X+Z}$ which acts only on one qubit? Han-