# Extending the Graph Formalism to Higher-Order Gates

A. Khesin  K. Ren  MIT

###### Abstract

We present an algorithm for efficiently simulating a quantum circuit in the
graph formalism. In the graph formalism, we represent states as a linear
combination of graphs with Clifford operations on their vertices. We show how
a $\mathcal{C}_{3}$ gate such as the Toffoli gate or $\frac{\pi}{8}$ gate
acting on a stabilizer state splits it into two stabilizer states. We also
describe conditions for merging two stabilizer states into one. We discuss
applications of our algorithm to circuit identities and finding low stabilizer
rank representations of magic states.

##  I Introduction

Quantum logic gates play a crucial role in quantum informatics. These gates
allow a quantum circuit to behave predictably when presented with a certain
quantum state by transforming this state into a desirable one. While classical
computations could all be carried out using a Turing machine, the physical
reality of how classical circuits are implemented makes it useful to describe
classical circuits in terms of gates. Specifically, the NAND gate behaves
similarly to a transistor and is therefore “fundamental”, in some sense. The
NAND gate is in fact universal, meaning all Boolean circuits can be
constructed solely out of NAND gates.

It is harder to describe the concept of universality in the quantum case
because quantum operations are continuous and not discrete. Notably, if we
only limit ourselves to using a finite number of universal quantum gates, we
will never be able to describe all possible unitary operations that can be
done, as we could only ever make a countable number of circuits. Universal
quantum computation must be able to approximate unitary quantum operations
with arbitrary precision.

As Aharonov showed in aha , a small set of gates, such as the Clifford and
Toffoli gates, allows for universal quantum computation. It is thus desirable
to not only be able to classically simulate how these gates act on quantum
states, but also to do it quickly and in a small amount of space. Notably, it
is worth asking how much time and space will this simulation take as a
function of the number of qubits being simulated as well as of the number of
operations performed.

There is a classification of operations on quantum states called the Clifford
hierarchy. We call Pauli gates and Clifford gates $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$, respectively. The Toffoli gate is in a larger set of gates
called $\mathcal{C}_{3}$. We wish to be able to efficiently approximate
universal circuits by simulating the action of $\mathcal{C}_{3}$ gates on
quantum states. We can accomplish this by considering only a particular set of
quantum states called stabilizer states, which can be represented efficiently.
While Clifford gates take stabilizer states to stabilizer states,
$\mathcal{C}_{3}$ gates take stabilizer states to linear combinations of two
stabilizer states.

In this paper, we show how to simulate this action efficiently both in terms
of time and space, as well as how to reduce the complexity of the
representation by showing how to combine some linear combinations of two
stabilizer states into one. We accomplish this by providing explicit formulas
and algorithms, and we state the conditions in which the above can be applied.
These results have important implications for questions regarding quantum
computation and stabilizer rank.

In Sections II, III, and IV we introduce definitions of the Clifford
hierarchy, stabilizer rank, and graph states, respectively. In Section V we
state our results and show examples of how to apply them in Section VI. The
proof of the main result is in Section VII and the runtime in computed in
Section VIII.

##  II Clifford Hierarchy

We now introduce a family of sets of matrices known as the Clifford hierarchy.
These are key to the study of quantum circuits.

We begin by defining a fundamental set of unitary matrices, the Pauli group.
Let $n$ be the number of qubits we are simulating.

######  Definition II.1.

Let $\mathcal{P}$, the Pauli group, be the group generated by the unitary
matrices {$X$, $Y$, $Z$}, where $X=\left(\begin{smallmatrix}0&1\\\
1&0\end{smallmatrix}\right)$, $Y=\left(\begin{smallmatrix}0&-i\\\
i&0\end{smallmatrix}\right)$, and $Z=\left(\begin{smallmatrix}1&0\\\
0&-1\end{smallmatrix}\right)$. We also let $I=\left(\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}\right)$. $\mathcal{P}$ is on the first level of the
Clifford hierarchy, so we also denote it $\mathcal{C}_{1}$.

The matrices $X$, $Y$, and $Z$ are called Pauli matrices, and have many nice
properties.

######  Remark II.2.

The Pauli matrices obey $XY=iZ$, as well as similar expressions obtained by
cyclically permuting $X$, $Y$, and $Z$. Also note that the matrices $X$, $Y$,
and $Z$ are often denoted $\sigma_{x}$, $\sigma_{y}$, and $\sigma_{z}$ or
$\sigma_{1}$, $\sigma_{2}$, and $\sigma_{3}$, respectively.

In general, if we wish to denote a gate $U$ applied to a specific qubit $a$
(or pair of qubits $a,b$), we will write $U_{a}$ (respectively, $U_{a,b}$) and
it is implied that the tensor product is taken with identity matrices applied
to all other qubits. Furthermore, when writing tensor products of several
matrices, we will usually omit the $\otimes$ sign for brevity.

Since unitary matrices represent quantum gates, it is useful to examine the
conjugation of one matrix by another. In other words, if a circuit contains
the matrix $A$, we want to know whether the matrix $B$ commutes with it, and
if it doesn’t, what is the value of $C$ in the expression $BA=AC$.
Equivalently, we want to know what $B$ turns into if we “pull it through” $A$.
We find that $C=A^{-1}BA$.

It is now natural to examine the normalizer of $\mathcal{P}$, the set of
matrices $C$ through which we can pull a Pauli matrix and be sure to produce a
Pauli matrix.

######  Definition II.3.

Let $\mathcal{C}_{2}$, the Clifford group, be the normalizer of $\mathcal{P}$,
given by $\mathcal{C}_{2}=\\{U\in\mathcal{U}(2^{n})\mid
U^{-1}\mathcal{P}^{\otimes n}U=\mathcal{P}^{\otimes n}\\}$.

As Gottesman shows in got , $\mathcal{C}_{2}$ is generated by the Hadamard
gate, $H=\frac{1}{\sqrt{2}}\left(\begin{smallmatrix}1&1\\\
1&-1\end{smallmatrix}\right)$, the phase gate
$S=\left(\begin{smallmatrix}1&0\\\ 0&i\end{smallmatrix}\right)$, and any
controlled Pauli gate, such as the controlled-$X$ gate,
$CX=\left(\begin{smallmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{smallmatrix}\right)$, which applies the $X$ gate to the target
qubit if the control qubit is in the $\left|1\right\rangle$ state. When using
subscripts to indicate the qubits to which the gate is applied, we write the
control qubit first. The above matrix shows $CX_{1,2}$.

######  Example II.4.

The SWAP gate is a $\mathcal{C}_{2}$ gate formed by $CX_{1,2}\cdot
CX_{2,1}\cdot CX_{1,2}$, which swaps the values of qubits 1 and 2 and is
written as $\left(\begin{smallmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{smallmatrix}\right)$.

######  Definition II.5.

We define a local Clifford operation as any of the 24 matrices in $\langle
H,S\rangle$, the set of matrices generated by multiplying a sequences of $H$
and $S$ matrices, which are all of the possible Clifford operations that can
be applied to a single qubit.

We can further extend this idea and ask ourselves which operators map Pauli
gates to the Clifford group under conjugation. This leads us to the following
definition.

######  Definition II.6.

For $k\in\mathbb{N}$, let $\mathcal{C}_{k}$, the operators on level $k$ of the
Clifford hierarchy, be defined recursively as
$\mathcal{C}_{k}=\\{U\in\mathcal{U}(2^{n})\mid
U^{-1}\mathcal{P}U\subseteq\mathcal{C}_{k-1}\\}$, with the base case being
$\mathcal{P}=\mathcal{C}_{1}$. Note that the Clifford group is indeed
$\mathcal{C}_{2}$ under this definition. Furthermore, we note that for $k>2$,
these operators do not form a group.

As we mentioned earlier, we can achieve universal quantum computation by just
using Clifford gates and the Toffoli gate, which is in $\mathcal{C}_{3}$.

######  Remark II.7.

To apply a controlled operation $U$, the matrix used is
$\left(\begin{smallmatrix}I&0\\\ 0&U\end{smallmatrix}\right)$. The operation
$U$ is controlled by qubit 1 and applied to remaining qubits. This operation
is denoted $CU$, which can be nested if $U$ is already a controlled operation.
Note that applying a control operation to a gate raises its level in the
Clifford hierarchy. For the rest of the paper, we use the convention that if a
controlled operation $CU_{a,b}$ is applied to qubits $a$ and $b$, then when
$b=a$ this operation is equal to $U_{a}$.

The gates in $\mathcal{C}_{3}$ that we study are
$T=\left(\begin{smallmatrix}1&0\\\
0&e^{\frac{i\pi}{4}}\end{smallmatrix}\right)$, $CH$, $CS$, $CCX$, $CCZ$,
CSWAP. These are the $\frac{\pi}{8}$ gate, the controlled-$H$ gate, the
controlled-$S$ gate, the Toffoli or controlled-controlled-$X$ gate, the
controlled-controlled-$Z$ gate, and the controlled-SWAP gate, respectively.
For ease of notation we denote the set of these six $\mathcal{C}_{3}$
operators as $\mathcal{S}$.

##  III Stabilizer Rank

When doing quantum simulations, it is convenient to start the simulation with
a particular state, such as $\left|0\right\rangle^{\otimes n}$, and then
proceed from there. In fact there is a specific finite subset of all $n$-qubit
states which is convenient to work with. For this we introduce the stabilizer
formalism.

######  Definition III.1.

We say that a state $\left|\psi\right\rangle$ is a stabilizer state if there
exists a set of $n$ independent operators $U\in\mathcal{P}^{\otimes n}$ such
that $U\left|\psi\right\rangle=\left|\psi\right\rangle$. We say that the
operators $U$ stabilize $\left|\psi\right\rangle$.

######  Remark III.2.

If $\left|\psi\right\rangle$ is a stabilizer state and $U\in\mathcal{C}_{2}$,
then $U\left|\psi\right\rangle$ will also be a stabilizer state. Furthermore,
any stabilizer state can be expressed as $U\left|0\right\rangle^{\otimes n}$
for some $U\in\mathcal{C}_{2}$.

One of the things that make stabilizer states useful is that they can be
represented efficiently. An $n$-qubit state requires $2^{n}$ components to
represent as a state vector, but the $n\times n$ stabilizer matrix of Pauli
matrices that identify the stabilizer state only requires $O(n^{2})$ space.
This exponential improvement is particularly important if the number of qubits
is large.

Bearing our goal of universal quantum computation in mind, the natural
question that arises now that we have defined stabilizer states is how do
$\mathcal{C}_{3}$ gates act on these states. Immediately, we see that if
$\left|\psi\right\rangle$ is a stabilizer state and $U\in\mathcal{C}_{3}$,
then $U\left|\psi\right\rangle$ will not always be a stabilizer state, as that
is only true for gates in $\mathcal{C}_{2}$. In fact, representing the action
of several $\mathcal{C}_{3}$ gates on $\left|\psi\right\rangle$ is of great
interest as this lets us perform universal quantum computation, magic state
distillation, and much more. For now, we need to introduce new terminology to
talk about the outputs of $\mathcal{C}_{3}$ gates on stabilizer states.

######  Definition III.3.

As defined by bss , let the stabilizer rank $\chi(\left|\psi\right\rangle)$ of
an $n$-qubit state $\left|\psi\right\rangle$ be the smallest number $k$ of
stabilizer states $\left|\phi_{i}\right\rangle$ needed to write
$\left|\psi\right\rangle=\sum\limits_{i=1}^{k}c_{i}\left|\phi_{i}\right\rangle$.
Note that $\chi(\left|\psi\right\rangle)\geq 1$ with equality iff
$\left|\psi\right\rangle$ is a stabilizer state. Also we observe that
$\chi(\left|\psi\right\rangle)\leq 2^{n}$, since the standard basis vectors
are all stabilizer states.

We will later show that if $\left|\psi\right\rangle$ is a stabilizer state and
$U\in\mathcal{S}$ is one of the $\mathcal{C}_{3}$ gates, then we can always
write $U\left|\psi\right\rangle$ as a linear combination of no more than 2
stabilizer states. In other words, $\chi(U\left|\psi\right\rangle)\leq 2$.

This is a very important point, as this means that we can represent the action
of a $\mathcal{C}_{3}$ gate in a circuit as a linear combination of two
stabilizer states. Since matrix multiplication is additive, a second
$\mathcal{C}_{3}$ gate would act on both parts independently. This means that
we have reduced the problem of finding out how a series of $\mathcal{C}_{3}$
gates acts on a stabilizer state, to learning the behaviour of just one. The
cost we pay for this is that our memory system must be able to store a linear
combination of stabilizer states.

Presently, this means that applying $m$ $\mathcal{C}_{3}$ gates will result in
a linear combination of $2^{m}$ stabilizer states, which we would like to
avoid. What we focus on is detecting when a linear combination of two
stabilizer states can be merged into one. By applying such a merging operation
after every application of a $\mathcal{C}_{3}$ gate, we can massively reduce
the exponential growth in the space required to represent our state. However,
with our current representation of stabilizer states, this merging operation
would require us to identify when a linear combination of two stabilizer
matrices can be merged and produce a stabilizer matrix of the sum. We are not
currently aware of a method that would allow us to do this, which is why we
have to turn to a different representation of stabilizer states.

##  IV Graph States

A lot of work in quantum cryptography has been done using codes based on
graphs. Similar techniques allow us to adapt graphs for our purposes.

######  Definition IV.1.

A graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges
$E\subseteq V\times V$ connecting those vertices. In this paper we always take
$V$ to be the set of $n$ qubits numbered from $1$ to $n$. By $\text{nbhd}(a)$
we denote the neighbourhood of $a$, the set of all vertices $b$ such that
$(a,b)\in E$.

We can associate a specific stabilizer state with each graph.

######  Definition IV.2.

Let the graph state of a graph $G$, $\left|G\right\rangle$, be given by the
state stabilized by the operators
$g_{i}=X_{i}\prod\limits_{j\in\text{nbhd}(i)}Z_{j}$, $\forall i\in V$. Note
that $\left|G\right\rangle$ is a stabilizer state.

However, not all stabilizer states can be expressed as graph states, which
means we need to supplement our graphs with additional information. As Van de
Nest et. al. show in vdn , any stabilizer state can be expressed as a graph
state with local Clifford operations performed on the vertices (see Definition
II.5). This means that any stabilizer state can be denoted by
$U\left|G\right\rangle$ where $U\in\langle H,S\rangle$ and $G$ is a graph.
Storing such a graph takes $O(1)$ additional space per qubit, as the number of
local Clifford operations is fixed. Storing the entire graph as an adjacency
list takes $O(nd)$ space where $d$ is the average degree of the graph.

Now what we have to do is figure out when and how we can merge a linear
combination of two graphs into one.

##  V Statement of results

We now present our main result. Let $\mathcal{S}$ be
$\\{T,CS,CH,CCZ,CCX,\textit{CSWAP}\\}$, a collection of $\mathcal{C}_{3}$
gates.

######  Theorem V.1.

Given an operator $C\in\mathcal{S}$ and a state $U\left|G\right\rangle$ with
largest degree $d$, we can find two states $U_{1}\left|G_{1}\right\rangle$ and
$U_{2}\left|G_{2}\right\rangle$ such that
$CU\left|G\right\rangle=U_{1}\left|G_{1}\right\rangle+U_{2}\left|G_{2}\right\rangle$
in runtime $O(nd)$, where $d$ is the average degree of $G$.

We will prove Theorem V.1 by means of the following algorithm, generalizing
Prop. 1 of heb .

######  Proposition V.2.

Let $A=\text{nbhd}(1)\cup\\{1\\}$, and let $B$ be a set including $1$. Let $k$
be an integer. Then

$\frac{1}{\sqrt{2}}\left(I+i^{k}\prod_{j\in
B}Z_{j}\right)\left|G\right\rangle\\\ =H_{1}Z_{1}\prod_{x\in A,y\in
A}CS_{x,y}^{k}\prod_{x\in A,y\in B}CZ_{x,y}\left|G\right\rangle.$ (1)

(Note the convention from Remark II.7.)

Note that the expression in Proposition V.2 may contain a $CS_{x,y}$ operator,
which is a $\mathcal{C}_{3}$ gate that we are not allowed to apply to a graph.
We note that the product of such terms has terms $x\in A$ and $y\in A$. Thus,
for every term $x=a\neq y=b$, we will apply both $CS_{a,b}$ and $CS_{b,a}$
which multiply to $CZ_{a,b}$, the toggling of an edge. Meanwhile, if $x=a=y$,
then by our convention $CS_{a,a}=S_{a}$, which we are also allowed to apply.

We will describe the algorithm to prove Theorem V.1. First, Table 1 allows us
to decompose gates in $\mathcal{S}$ into the sum of two products of projectors
and $\mathcal{C}_{2}$ gates:

$\mathbf{\mathcal{C}_{3}}$ Gate | Decomposition
---|---
T | $\frac{1}{2}(I+Z)\phantom{I}+\frac{1}{2}e^{\frac{i\pi}{4}}(I-Z)\phantom{S}$
CS | $\frac{1}{2}(I+Z)I+\phantom{e^{\frac{i\pi}{4}}}\frac{1}{2}(I-Z)S$
CH | $\phantom{H}\frac{1}{2}(I+Z)I+\phantom{e^{\frac{i\pi}{4}}}\frac{1}{2}(I-Z)H\phantom{S}$
CCZ | $III-\frac{1}{4}(I-Z)(I-Z)(I-Z)$
CCX | $III-\frac{1}{4}(I-Z)(I-Z)(I-X)$
CSWAP | $III-\frac{1}{4}(I-Z)\otimes(II-ZZ)\cdot(II-XX)$

Table 1: A decomposition of the $\mathcal{C}_{3}$ gates we examined into a sum
of two products of projectors and $\mathcal{C}_{2}$ gates. Note that all
tensor products have been removed for brevity except for that in the final
entry, to highlight the distinction between matrix product and tensor product.

Here, a projector is a term of the form $I+P$, where $P\in\mathcal{P}^{n}$.
The projectors have the nice property that conjugation by a local Clifford
operator gives another projector. For example,

$H(I+Z)H=I+X.$ (2)

Thus, for any local Clifford gate $U$ and projector $P$, we have

$PU\left|\psi\right\rangle=UP^{\prime}\left|\psi\right\rangle,$ (3)

where $P^{\prime}$ is another projector. With the local Clifford operations
out of the way, we can now apply our merging algorithm to
$P^{\prime}\left|\psi\right\rangle$. Splitting $P^{\prime}=P_{1}P_{2}\dots
P_{k}$, a product of projectors, we will apply $P_{k},P_{k-1},\dots,P_{1}$ in
order to $\left|\psi\right\rangle$. Now we need to outline how to apply a
single projector $P$ to $\left|\psi\right\rangle$.

If $P$ is a product of $Z$ gates, then we can directly apply the merging
algorithm. Otherwise, we convert $Y=iXZ$ to replace all $Y$’s, and we can use
the identity

$X_{a}\left|G\right\rangle=\left(\prod\limits_{b\in\text{nbhd}(a)}Z_{b}\right)\left|G\right\rangle$
(4)

to convert all $X$ gates to $Z$ gates on other qubits. This identity is valid
because $X_{a}\prod\limits_{b\in\text{nbhd}(a)}Z_{b}$ is a stabilizer for the
graph state $\left|G\right\rangle$. This operation might cause $Z$ gates to
appear on other qubits that still had $X$ gates that needed to be applied to
the graph. In this case, we use the anti-commutativity of the Pauli matrices
to fix the order. Thus, we can make sure there are only $Z$ gates left, and we
can apply the merging algorithm. The application of $P_{1}$ is thus another
stabilizer state, and then we can apply $P_{2}$, $P_{3}$, and so on. This
proves Theorem V.1.

##  VI Examples

One important concern is that our algorithm behaves well with circuit
identities. For example, applying two $CCX$ gates gives the identity, but each
$CCX$ would turn one stabilizer state into two, so that we end up with four
stabilizer states. A robust algorithm would find a way to merge or otherwise
annihilate these four stabilizer states such that only one remains. This is
the content of the next two examples, which deal with the identities $CS\cdot
CS=CZ$ and $CCX\cdot CCX=III$. In both cases, we should expect the output to
be a single stabilizer state. The third example is related, in which we show
that the stabilizer rank of the 2-qubit magic state $TT\left|++\right\rangle$
is 2 and not 4.

###  VI.1 CS

Start with a stabilizer state $\left|\psi\right\rangle=U\left|G\right\rangle$.
Then

$CS\left|\psi\right\rangle=\frac{1}{2}\left((I+Z)I+(I-Z)S\right)U\left|G\right\rangle.$
(5)

If we apply $CS$ again then we get

$CZ\left|\psi\right\rangle=\frac{1}{2}\left((I+Z)I+(I-Z)S\right)^{2}U\left|G\right\rangle.$
(6)

Now, we use the identity $(I+Z)(I-Z)=0$ and $(I+Z)^{2}=2(I+Z)$ to simplify
this to

$CZ\left|\psi\right\rangle=\left((I+Z)I+(I-Z)Z\right)U\left|G\right\rangle$
(7)

We should have four stabilizer states, but two of them (corresponding to the
cross terms) collapsed to zero. We can now perform merges on
$(I+Z)U\left|G\right\rangle$ and $(I-Z)U\left|G\right\rangle$. According to
the algorithm, we should first make them into

$U\left(I\pm i^{k}\prod_{q\in B}Z_{q}\right)\left|G\right\rangle.$ (8)

Without loss of generality, let $1\in B$. Then the output of the algorithm
will be two stabilizer states $U_{1}\left|G^{\prime}\right\rangle$ and
$U_{2}\left|G^{\prime}\right\rangle$, where

$U_{1}=U_{2}\prod_{a\in A}Z_{a}.$ (9)

The extra $Z_{a}$ terms come from the powers of $CS$ in Proposition V.2. Thus,
we can merge $U_{1}\left|G^{\prime}\right\rangle$ and
$U_{2}\left|G^{\prime}\right\rangle$ into a single final state. As expected,
two $CS$ gates produce a single stabilizer state.

###  VI.2 CCX

Start with a stabilizer state $\left|\psi\right\rangle=U\left|G\right\rangle$.
Then

$CCX\left|\psi\right\rangle=\\\
\left(III-\frac{1}{4}(I-Z)(I-Z)(I-X)\right)U\left|G\right\rangle.$ (10)

Apply $CCX$ again to get

$\left|\psi\right\rangle=\left(III-\frac{1}{4}(I-Z)(I-Z)(I-X)\right)^{2}U\left|G\right\rangle.$
(11)

Let $U=(I-Z)(I-Z)(I-X)$. Then $U^{2}=8U$. Hence

$\left(I-\frac{1}{4}U\right)^{2}=I-\frac{1}{2}U+\frac{1}{16}U^{2}=I.$ (12)

We thus get the desired result.

To sum up, after the first $CCX$ we get two stabilizer states. After the
second, we get four states, of which three combine to zero.

###  VI.3 Magic states

We can simulate the application of $T$ gates. Consider
$T_{1}T_{2}\left|++\right\rangle$, where $\left|++\right\rangle$ is the graph
state of the empty graph on 2 vertices. As expected, one application of the
algorithm leads to two stabilizer states:

$T_{1}\left|++\right\rangle=\frac{1}{\sqrt{2}}H_{1}\left|++\right\rangle+\frac{1}{\sqrt{2}}e^{\frac{i\pi}{4}}H_{1}Z_{1}\left|++\right\rangle.$
(13)

Applying the algorithm again, we get four stabilizer states:

$T_{2}T_{1}\left|++\right\rangle=\frac{1}{2}H_{1}H_{2}\left|++\right\rangle+\\\
\frac{1}{2}e^{\frac{i\pi}{4}}H_{1}H_{2}Z_{2}\left|++\right\rangle+\frac{1}{2}e^{\frac{i\pi}{4}}H_{1}H_{2}Z_{1}\left|++\right\rangle+\\\
\frac{i}{2}H_{1}H_{2}Z_{1}Z_{2}\left|++\right\rangle.$ (14)

We can apply our merge on the first and fourth states, and the second and
third states, to get

$T_{2}T_{1}\left|++\right\rangle=\frac{1}{\sqrt{2}}S_{1}H_{2}\left|G\right\rangle+\frac{1}{\sqrt{2}}e^{\frac{\pi
i}{4}}H_{1}Z_{1}\left|G\right\rangle,$ (15)

where $G$ is connected on two vertices, so $\left|G\right\rangle$ is
$CZ\left|++\right\rangle$. We obtain a decomposition into two stabilizer
states, which agrees with the stabilizer rank of $2$ found in bss .

##  VII Proof of Proposition V.2

###  VII.1 An initial simplification

We now show that if we prove Proposition V.2 for the case of $k\in\\{0,1\\}$,
then the $k+2$ case follows. Let $A^{\prime}=A\backslash\\{1\\}$ and
$B^{\prime}=B\backslash\\{1\\}$. We assume that for $k\in\\{0,1\\}$, the
equation in Proposition V.2 holds. Then, we use the following facts:

  1. A.

$H_{1}$ commutes with $Z_{p}$ for $p\neq 1$, and $H_{1}Z_{1}H_{1}=X_{1}$;

  2. B.

Equation 1, the merge for the case $k$,

  3. C.

Equation 4, that allows us to convert $X_{a}$ to $Z_{b}$’s on
$\text{nbhd}(a)$.

$H_{1}Z_{1}\prod_{x\in A,y\in A}CS_{x,y}^{k+2}\prod_{p\in A,q\in
B}CZ_{p,q}\left|G\right\rangle\\\ \overset{A}{=}X_{1}\prod_{p\in
A^{\prime}}Z_{p}^{k}H_{1}Z_{1}\prod_{p\in A,q\in A}CS_{p,q}^{k}\prod_{p\in
A,q\in B}CZ_{p,q}\left|G\right\rangle\\\ \overset{B}{=}X_{1}\prod_{p\in
A^{\prime}}Z_{p}^{k}\frac{1}{\sqrt{2}}\left(I+i^{k}\prod_{q\in
B}Z_{q}\right)\left|G\right\rangle\\\ =\prod_{p\in
A^{\prime}}Z_{p}^{k}\frac{1}{\sqrt{2}}\left(I-i^{k}\prod_{q\in
B}Z_{q}\right)X_{1}\left|G\right\rangle\\\ \overset{C}{=}\prod_{p\in
A^{\prime}}Z_{p}^{k}\frac{1}{\sqrt{2}}\left(I-i^{k}\prod_{q\in
B}Z_{q}\right)\prod_{p\in A^{\prime}}Z_{p}^{k}\left|G\right\rangle\\\
=\frac{1}{\sqrt{2}}\left(I+i^{k+2}\prod_{q\in
B}Z_{q}\right)\left|G\right\rangle$ (16)

Thus, we need to show this where $k\in\\{0,1\\}$.

###  VII.2 Outline of Proof

To prove Proposition V.2, we need to verify that the input state and the
output state have the same stabilizer group and global phase.

We remark that a similar result is given as Proposition 1 in heb . However,
they only prove the first of these claims. In the following, let $\zeta$ be
the CZ’s and $\sigma$ be the CS’s in Equation 1.

###  VII.3 Same stabilizer group

We first consider $k=0$. Let $\left|G\right\rangle$ be stabilized by
$g_{1},g_{2},\dots,g_{n}$. Let
$\left|\psi\right\rangle=\left(I+\prod\limits_{j\in
B}Z_{j}\right)\left|G\right\rangle$. Then applying the local Clifford
operators in the RHS of Equation 1 transforms the stabilizers by conjugation
into $g_{1}^{\prime},g_{2}^{\prime},\dots,g_{n}^{\prime}$. Thus, we know that
$g_{1}^{\prime}$ through $g_{n}^{\prime}$ stabilize the RHS of Equation 1. We
will later prove they also stabilize $\left|\psi\right\rangle$ by first
proving three claims. Define $A^{\prime}=A\backslash\\{1\\}$ and
$B^{\prime}=B\backslash\\{1\\}$.

  1. 1.

$g_{1}^{\prime}=\prod\limits_{j\in B}Z_{j}$.

  2. 2.

If $m\notin A$, then $g_{m}^{\prime}$ stabilizes $\left|G\right\rangle$.

  3. 3.

If $m\in A^{\prime}$, then $g_{1}^{\prime}g_{m}^{\prime}$ stabilizes
$\left|G\right\rangle$.

Before we prove the claims, we should mention a fact. The action of $CZ_{a,b}$
on a stabilizer $g_{k}$ is trivial (i.e. doesn’t affect the stabilizer) if
$k\neq a$ or $k\neq b$, and it is multiplication by $Z_{b}$ if $k=a$, and
multiplication by $Z_{a}$ if $k=b$.

To prove Claim 1, we compute the action of $H_{1}Z_{1}\zeta$ on $g_{1}$. This
is represented in the following equation.

$g_{1}^{\prime}=(-Z_{1}X_{1})\cdot\prod\limits_{p\in
A^{\prime}}Z_{p}\prod\limits_{q\in B^{\prime}}Z_{q}\\\
\cdot(-1)\cdot\left(X_{1}\prod\limits_{p\in
A^{\prime}}Z_{p}\right)=\prod_{q\in B}Z_{q}.$ (17)

All terms except the first and last are the action of $\zeta$:

  * •

the $CZ_{1,q}$ and $CZ_{p,1}$ multiply $g_{1}$ by $Z_{q}$ or $Z_{p}$,
respectively,

  * •

the $CZ_{p,q}$ for $p,q\neq 1$ do nothing,

  * •

the $CZ_{1,1}$ is conjugation by $Z_{1}$, which turns $X_{1}$ into $-X_{1}$,
hence the $-1$.

The first term represents the action of $H_{1}Z_{1}$, which turns the $X_{1}$
into a $-Z_{1}$ (hence the multiplication by $-Z_{1}X_{1}$).

Claim 2 has two cases: $m\in B$ and $m\notin B$.

For $m\notin B$, we have $g_{m}^{\prime}=g_{m}$, because neither $\zeta$ nor
$H_{1}Z_{1}$ affects $g_{m}$.

For $m\in B$, the action of $\zeta$ is just $\prod_{p\in A}Z_{p}$, since
$p\notin A$. Note that the first entry in $g_{m}$ was $I_{1}$, which is now
converted to $Z_{1}$. The action of $H_{1}Z_{1}$ converts the $Z_{1}$ to
$X_{1}$. Thus $g_{m}^{\prime}=(X_{1}Z_{1})\prod_{p\in
A}Z_{p}g_{m}=g_{1}g_{m}$, which stabilizes $\left|G\right\rangle$.

Claim 3 has two cases: $m\in B$ and $m\notin B$.

For $m\notin B$, the action of $\zeta$ gives $\prod_{q\in B}Z_{q}g_{m}$. Note
that the first qubit is $I_{1}$ because the edge $(1,m)$ is toggled off.
Hence, $H_{1}Z_{1}$ acts trivially. Thus, $g_{m}^{\prime}=\prod_{q\in
B}Z_{q}g_{m}$, and so $g_{1}^{\prime}g_{m}^{\prime}=g_{m}$.

For $m\in B$, the action of $\zeta$ gives

$-\prod_{p\in A}Z_{p}\prod_{q\in B}Z_{q}g_{k}.$ (18)

Note that the first qubit is $Z_{1}$ because the edge $(1,m)$ is toggled
twice, and hence is still on. Thus, $H_{1}Z_{1}$ acts non-trivially, and we
get

$g_{m}^{\prime}=-(X_{1}Z_{1})\prod_{p\in A}Z_{p}\prod_{q\in B}Z_{q}g_{m}$ (19)

and so (since $X_{1}$ anticommutes with $Z_{1}$):

$g_{1}^{\prime}g_{m}^{\prime}=X_{1}\prod_{p\in
A^{\prime}}Z_{p}g_{m}=g_{1}g_{m}.$ (20)

This proves Claim 3. Now we will prove the $g_{i}^{\prime}$ stabilize
$\left|\psi\right\rangle$. First, rewrite
$\left|\psi\right\rangle=(I+g_{1}^{\prime})\left|G\right\rangle$. Thus,
$g_{1}^{\prime}$ stabilizes $\left|\psi\right\rangle$ because
$g_{1}^{\prime}(I+g_{1}^{\prime})=I+g_{1}^{\prime}$. Also, for $m\notin A$, we
have $g_{m}^{\prime}$ stabilizes $\left|\psi\right\rangle$ because
$g_{m}^{\prime}$ commutes with $g_{1}^{\prime}$ and

$g_{m}^{\prime}\left(I+g_{1}^{\prime}\right)\left|G\right\rangle=\left(I+g_{1}^{\prime}\right)g_{m}^{\prime}\left|G\right\rangle=\left(I+g_{1}^{\prime}\right)\left|G\right\rangle.$
(21)

Finally, for $m\in A$,

$g_{m}^{\prime}\left(I+g_{1}^{\prime}\right)\left|G\right\rangle=\left(I+g_{1}^{\prime}\right)g_{1}^{\prime}g_{m}^{\prime}\left|G\right\rangle=\left(I+g_{1}^{\prime}\right)\left|G\right\rangle.$
(22)

This completes $k=0$.

###  VII.4 The case $k=1$

Suppose $k=1$. We first note that

$i\prod_{q\in B}Z_{q}\left|G\right\rangle=-Y_{1}X_{1}\prod_{q\in
B^{\prime}}Z_{q}\left|G\right\rangle\\\ =-Y_{1}\prod_{q\in
B^{\prime}}Z_{q}\prod_{p\in A^{\prime}}Z_{p}\left|G\right\rangle\\\
=-Y_{1}\prod_{q\in B}Z_{q}\prod_{p\in A}Z_{p}\left|G\right\rangle.$ (23)

We have the following claims.

  1. 1.

$\displaystyle g_{1}^{\prime}=-Y_{1}\prod_{q\in B}Z_{q}\prod_{p\in A}Z_{p}$.

  2. 2.

If $m\notin A$, then $g_{m}^{\prime}$ stabilizes $\left|G\right\rangle$.

  3. 3.

If $m\in A^{\prime}$, then $g_{1}^{\prime}g_{m}^{\prime}$ stabilizes
$\left|G\right\rangle$.

We show $\displaystyle\left(I-Y_{1}\prod_{q\in B}Z_{q}\prod_{p\in
A}Z_{p}\right)\left|G\right\rangle$ is stabilized by $g_{m}^{\prime}$, in a
similar way to the case $k=0$.

Before doing the computations, we observe that $S$ commutes with $Z$, so the
only non-trivial action of $S$ is converting an $X$ to a $Y$. This we
represent by $Y_{m}X_{m}$ when appropriate.

The proof of Claim 1 follows the same way as in the $k=0$ case.

$g_{1}^{\prime}=(Y_{1}X_{1})\cdot\prod_{p\in A^{\prime}}Z_{p}\\\
\cdot\prod_{p\in A^{\prime}}Z_{p}\prod_{q\in B^{\prime}}Z_{q}\cdot(-1)\cdot
X_{1}\prod_{p\in A^{\prime}}Z_{p}\\\ =-Y_{1}\prod_{q\in
B^{\prime}}Z_{q}\prod_{p\in A^{\prime}}Z_{p}=-Y_{1}\prod_{q\in
B}Z_{q}\prod_{p\in A}Z_{p}$ (24)

The second line is the action of $\zeta$ on $g_{1}$, and the first is the
action of $\sigma$ and $H_{1}Z_{1}$. The only $X$ that an $S$ acts on is
$X_{1}$, which we write as $Y_{1}X_{1}$. $H_{1}Z_{1}$ commutes with $Y_{1}$ so
$H_{1}$ acts trivially.

Claim 2 follows the same way as when $k=0$.

Claim 3 has two cases: $m\in B$ and $m\notin B$.

For $m\notin B$, the action of $\zeta$ gives $\prod_{q\in B}Z_{q}g_{m}$, while
the action of $\sigma$ gives

$(Y_{m}X_{m})\prod_{p\in A\backslash\\{m\\}}Z_{p}\prod_{q\in B}Z_{q}g_{m}.$
(25)

Note that the operation on the first qubit is $Z_{1}$ because the edge $(1,m)$
is toggled twice, so it is on. Thus, $H_{1}Z_{1}$ acts non-trivially, and

$g_{m}^{\prime}=(X_{1}Z_{1}Y_{m}X_{m})\prod_{p\in
A\backslash\\{m\\}}Z_{p}\prod_{q\in B}Z_{q}g_{m}.$ (26)

As a result,

$g_{1}^{\prime}g_{m}^{\prime}=-Y_{1}\prod_{q\in B}Z_{q}\prod_{p\in A}Z_{p}\\\
(X_{1}Z_{1}Y_{m}X_{m})\prod_{p\in A-\\{m\\}}Z_{p}\prod_{q\in
B}Z_{q}g_{m}=g_{m}.$ (27)

For $m\in B$, the action of $\zeta$ on $g_{m}$ gives $\prod_{p\in
A}Z_{p}\prod_{q\in B}Z_{q}g_{m}$, while the action of $\sigma$ gives

$-(Y_{m}X_{m})\prod_{p\in A\backslash\\{m\\}}Z_{p}\cdot\prod_{p\in
A}Z_{p}\prod_{q\in B}Z_{q}g_{m}\\\ =i\prod_{q\in B}Z_{q}g_{m}.$ (28)

Note that the operation on the first qubit is $I_{1}$ because the edge $(1,m)$
is toggled thrice, but was on originally (since $m\in A$) and hence is now
off. Thus, $H_{1}Z_{1}$ acts trivially, $g_{1}^{\prime}=i\prod_{q\in
B}Z_{q}g_{m}$, and

$g_{1}^{\prime}g_{m}^{\prime}=-Y_{1}\prod_{q\in B}Z_{q}\prod_{p\in
A}Z_{p}\cdot i\prod_{q\in B}Z_{q}g_{m}=g_{1}g_{m}.$ (29)

###  VII.5 Same global phase

We now prove that the two sides of Equation 1 have the same global phase. Let
$c=\frac{1}{\sqrt{2^{n}}}$. We apply $\left<0\right|=\left<00\dots 0\right|$
to both sides. Also define $\left<1\right|=\left<10\dots 0\right|$. On the
LHS, the $\prod Z$ acts on the $\left<0\right|$ trivially, since
$\left|0\right\rangle$ is a $+1$ eigenstate of $Z_{p}$ for all $p$.
Furthermore, since $\displaystyle\left|G\right\rangle=\prod_{(a,b)\in
E}CZ_{a,b}\left|+\right\rangle$ where $E$ is the edge set of $G$, and since
$CZ_{a,b}$ stabilizes $\left<0\right|$ and $\left<1\right|$, we have

$\left<0\right|\prod_{(a,b)\in
E}CZ_{a,b}\left|+\right\rangle=\left<0|+\right>=c,$ (30)
$\left<1\right|\prod_{(a,b)\in
E}CZ_{a,b}\left|+\right\rangle=\left<1|+\right>=c.$ (31)

Thus, $\left<0|G\right>=\left<1|G\right>=c$, so

$\left<0\left|\frac{1}{\sqrt{2}}\left(I+i^{k}\prod
Z\right)\right|G\right>=\frac{1+i^{k}}{\sqrt{2}}\cdot c.$ (32)

For the RHS, we note that $\left|0\right\rangle$ is a $+1$ eigenstate of $Z$,
$CZ$, and $CS$. We then have

$\left<0\left|Z_{1}\prod CS_{x,y}^{k}\prod CZ_{x,y}\right|G\right>=c.$ (33)
$\left<1\left|Z_{1}\prod CS_{x,y}^{k}\prod CZ_{x,y}\right|G\right>=i^{k}\cdot
c.$ (34)

This is since $\left|10\dots 0\right\rangle$ is a $-1$, $i$, and $+1$
eigenstate of $Z_{1}$, $S_{1}$, everything else, respectively. Note the two
$Z_{1}$’s in the above product; one written as $CZ_{1,1}$, which verifies
Equation 34. Thus,

$\left<0\left|H_{1}Z_{1}\prod CS_{x,y}^{k}\prod
CZ_{x,y}\right|G\right>=\frac{1+i^{k}}{\sqrt{2}}\cdot c.$ (35)

In summary, we proved that applying $\left<0\right|$ to both sides gives the
same nonzero result (since $k\neq 2$), which means the global phases are
equal. This proves the correctness of our algorithm.

##  VIII Runtime

Consider the action of a $\mathcal{C}_{3}$ gate $C$ on stabilizer state
$U\left|G\right\rangle$. The steps of our algorithm are:

  * •

Express $C$ as a sum of two products of projectors $D+E$ and $\mathcal{C}_{2}$
gates, as in Table 1.

  * •

Form the conjugate $D^{\prime}=U^{-1}DU$.

  * •

Convert all $X$’s and $Y$’s to $Z$’s.

  * •

Apply the merging algorithm in Proposition V.2.

The main contributors to the runtime are the last two steps. If $n$ is the
number of qubits and $d$ is the average degree of $\left|G\right\rangle$, we
claim that our average runtime is $O(nd)$. The first two steps above take
$O(n)$ time since $|\langle H,S\rangle|=24$. Converting an $X$ or $Y$ on a
qubit to $Z$’s, which must be done for each of $n$ qubits, requires $d$
applications of $Z$ on average, hence has $O(nd)$ runtime. Lastly, applying
the gates in the algorithm takes $O(|A|\cdot|A|+|A|\cdot|B|)$. However, on
average we have $|A|=d$ and $|B|=n$, so we get $O(d^{2}+dn)$. Since $d<n$, we
get runtime $O(nd)$.

##  IX Conclusions

We showed how to simulate $\mathcal{C}_{3}$ circuits on stabilizer states. We
use a decomposition of $\mathcal{C}_{3}$ operators into a sum of projectors
and a merging algorithm that combines two states. We showed robustness of our
algorithm with circuit identities, and we also derived a decomposition of the
magic state $TT\left|++\right\rangle$ in two stabilizer states, in accordance
with the known results. As further research, we can look at how our algorithm
performs when computing higher-qubit magic states. We can also look to derive
more cases where merging two states is possible besides the ones we found.
Finally, we can look at the implications of our $\mathcal{C}_{3}$ circuit
simulation algorithm for universal quantum computation.

##  X Acknowledgements

The authors are grateful to Professor Isaac Chuang for suggesting the research
question and fruitful discussions as well as to Professor Peter Shor for
helpful comments and encouragement.

## References

  * (1) Aharonov, D. A simple proof that Toffoli and Hadamard are quantum universal, arXiv:quant-ph/0301040 (2003).
  * (2) Gottesman, D. A theory of fault-tolerant quantum computation, Phys. Rev. A 57, 127–137 (1998).
  * (3) Bravyi, S., Smith, G., & Smolin, J. A. Trading Classical and Quantum Computational Resources, Phys. Rev. X 6, 021043 (2016).
  * (4) Van den Nest, M., Dehaene, J., & De Moor, B., Graphical description of the action of local Clifford transformations on graph states, Phys. Rev. A 69, 022316 (2004)
  * (5) Hein, M., Eisert, J. & Briegel, H. J. Multi-party entanglement in graph states, Phys. Rev. A 69, 062311 (2004)