begin{tabular}{| l | c l c |} \hline
Rule name  & \hspace{.5em} & Rule \hspace{11em} & \hspace{.5em}  \\ \hline
Spider fusion  && \parbox[c][5em]{0pt}{\input{figures/z_spider_fusion.tikz}} & \\ \hline
Identity rule  && \parbox[c][2em]{0pt}{\input{figures/identity_rule.tikz}} & \\ \hline
Color change  && \parbox[c][5em]{0pt}{\input{figures/color_change.tikz}} & \\ \hline
$\pi$-copy  && \parbox[c][5em]{0pt}{\input{figures/pi_copy_rule.tikz}} & \\ \hline
\end{tabular}
\caption{Rules for the ZX-calculus. In every rule, red and green nodes can be exchanged.}
\label{tab:zx_rules}
\end{table}

We will primarily use the ZX-calculus to determine the affect of the $X$ and $Y$ measurements on graph states.\footnote{Using the ZX-calculus to analyze measurement-based computation is not new. For instance, see references \cite{cd:2011_zx} and \cite{duncan:2010}.} First, one can verify that the following diagram represents a $\operatorname{CZ}$ gate:
\begin{center}
\input{figures/csign.tikz}
\end{center}
Using this fact and the spider fusion rule from \Cref{tab:zx_rules}, it is easy to prove the following lemma:
\begin{lemma}
\label{lem:zx_graph_state}
Every graph state $\ket{G}$ for $G = (V,E)$ is represented by a $|V|$-qubit ZX-calculus diagram where two qubits in the diagram are connected by edge with a Hadamard gate if and only if they share an edge in the graph $G$.
\end{lemma}
For instance, the triangle graph on three vertices is represented by the diagram
\begin{center}
\input{figures/triangle_graph.tikz}
\end{center}

We now want to show the effect of $X$ and $Y$ measurements on the graph.  In the subsequent discussion, we will actually refer to \emph{projections}, rather than measurements.  Let us briefly justify this choice.  First, recall that Pauli measurement on a single qubit for Pauli $P \in \ensuremath\mathcal{P}_1$ projects the state onto either the $+1$ or $-1$ eigenspace of $P$.  The key observation is that the net result of the measurement can always be described by applying a Pauli operator, projecting the qubit onto the $+1$ eigenspace, and applying another Pauli operator.  There are two cases:  if the Pauli measurement would have resulted in a projection into the $+1$ eigenspace, then do nothing; if it would have projected into the $-1$ eigenspace, then apply Pauli $Q$ such that $Q \neq P$, project into the $+1$ eigenspace, and apply Pauli $Q$ again.  This is justified by the following equation:
$$
\frac{\pfont{I} - P}{2} = Q \( \frac{\pfont{I} + P}{2} \) Q.
$$
To be clear, in the following $ZX$-calculus diagrams we will make no explicit mention of the Pauli $Q$ operation mentioned above, which is required to accurately describe the state if the measurement projects the state onto the $-1$ eigenspace.  However, using the $\pi$-copy rule from \Cref{tab:zx_rules}, these phases can easily\footnote{On the other hand, such calculations will not be ``easy'' for sufficiently weak machines, which in some sense is the basis for the hardness results of sections \ref{sec:nc1} and \ref{sec:parityL}.} be pushed to the end of the circuit.  These phases determine the Pauli correction operation which appears in \Cref{thm:rbb_mbqc} (and, in fact, all measurement-based computation schemes).

With this out of the way, let us discuss measurements in the context of the ZX-calculus.  To measure a qubit in the $X$-basis, we will apply the green projection generator in \Cref{tab:zx_generators} to the corresponding qubit.  To measure in the $Y$-basis, we first apply a $\pi/2$-phase gate to the corresponding qubit, and then project onto the $X$-basis.  Since
\begin{center}
\input{figures/measurement_simplification.tikz}
\end{center}
by the spider fusion rule, we get that each measurement corresponds to a $Z$-projection with $\alpha = 0$ for $X$ measurements, and a $Z$-projection with $\alpha = \pi/2$ for $Y$ measurements. 

\section{Measurement-Based Quantum Computation Gadgets}
\label{app:mbqc_gadgets}

The goal of this appendix is to construct explicit graph states and show how measuring them can \emph{efficiently} implement desired operations. That is, we describe \emph{measurement-based computation gadgets} (or simply \emph{measurement gadgets}) which implement various Clifford operations under appropriate measurements. 

\begin{definition}
	A \emph{measurement-based computation gadget} (or just \emph{measurement gadget} in this paper) is a graph state $\ket{G}$ with $m$ distinguished \emph{input} qubits and $m$ distinguished \emph{output} qubits. To use the gadget, we connect the graph state $\ket{G}$ to an \emph{input register} (not to be confused with the input qubits) $\ket{\psi}$ and an \emph{output register} (also not to be confused with the output qubits), initially in state $\ket{+}^{\otimes m}$, with $\operatorname{CZ}$ gates. Specifically, starting with state $\ket{\psi} \otimes \ket{G} \otimes \ket{+}^{\otimes m}$, we apply $\operatorname{CZ}$ gates from the $i$th qubit of the input state to the $i$th input qubit, and from the $i$th output qubit to the $i$th qubit of the output register. We measure the qubits of $\ket{\psi}$ in the $X$-basis and each qubit of $\ket{G}$ in the $X$ or $Y$ basis. The output register contains some state $P U \ket{\psi}$, where $U$ is a unitary depending on the choice of measurement bases, and $P$ is a Pauli operation depending on the measurement outcomes (and bases). 
\end{definition}

Functionally, a measurement gadget implements one of a family of unitaries, depending on the choice of measurement bases. Naturally, we expect to be able to compose measurement gadgets as one would compose gates.  For instance, if we put two measurement gadgets beside each other (the disjoint union of the graphs), this gives a gadget which implements $U_1 \otimes U_2$ for any unitaries $U_1, U_2$ implemented by the original gadgets. Similarly, we can compose measurement gadgets sequentially (assuming they have the same number of input/output qubits) as follows, by a procedure of Raussendorf, Browne, and Briegel.

\begin{lemma}[Raussendorf, Browne, and Briegel \cite{rbb:2003_mbc}]
	\label{lem:mbqc_composition}
	Let $\mathcal G_1$ and $\mathcal G_2$ be two measurement gadgets. Let $\mathcal G$ be the gadget with $\mathcal G_1$, followed by a layer of $m$ \emph{buffer qubits}, followed by $\mathcal G_2$, and connect the $i$th buffer qubit to the $i$th output qubit of $\mathcal G_1$ and the $i$th input qubit of $\mathcal G_2$. The input qubits of $\mathcal{G}_1$ and the output qubits of $\mathcal{G}_2$ become the input and output qubits of $\mathcal{G}$. 
	
	For any unitary $U_1$ implemented by $\mathcal{G}_1$ with measurements $M_1$, and any unitary $U_2$ implemented by $\mathcal{G}_2$ with measurements $M_2$, we can implement $U_2 U_1$ with $\mathcal{G}$ by measuring $M_1$ on the vertices from $\mathcal{G}_1$, $M_2$ on the vertices from $\mathcal{G}_2$, and $X$ on the new vertices. 
\end{lemma}
\begin{proof}[Sketch]
	This appears to be trivial: the output bits of $\mathcal G_1$ are literally the same as the input bits for $\mathcal G_2$. However, when we execute $\mathcal G$, we apply the $\operatorname{CZ}$ gates from the buffer qubits to the input of $\mathcal G_2$ at the beginning rather than after $\mathcal G_1$