text:
\section{Introduction}
In Quantum Computation, any unitary operation can be approximated to arbitrary accuracy using $\cnot$ gates together with Hadamard, Phase, and  $\pi/8$  gates (see Figure \ref{univers} for a definition of these gates and \cite[Section 4.5.3]{2011NC} for a proof of this result). Therefore, this set of gates is often called the standard set of universal gates. When we restrict this set to Hadamard, Phase and $\cnot$ gates, we obtain the set of Clifford gates. The Pauli group $\PG$ is the group generated by the Pauli gates acting on $n$ qubits (see Figure \ref{Pauli}) and the normalizer of the Pauli Group in the unitary group $\UG$ is called the Clifford group.
In his PhD thesis \cite[Section 5.8]{1997G}, Gottesman gave a constructive proof of the fact that the Clifford gates generate the Clifford group, up to a global phase. He also introduced the stabilizer formalism \cite[Section 10.5.1]{2011NC}, which turned out to be is a very efficient tool to analyze quantum error-correction codes \cite{1997G} and, more generaly,  to describe unitary dynamics \cite[Section 10.5.2]{2011NC}. Indeed, the Gottesman-Knill theorem asserts that a stabilizer circuit (\textit{i.e.} a quantum circuit consisting only of Clifford gates) can be simulated efficiently on a classical computer (see \cite[Section 10.5.4]{2011NC} and \cite[p. 52]{1997G}).

Due to their importance in many fields of Quantum Computation, several  normal forms for stabilizer circuits were proposed over the last two decades, with the
aim of  reducing the gate count in these circuits.
The first normal proposed by Aaronson and Gottesman \cite{2004AG} was successively improved by Maslov and Roetteler \cite{2018MR}, Bravyi and Maslov \cite{2020BM} and
Duncan \textit{et.al.} \cite{2020DKPV}. These authors use decomposition methods in the symplectic group over $\F$ in dimension $2n$ (\cite{2004AG,2018MR,2020BM}) or
ZX-calculus (\cite{2020DKPV}) in order to compute the normal form. In this paper we provide two normal forms for stabilizer circuits. The first form is similar to the most recent ones (\cite{2020BM,2020DKPV}) but it is computed with a different method based on conjugation rules in the Clifford group. The second form is obtained from the first one by replacing most of the $\cz$ gates  by $\cnot$ gates.

This article is structured  as follows. Section \ref{background} is a background section on quantum circuits and Clifford gates that will guide the non-specialist reader through the rest of the paper. In Section \ref{groups} we investigate some remarkable subgroups of the Clifford Group. The precise description of these group structures allows us  to propose, in  Section \ref{NF}, a polynomial-time algorithm to compute the normal forms.

\section{Quantum circuits and Clifford gates\label{background}}
In this background section we recall classical notions about quantum circuits and Clifford gates and we also introduce the main notations used in the paper.
In Quantum Information Theory, a qubit is a quantum state that represents the basic information
storage unit. This state is described by a ket vector in the Dirac notation $\ket{\psi} = a_0 \ket{0} + a_1\ket{1}$ where $a_0$ and $a_1$ are complex numbers
such that $|a_0|^2 + |a_1|^2= 1$. The value of $|a_i|^2$ represents the probability that measurement produces
the value $i$. The states $\ket{0}$ and $\ket{1}$ form a basis of the Hilbert space $\HS\simeq \C^2$ where a one qubit quantum system evolves.
Operations on qubits must preserve the norm and are therefore described by unitary operators $U$ in the unitary group $\UG$.
In quantum computation, these operations are represented by quantum gates and a quantum circuit is a conventional representation of the sequence  of quantum gates applied to the qubit register over time. In Figure \ref{Pauli}, we recall the definition of the Pauli gates mentioned in the introduction. Notice that the states $\ket{0}$
and $\ket{1}$ are eigenvectors of the \PauliZ operator respectively associated to the eigenvalues 1 and -1, so the standard computational basis $(\ket{0},\ket{1})$ is also called the $\ZZ$-basis. Notice also that $\XX\ket{0}=1$ and $\XX\ket{1}=0$, hence the \PauliX gate is called the $\mathtt{NOT}$ gate. The phase gate $\PP$ (see Figure \ref{univers}) is defined by $\PP\ket{0}=\ket{0}$ and $\PP\ket{1}=\ii\ket{1}$. The Hadamard gate $\HH$ creates superposition as $\HH\ket{0}=\frac{1}{\sqrt2}(\ket{0}+\ket{1})$. The following usefull identities are obtained by direct computation.
\begin{align}
  &\HH^2=\XX^2=\YY^2=\ZZ^2=\II\label{involutions}\\
  &\XX\ZZ=-\ZZ\XX\label{anticom}\\
  &\YY=\ii\XX\ZZ\label{yixz}\\
  &\HH\ZZ\HH=\XX\label{conj-z-h}\\
  &\PP^2=\ZZ\\
  &\PP\XX\PP=\YY\label{conj-x-p}
\end{align}
The Pauli group for one qubit is the group generated by $\{\XX,\YY,\ZZ\}$. Any element of this group can be written uniquely under the form $\ii^{\lambda}\XX^a\ZZ^b$,
where $\lambda\in\Z_4$ and $a,b\in\F$.
\begin{figure}[h]
	\begin{center}
	\begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (24.000000, 7.500000);
\draw[color=black] (0.000000,0.000000) -- (24.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {\PauliX\ \ };
\draw (45.00, 0.00) node {$\left[\begin{array}{cc}0&1\\1&0\end{array}\right]$};
\begin{scope}
\draw[fill=white] (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (12.000000, -0.000000) node {$X$};
\end{scope}

\end{tikzpicture}\qquad\qquad
\begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (24.000000, 7.500000);
\draw[color=black] (0.000000,0.000000) -- (24.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {\PauliY\ \ };
\draw (45.00, 0.00) node {$\left[\begin{array}{cc}0&-i\\i&0\end{array}\right]$};
\begin{scope}
\draw[fill=white] (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (12.000000, -0.000000) node {$Y$};
\end{scope}
\end{tikzpicture}
\begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (24.000000, 7.500000);
\draw[color=black] (0.000000,0.000000) -- (24.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {\PauliZ\ \ };
\draw (45.00, 0.00) node {$\left[\begin{array}{cc}1&0\\0&-1\end{array}\right]$};
\begin{scope}
\draw[fill=white] (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (12.000000, -0.000000) node {$Z$};
\end{scope}

\end{tikzpicture}\vspace{-4mm}

{ \caption{ The Pauli gates \label{Pauli}}}
\end{center}
\end{figure}

A quantum system of two qubits $A$ and $B$ (also called  a two-qubit register) lives in a 4-dimensional Hilbert space $\HS_A\otimes\HS_B$ and the computational basis of this space is $((\ket{00}=\ket{0}_A\otimes\ket{0}_B,\ket{01}=\ket{0}_A\otimes\ket{1}_B,\ket{10}=\ket{1}_A\otimes\ket{0}_B,\ket{11}=\ket{1}_A\otimes\ket{1}_B))$.
If $U$ is any unitary operator acting on one qubit, a controlled-$U$ gate acts on the Hilbert space $\HS_{A}\otimes\HS_{B}$ as follows.
One of the two qubits (say qubit $A$) is the control qubit whereas the other qubit is the target qubit. If the control qubit $A$ is in the state $\ket 1$ then $U$ is applied on the target qubit $B$ but when qubit $A$ is in the state $\ket{0}$ nothing is done on qubit $B$.
The $\cnot$ gate (or $\cx$ gate) is the controlled-$\XX$ gate with control on qubit $A$ and target on qubit $B$, so the action of $\cnot$ on a two-qubit register is described by :
$\cnot\ket{00}=\ket{00}, \cnot\ket{01}=\ket{01}, \cnot\ket{10}=\ket{11}, \cnot\ket{11}=\ket{10}$ (the corresponding matrix is given in Figure \ref{univers}).
Observe that this action can be sum up by the simple formula   $\cnot\ket{xy}=\ket{x,x \oplus y}$,
where $\oplus$ denotes the XOR operator between two bits $x$ and $y$, which is also the addition in $\F$. In the same way, the reader can check that the controlled-$\ZZ$ operator  acts on a a basis vector as $\cz\ket{xy}=(-1)^{xy}\ket{xy}$.
Note that this action is invariant by switching the control and the target.
The last 2-qubit gate we need is the $\swap$ gate defined by $\swap\ket{xy}=\ket{yx}$.
\begin{figure}[h]
\ \ CNOT :\raisebox{-7mm}{
 \begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (18.000000, 22.500000);
\draw[color=black] (0.000000,15.000000) -- (18.000000,15.000000);
\draw[color=black] (0.000000,15.000000) node[left] {$A$};
\draw[color=black] (0.000000,0.000000) -- (18.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {$B$};
\draw (9.000000,15.000000) -- (9.000000,0.000000);
\begin{scope}
\draw[fill=white] (9.000000, 0.000000) circle(3.000000pt);
\clip (9.000000, 0.000000) circle(3.000000pt);
\draw (6.000000, 0.000000) -- (12.000000, 0.000000);
\draw (9.000000, -3.000000) -- (9.000000, 3.000000);
\end{scope}
\filldraw (9.000000, 15.000000) circle(1.500000pt);
\end{tikzpicture}
}
\ $\cnot=\begin{bmatrix}
  1&0&0&0\\
  0&1&0&0\\
  0&0&0&1\\
  0&0&1&0
\end{bmatrix}$\qquad
Phase :\raisebox{-3mm}{
\begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (24.000000, 7.500000);
\draw[color=black] (0.000000,0.000000) -- (24.000000,0.000000);
\begin{scope}
\draw[fill=white] (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (12.000000, -0.000000) node {$P$};
\end{scope}
\end{tikzpicture}
}\quad
$\PP=\begin{bmatrix}1&0\\0&\ii\end{bmatrix}$

\raisebox{-3mm}{
\begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (24.000000, 7.500000);
\draw[color=black] (0.000000,0.000000) -- (24.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {Hadamard\ :\ \ };
\begin{scope}
\draw[fill=white] (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (12.000000, -0.000000) node {$H$};
\end{scope}
\end{tikzpicture}
}\ \
$\HH=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$
\hspace{10mm}
$\pi/8 : $\raisebox{-3mm}{
\begin{tikzpicture}[scale=1.500000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (24.000000, 7.500000);
\draw[color=black] (0.000000,0.000000) -- (24.000000,0.000000);
\begin{scope}
\draw[fill=white] (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (12.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (12.000000, -0.000000) node {$T$};
\end{scope}
\end{tikzpicture}
}\quad
$\mathtt{T}=\begin{bmatrix}1&0\\0&\ee^{\frac{\ii\pi}{4}}\end{bmatrix}$

{ \caption{ The standard set of universal gates : names, circuit symbols and matrices. \label{univers}}}
\end{figure}

On a system of $n$ qubits, we label each qubit from 0 to $n-1$ thus following the usual convention. For coherence we also number
the lines and columns of a matrix of dimension $n$ from 0 to $n-1$ and we consider that a permutation of the symmetric group $sym$ is a bijection of $\{0,\cdots,n-1\}$. The $n$-qubit system evolves over time in the Hilbert space $\HS_0\otimes \HS_1\otimes\cdots\otimes \HS_{n-1}$ where $\HS_i$ is the Hilbert space of
qubit $i$.
In this space, a state vector of the standard computational basis is classicaly denoted by
$\ket{b}=\ket{b_0b_1\cdots b_{n-1}}$ where $b_i$ is in $\{0,1\}$. Let $(e_i)_{0\leq i< n}$ be the canonical basis of $\F^n$. It is convenient to identify the binary label  $b=b_0b_1\cdots b_{n-1}$
with the column vector vector $[b_0,\dots,b_{n-1}]^{\T}=\sum_ib_ie_i$ of $\F^n$, which is also denoted by $b$. So the standard basis is $(\ket{b})_{b\in\F^n}$.
When we apply locally a single qubit gate $U$ to qubit $i$ of a $n$-qubit register, the corresponding action on the $n$-qubit system is that of the operator
$U_i=\II\otimes\cdots\otimes\II\otimes U\otimes\II\otimes\cdots\otimes\II$
where $\otimes$ is the Kronecker product of matrices and $\II$ the identity matrix in dimension 2.
As an example, if $n=4$, $\HH_1=\II\otimes\HH\otimes\II\otimes\II$ and $\HH_0\HH_3=\HH\otimes\II\otimes \II\otimes \HH$. We also use a $n$-bit column vector notation,
\textit{e.g.} $\HH_0\HH_3=\HH_{[1,0,0,1]^{\T}}$. Observe that with this notation one has $U_i=U_{e_i}$. When $U$ is an involution (\textit{i.e.} $U^2=\II$), the group generated by the $U_i$'s is isomorphic to $\F^n$, since it is an abelian 2-group. This is the case for the Pauli and Hadamard gates but not for the phase gates. For instance
$\HH_{[1,0,0,1]^{\T}}\HH_{[0,0,1,1]^{\T}}=\HH_{[1,0,0,1]^{\T}\oplus[0,0,1,1]^{\T}}=\HH_{[1,0,1,0]^{\T}}=\HH_0\HH_2$. Note that the action of $\ZZ_i$ on $\ket{b}=\ket{b_0\cdots b_{n-1}}$ is described by
$\ZZ_i\ket{b}=(-1)^{b_i}\ket{b}\label{zi}$. Hence, if $u=[u_0,\dots,u_{n-1}]^{\T}\in\F^n$, one has
\begin{equation}
\ZZ_u\ket{b}=(-1)^{u\cdot b}\ket{b},\label{zu}
\end{equation}
where $u\cdot v=u^{\T}b$ denotes the scalar product of $u$ and $b$ in $\F^{n}$. In the same way, $\PP_i\ket{b}=\ii^{b_i}\ket{b}$, hence
\begin{equation}
\PP_u\ket{b}=\ii^{u\cdot b}\ket{b},\label{pu}
\end{equation} where we consider that vectors $u$ and $b$ are in $\Z_4^{n}$.
A $\cnot$ gate with target on qubit $i$ and control on qubit $j$ will be denoted $X_{ij}$. The reader will pay attention to the fact that our convention is the opposite of that generaly used, where $\cnot_{ij}$ denotes a $\cnot$ gate with control on qubit $i$ and target on qubit $j$. The reason for this change will apperar clearly in the proof of Theorem \ref{X-GL}. So, if $i<j$, the action of $X_{ij}$ and $X_{ji}$ on a basis vector $\ket{b}$ is given by
\begin{align}
&  X_{ij}\ket{b}=X_{ij}\ket{b_0\cdots b_i\cdots b_j\cdots b_{n-1}}=\ket{b_0\cdots b_i\oplus b_j\cdots b_j\cdots b_{n-1}}\ ,\label{xij}\\
&  X_{ji}\ket{b}=X_{ji}\ket{b_0\cdots b_i\cdots b_j\cdots b_{n-1}}=\ket{b_0\cdots b_i\cdots b_j\oplus b_i\cdots b_{n-1}}.\label{xji}
\end{align}
The $\cz$ (res. $\swap$) gate between qubits $i$ and $j$ will be denoted by $Z_{ij}$ (resp. $S_{ij}$). Notice that $Z_{ij}=Z_{ji}$ and $S_{ij}=S_{ji}$. These gates are defined by
\begin{align}
  &Z_{ij}\ket{b_0\cdots b_{n-1}}=(-1)^{b_ib_j}\ket{b}\ ,\label{zij}\\
  &S_{ij}\ket{b_0\cdots b_i\cdots b_j\cdots b_{n-1}}=\ket{b_0\cdots b_j\cdots b_i\cdots b_{n-1}}.\label{sij}
\end{align}
Observe that the $X_{ij}$, $S_{ij}$ and $\XX_i$ gates are permutation matrices while the $Z_{ij}$ and $\ZZ_i$ gates are diagonal matrices whose entries $(\alpha,\alpha)$ are equal to $1$ or $-1$. All these matrices are involutions.
We end this section by recalling 3 classical identities. They corresponds to the circuit equivalences in Figure \ref{equi}. Each identity can be proved by checking that the action of its left hand side and of its right hand side on a basis vector $\ket{b}$ is the same.
\begin{align}
  X_{ij}&=\HH_i\HH_jX_{ji}\HH_i\HH_j\label{conj-xij-h}\\
  Z_{ij}&=\HH_iX_{ij}\HH_i=\HH_jX_{ji}\HH_j\label{zijxij}\\
  S_{ij}&=X_{ij}X_{ji}X_{ij}=X_{ji}X_{ij}X_{ji}\label{sijxij}
\end{align}
The Pauli group for $n$ qubits is the group generated by the set $\{\XX_i,\YY_i,\ZZ_i\mid i=0\dots n-1\}$. Since
Identities \eqref{involutions}, \eqref{anticom} and \eqref{yixz},  any element of this group can be uniquely under the form $\ii^{\lambda}\XX_{u}\ZZ_{v}$, where $\lambda\in\Z_4$ and $u,v\in\F^n$. The multiplication in the Pauli group is given by
\begin{equation}\label{pauli-mult}
  \ii^{\lambda}X_{u}Z_{v}\ii^{\lambda'}X_{u'}Z_{v'}=\ii^{\lambda+\lambda'}(-1)^{u'\cdot v}\XX_{u\oplus u'}\ZZ_{v\oplus v'}.
\end{equation}
This identity is a consequence of \eqref{anticom}.
A stabilizer circuit for $n$ qubit is an element of the group generated by the set $\{\PP_i,\HH_i,\XX_{ij}\mid 0\leq i,j\leq n-1 \}$. This group contains the $\swap$ and $\cz$ gates since \eqref{zijxij} and \eqref{sijxij}. It also contains the Pauli group. For instance $(X_{ij}Z_{ij})^2=\ZZ_j$ (see \eqref{conj-Zij}).
In a stabilizer circuit, changes of the overall phase by a multiple of $\frac{\pi}{4}$ are possible since
\begin{equation}
(\HH_i\PP_i)^3=(\PP_i\HH_i)^3=\ee^{\ii\frac{\pi}{4}}\III.\label{hp3}
\end{equation}
This last equation can be proved by a direct computation.
\begin{figure}
$\cnot$ : \ \raisebox{-5mm}{
\begin{tikzpicture}[scale=1.200000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (111.000000, 22.500000);
\draw[color=black] (0.000000,15.000000) -- (111.000000,15.000000);
\draw[color=black] (0.000000,15.000000) node[left] {$A$};
\draw[color=black] (0.000000,0.000000) -- (111.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {$B$};
\draw (9.000000,15.000000) -- (9.000000,0.000000);
\begin{scope}
\draw[fill=white] (9.000000, 0.000000) circle(3.000000pt);
\clip (9.000000, 0.000000) circle(3.000000pt);
\draw (6.000000, 0.000000) -- (12.000000, 0.000000);
\draw (9.000000, -3.000000) -- (9.000000, 3.000000);
\end{scope}
\filldraw (9.000000, 15.000000) circle(1.500000pt);
\draw[fill=white,color=white] (24.000000, -6.000000) rectangle (39.000000, 21.000000);
\draw (31.500000, 7.500000) node {$\sim$};
\begin{scope}
\draw[fill=white] (57.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (57.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (57.000000, 15.000000) node {$H$};
\end{scope}
\begin{scope}
\draw[fill=white] (57.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (57.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (57.000000, -0.000000) node {$H$};
\end{scope}
\draw (78.000000,15.000000) -- (78.000000,0.000000);
\begin{scope}
\draw[fill=white] (78.000000, 15.000000) circle(3.000000pt);
\clip (78.000000, 15.000000) circle(3.000000pt);
\draw (75.000000, 15.000000) -- (81.000000, 15.000000);
\draw (78.000000, 12.000000) -- (78.000000, 18.000000);
\end{scope}
\filldraw (78.000000, 0.000000) circle(1.500000pt);
\begin{scope}
\draw[fill=white] (99.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (99.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (99.000000, 15.000000) node {$H$};
\end{scope}
\begin{scope}
\draw[fill=white] (99.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (99.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (99.000000, -0.000000) node {$H$};
\end{scope}
\end{tikzpicture}
}

$\cz$ :\ \raisebox{-5mm}{
\begin{tikzpicture}[scale=1.200000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (204.000000, 22.500000);
\draw[color=black] (0.000000,15.000000) -- (204.000000,15.000000);
\draw[color=black] (0.000000,15.000000) node[left] {$A$};
\draw[color=black] (0.000000,0.000000) -- (204.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {$B$};
\draw (9.000000,15.000000) -- (9.000000,0.000000);
\filldraw (9.000000, 15.000000) circle(1.500000pt);
\filldraw (9.000000, 0.000000) circle(1.500000pt);
\draw[fill=white,color=white] (24.000000, -6.000000) rectangle (39.000000, 21.000000);
\draw (31.500000, 7.500000) node {$\sim$};
\begin{scope}
\draw[fill=white] (57.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (57.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (57.000000, 15.000000) node {$H$};
\end{scope}
\draw (78.000000,15.000000) -- (78.000000,0.000000);
\begin{scope}
\draw[fill=white] (78.000000, 15.000000) circle(3.000000pt);
\clip (78.000000, 15.000000) circle(3.000000pt);
\draw (75.000000, 15.000000) -- (81.000000, 15.000000);
\draw (78.000000, 12.000000) -- (78.000000, 18.000000);
\end{scope}
\filldraw (78.000000, 0.000000) circle(1.500000pt);
\begin{scope}
\draw[fill=white] (99.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (99.000000, 15.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (99.000000, 15.000000) node {$H$};
\end{scope}
\draw[fill=white,color=white] (117.000000, -6.000000) rectangle (132.000000, 21.000000);
\draw (124.500000, 7.500000) node {$\sim$};
\begin{scope}
\draw[fill=white] (150.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (150.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (150.000000, -0.000000) node {$H$};
\end{scope}
\draw (171.000000,15.000000) -- (171.000000,0.000000);
\begin{scope}
\draw[fill=white] (171.000000, 0.000000) circle(3.000000pt);
\clip (171.000000, 0.000000) circle(3.000000pt);
\draw (168.000000, 0.000000) -- (174.000000, 0.000000);
\draw (171.000000, -3.000000) -- (171.000000, 3.000000);
\end{scope}
\filldraw (171.000000, 15.000000) circle(1.500000pt);
\begin{scope}
\draw[fill=white] (192.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\clip (192.000000, -0.000000) +(-45.000000:8.485281pt and 8.485281pt) -- +(45.000000:8.485281pt and 8.485281pt) -- +(135.000000:8.485281pt and 8.485281pt) -- +(225.000000:8.485281pt and 8.485281pt) -- cycle;
\draw (192.000000, -0.000000) node {$H$};
\end{scope}
\end{tikzpicture}
}

$\swap$ : \ \raisebox{-5mm}{
      \begin{tikzpicture}[scale=1.200000,x=1pt,y=1pt]
\filldraw[color=white] (0.000000, -7.500000) rectangle (180.000000, 22.500000);
\draw[color=black] (0.000000,15.000000) -- (180.000000,15.000000);
\draw[color=black] (0.000000,15.000000) node[left] {$A$};
\draw[color=black] (0.000000,0.000000) -- (180.000000,0.000000);
\draw[color=black] (0.000000,0.000000) node[left] {$B$};
\draw (9.000000,15.000000) -- (9.000000,0.000000);
\begin{scope}
\draw (6.878680, 12.878680) -- (11.121320, 17.121320);
\draw (6.878680, 17.121320) -- (11.121320, 12.878680);
\end{scope}
\begin{scope}
\draw (6.878680, -2.121320) -- (11.121320, 2.121320);
\draw (6.878680, 2.121320) -- (11.121320, -2.121320);
\end{scope}
\draw[fill=white,color=white] (24.000000, -6.000000) rectangle (39.000000, 21.000000);
\draw (31.500000, 7.500000) node {$\sim$};
\draw (54.000000,15.000000) -- (54.000000,0.000000);
\begin{scope}
\draw[fill=white] (54.000000, 0.000000) circle(3.000000pt);
\clip (54.000000, 0.000000) circle(3.000000pt);
\draw (51.000000, 0.000000) -- (57.000000, 0.000000);
\draw (54.000000, -3.000000) -- (54.000000, 3.000000);
\end{scope}
\filldraw (54.000000, 15.000000) circle(1.500000pt);
\draw (72.000000,15.000000) -- (72.000000,0.000000);
\begin{scope}
\draw[fill=white] (72.000000, 15.000000) circle(3.000000pt);
\clip (72.000000, 15.000000) circle(3.000000pt);
\draw (69.000000, 15.000000) -- (75.000000, 15.000000);
\draw (72.000000, 12.000000) -- (72.000000, 18.000000);
\end{scope}
\filldraw (72.000000, 0.000000) circle(1.500000pt);
\draw (90.000000,15.000000) -- (90.000000,0.000000);
\begin{scope}
\draw[fill=white] (90.000000, 0.000000) circle(3.000000pt);
\clip (90.000000, 0.000000) circle(3.000000pt);
\draw (87.000000, 0.000000) -- (93.000000, 0.000000);
\draw (90.000000, -3.000000) -- (90.000000, 3.000000);
\end{scope}
\filldraw (90.000000, 15.000000) circle(1.500000pt);
\draw[fill=white,color=white] (105.000000, -6.000000) rectangle (120.000000, 21.000000);
\draw (112.500000, 7.500000) node {$\sim$};
\draw (135.000000,15.000000) -- (135.000000,0.000000);
\begin{scope}
\draw[fill=white] (135.000000, 15.000000) circle(3.000000pt);
\clip (135.000000, 15.000000) circle(3.000000pt);
\draw (132.000000, 15.000000) -- (138.000000, 15.000000);
\draw (135.000000, 12.000000) -- (135.000000, 18.000000);
\end{scope}
\filldraw (135.000000, 0.000000) circle(1.500000pt);
\draw (153.000000,15.000000) -- (153.000000,0.000000);
\begin{scope}
\draw[fill=white] (153.000000, 0.000000) circle(3.000000pt);
\clip (153.000000, 0.000000) circle(3.000000pt);
\draw (150.000000, 0.000000) -- (156.000000, 0.000000);
\draw (153.000000, -3.000000) -- (153.000000, 3.000000);
\end{scope}
\filldraw (153.000000, 15.000000) circle(1.500000pt);
\draw (171.000000,15.000000) -- (171.000000,0.000000);
\begin{scope}
\draw[fill=white] (171.000000, 15.000000) circle(3.000000pt);
\clip (171.000000, 15.000000) circle(3.000000pt);
\draw (168.000000, 15.000000) -- (174.000000, 15.000000);
\draw (171.000000, 12.000000) -- (171.000000, 18.000000);
\end{scope}
\filldraw (171.000000, 0.000000) circle(1.500000pt);
\end{tikzpicture}
}
{ \caption{ Classical equivalences of circuits involving $\cnot$ and Hadamard gates.\label{equi}}}
\end{figure}

\section{Subgroup structures underlying stabilizer circuits\label{groups}}
We start by describing the group $\czg$ which is the group
generated by the $Z_{ij}$ gates. The set of parts of $\{\{i,j\}\mid 0 \leq i<j\leq n-1\}$ is denoted by $\BG$.
As noticed in Section \ref{background}, the  matrices $Z_{ij}$ are involutions and commute with each other since they are diagonal matrices.
So $\czg$ is isomorphic to the abelian 2-group $(\BG,\oplus)$, where $\oplus$ denotes the symmetric difference between two parts of a set (\textit{i.e.} their union minus their intersection). As a consequence, the order of $\czg$ si $2^{\frac{n(n-1)}{2}}$.
For any $B$ in $\BG$, we denote by $Z_B$ the unitary operator in $\czg$ associated to $B$. So, when $n=4$, one has for instance $Z_{\{\{0,2\},\{0,3\},\{1,2\}\}}=Z_{02}Z_{03}Z_{12}$.
With this notation, Identity \eqref{zij} can be generalized as
\begin{equation}
Z_B\ket{b}=(-1)^{\sum_{\{i,j\}\in B}b_ib_j}\ket{b}.\label{zB}
\end{equation}
To any $B$ in $\BG$ we associate a $n\times n$ $\F$-matrix whose entry $(i,j)$
is 1 if $\{i,j\}$ is in $B$. This matrix is symmetric with null entries on the diagonal and,  for convenience, we also denote it by $B$. For example $\{\{i,j\}\}$ also denotes the matrix whose entries are 0
but entries $(i,j)$ and $(j,i)$ that are 1, and $\{\}$ also denotes the null matrix. Depending on the context, it will be clear if we consider the set or the matrix.    Let $q_B$ be the quadratic form defined on $\F^n$ by
\begin{equation}
  q_B(b)=\sum_{\{i,j\}\in B}b_ib_j=\sum_{i<j}B_{ij}b_ib_j,
  \end{equation}
  where $B_{ij}$ is the entry $(i,j)$ of the matrix $B$. Then Identity \eqref{zB} can be rewritten as
\begin{equation}
  Z_B\ket{b}=(-1)^{q_{B}(b)}\ket{b}.
\end{equation}
Note that $B$ can be viewed as the matrix of the alternating (and symmetric) bilinear form associated to the quadratic form $q_B$.

In a previous work \cite{2020B}, we described  the group $\cnotg$ generated by the $X_{ij}$ gates. We recall now some results of \cite{2020B}. The special linear group on any field $K$ is generated by the set of transvection matrices. In the special case of $K=\F$, this set is reduced to the $n(n-1)$ matrices $T_{ij}=I_n + E_{ij}$, where $E_{ij}$ is the matrix with all entries 0 except the entry $(i,j)$ that is 1.  So $\GL=\SL$ is generated by the matrices $T_{ij}$. The following simple property of the $T_{ij}$ matrices will be of great use.
    \begin{prop}\label{tij-mult}
Multiplying to the left (resp. the right) any matrix $M$ by a
transvection matrix $T_{ij}$ is equivalent to add the row $j$ (resp. column $i$) to the row $i$ (resp. column $j$) in $M$.
\end{prop}
Applying Proposition \ref{tij-mult} to vector $b\in\F^n$, we can rewrite Relation \eqref{xij} as
\begin{equation}
 X_{ij}\ket{b}=\ket{T_{ij}b}.\label{xijtij}
 \end{equation}
 The above considerations lead quite naturally to the following theorem.

\begin{theo}\label{X-GL}

      The group $\cnotg$ generated by the $\cnot$ gates acting on $n$ qubits is isomorphic to $\GL$.
      The morphism $\Phi$ sending each gate $X_{ij}$ to the transvection matrix $T_{ij}$ is an explicit isomorphism.
      The order of $\cnotg$ is $2^{\frac{n(n-1)}{2}}\prod_{i=1}^n(2^i-1)$.
    \end{theo}

    \begin{proof}
      Since the matrices $T_{ij}$ generate $\GL$, it is clear that  $\Phi$ is surjective. For Identity \eqref{xijtij}, a preimage $V$ under $\Phi$ of any matrix $A$ in $\GL$ must satisfy  the relations $V\ket{b}=\ket{Ab}$ for any basis vector $\ket{b}$. Since these relations define a unique matrix $V$, $\Phi$ is injective. The order of $\GL$ is classicaly obtained by counting the number of basis of the vector space $\F^n$.
\end{proof}

The following conjugation rule between the $\cnot$ gates can be proved by checking, thanks to Identity \eqref{xij}, that the action of its left hand side and of its right hand side on any basis vector $\ket{b}$ is the same.
\begin{equation}
  X_{ij}X_{jk}X_{ij}=X_{jk}X_{ik}\quad (i,j,k \text{ distinct})\label{conj-xij-xjk}
\end{equation}
Let $\czpg$ be the group generated by the set $\{\PP_i,Z_{ij}\}$.
Any element of the group generated by the $\PP_i$ gates can be written uniquely under the form $\ZZ_a\PP_b$ where $a,b\in\F^n$.
This group is isomorphic to $(\Z_4^n,+)$, one possible isomorphism associating $\ZZ_a\PP_b$ to $2a+b$.
Hence the group $\czpg$ is isomorphic to $\Z_4^n\times\BG$. Any element in $\czpg$ can be written uniquely under the form $\ZZ_a\PP_bZ_B$ and
\begin{equation}
  \ZZ_a\PP_bZ_B\ZZ_{a'}\PP_{b'}Z_{B'}=\ZZ_{a\oplus a'\oplus bb'}\PP_{b\oplus b'}Z_{B\oplus B'},\label{czpg-mult}
\end{equation}
where $bb'$ denotes the $\F^n$-vector $\sum_ib_ib_i'e_i$.
The conjugation by the $X_{ij}$ gates in $\czpg$ obey to the 7 rules below.
Each equality can be proved by checking, thanks to Identities \eqref{zu} to \eqref{zij}, that the action of its left hand side and of its right hand side on any basis vector $\ket{b}$ is the same.
\begin{align}
  &X_{ij}Z_{ij}X_{ij} = Z_{ij}\ZZ_j\label{conj-Zij}\\
  &X_{ij}Z_{ik}X_{ij} = Z_{ik}Z_{jk}\quad (i,j,k\ \text{distinct})\label{conj-Zik}\\
  &X_{ij}Z_{pq}X_{ij} = Z_{pq}\quad (p,q\neq i)\label{conj-Zpq}\\
  &X_{ij} \ZZ_{i}X_{ij}= \ZZ_i\ZZ_j\label{conj-Zi}\\
  &X_{ij} \ZZ_{j}X_{ij}= \ZZ_j\label{conj-Zj}\\
  &X_{ij} \PP_{i}X_{ij}= \PP_i\PP_jZ_{ij}\label{conj-Pi}\\
  &X_{ij} \PP_{j}X_{ij}= \PP_j\label{conj-Pj}
\end{align}

For any $A$ in $\GL$, let $X_A=\Phi^{-1}(A)$, where $\Phi$ is the morphism defined in Theorem \ref{X-GL}. So, if $[ij]$ denotes the transvection matrix $T_{ij}$, one has $X_{ij}=X_{[ij]}$. Let us denote by $\czxpg$ the group generated by the set of gates $\{\PP_i,Z_{ij},X_{ij}\}$. As described in the following proposition, we can extend relations \eqref{conj-Zij} to \eqref{conj-Pj} to matrices of type $Z_B,\ZZ_a$ or $\PP_b$.

\begin{prop}\label{normal}
  The group $\czpg$ is a normal subgroup of $\czxpg$. The conjugation of any element of $\czpg$ by a $\cnot$ gate is described by the relations
\begin{align}
  & X_{[ij]} \ZZ_{a}X_{[ij]}= \ZZ_{[ji]a}\ ,\label{conj-Za-xij}\\
  &X_{[ij]} \PP_{b}X_{[ij]}= \ZZ_{b_ib_je_j}\PP_{[ji]b}Z_{b_i\{\{ij\}\}}\ ,\label{conj-Pb-xij}\\
  &X_{[ij]}Z_{B}X_{[ij]} = \ZZ_{B_{ij}e_j}Z_{[ji]B[ij]}\ ,\label{conj-ZB-xij}\\
  &X_AZ_BX_A^{-1}=\ZZ_{q_{B}(A^{-1})}Z_{A^{-\T}BA^{-1}}\ ,\label{conj-ZB-XA}
 \end{align}
where $A^{-\T}$ is a shorthand for $\left(A^{\T}\right)^{-1}$, $q_B$ is the quadratic form defined by $B$ and $q_B(A)$ is a shorthand for the vector $[q_B(C_0),\cdots,q_B(C_{n-1})]^{\T}$ with $C_i$ being the column $i$ of $A$.
\end{prop}

\begin{proof}
  Identities \eqref{conj-Za-xij} and \eqref{conj-Pb-xij} are direct consequences of the conjugation relations \eqref{conj-Zi}, \eqref{conj-Zj}, \eqref{conj-Pi}, \eqref{conj-Pj} and Proposition \eqref{tij-mult} applied to vectors $a$ and $b$.
  Let us prove Identity \eqref{conj-ZB-xij}.
  Let $B_i=\{\{p,q\}\in B\mid i\in\{p,q\}\}$, $B_i^{C}=B\oplus B_i$ and $B_i'=B_i\oplus B_{ij}\{\{i,j\}\}$, then $B=B_{ij}\{\{i,j\}\}\oplus B_i'\oplus B_i^C$.
  On one hand,   $[ji]B[ij]=B_{ij}[ji]\{\{i, j\}\}[ij]\oplus[ji]B_i'[ij]\oplus [ji]B_i^C[ij]$.
    %
  We check that $[ji]\{\{i, j\}\}[ij] = \{\{i, j\}\}$,
  $[ji]\{\{i, k\}\}[ij] = \{\{i, k\}, \{j, k\}\}$ when $k\neq j$ and $[ji]\{\{p, q\}\}[ij] = \{\{p, q\}\}$ when $p,q\neq i$ (recall that $\{\{p,q\}\}$ denotes the matrix in $\BG$ whose entries are 0 but entries $(p,q)$ and $(q,p)$ that are 1).
  Hence
  \begin{equation}\label{one-hand}
    Z_{[ji]B[ij]}=Z_{ij}^{B_{ij}}Z_{B_i^C}\prod_{k\in K_i}Z_{ik}Z_{jk},
    \end{equation}
  where $K_i=\{k \mid \{i,k\}\in B_i'\}$.
On the other hand, $X_{[ij]}Z_{B}X_{[ij]}=X_{[ij]}Z_{ij}^{B_{ij}}Z_{B_i'}Z_{B_i^C}X_{[ij]}$.
  So, using \eqref{conj-Zij}, \eqref{conj-Zik}
  and \eqref{conj-Zpq}, one has
  \begin{equation}\label{other-hand}
    X_{[ij]}Z_{B}X_{[ij]}=Z_{ij}^{B_{ij}}\ZZ_j^{B_{ij}}Z_{B_i^C}\prod_{k\in K_i}Z_{ik}Z_{jk}.
  \end{equation}
  As $\ZZ_j^{B_{ij}}=\ZZ_{B_{ij}e_j}$, we conclude by comparing \eqref{one-hand} and \eqref{other-hand}.
    Let us prove Identity \ref{conj-ZB-XA}. Since \ref{conj-ZB-xij} and \ref{conj-Za-xij}, it is clear that $X_AZ_BX_A^{-1}$ can be written under the form
  $\ZZ_{a}Z_{A^{-\T}BA^{-1}}$ for some $a$ in $\F^n$, so we have to prove that $a=q_B(A^{-1})$. We start from $\ZZ_{a}=X_AZ_BX_A^{-1}Z_{B'}$, where
  $B'=A^{-\T}BA^{-1}$. Let $\ket{\psi}=\ZZ_{a}\ket{e_i}$, then $\ket{\psi}=(-1)^{a_i}\ket{e_i}$.
  On the other hand, $\ket{\psi}=X_AZ_BX_A^{-1}\ket{e_i}$ since $q_{B'}(e_i)=0$ for any $B'\in\BG$. Besides, $X_A^{-1}\ket{e_i}= \ket{A^{-1}e_i}=\ket{C_i}$ where $C_i$ is the $i$th column of $A^{-1}$, hence
  $\ket{\psi}=X_AZ_B\ket{C_i}=(-1)^{q_B(C_i)}X_A\ket{C_i}=(-1)^{q_B(C_i)}\ket{e_i}$. Finally we see that $a_i= q_B(C_i)$, thus $a=q_B(A^{-1})$.
  \end{proof}

From Identity \ref{sijxij}, the gate $S_{ij}$ is in $\cnotg$ and is therefore a $X_A$ gate. Let $(ij)$ be the permutation matrix of $\GL$ associated to the transposition of $\symg$ that swaps   $i$ and $j$, then $(ij)=[ij][ji][ij]=[ji][ij][ji]$ and  $S_{ij}=X_{(ij)}$. The group generated by the $S_{ij}$ gates is a subgroup of $\cnotg$ that is isomorphic to $\symg$.
The conjugation by $S_{ij}$ is given by $S_{ij}Z_{pq}S_{ij}=Z_{\tau(p)\tau(q)}$, where $\tau$ is the transposition that swaps $i$ and $j$ (see \cite{2019BL} for further development about $\cz$ and $\swap$ gates). As in Proposition \ref{normal}, we prove that
\begin{align}
  & X_{(ij)} \ZZ_{a}X_{(ij)}= \ZZ_{(ij)a}\ , \label{conj-Za-sij}\\
  &X_{(ij)} \PP_{b}X_{(ij)}= \PP_{(ij)b}\ ,\label{conj-Pb-sij}\\
  &X_{(ij)}Z_{B}X_{(ij)} = Z_{(ij)B(ij)}.\label{conj-ZB-sij}
\end{align}

The main results of this section are summarized by the theorem that follows.
\begin{theo}\label{decompo}
  Any element of $\czxpg$ admits a unique decomposition under the form $\ZZ_a\PP_bZ_BX_A$ where $a,b\in\F^n$, $B\in\BG$, $A\in\GL$.
  The group $\czxpg$ is the semidirect product of its normal subgroup $\czpg$ with $\cnotg$ : $\czxpg=\czpg\rtimes\cnotg$.
  The order of $\czxpg$ is $2^{n(n+1)}\prod_{i=1}^n(2^i-1)$.
\end{theo}

\begin{proof}
  The existence can be proved by induction using Proposition \ref{normal} and Identity \eqref{czpg-mult}. The process is detailled below in Figure \ref{C-to-abBA} :
  let $C= \prod_{k=1}^{\ell}M_k$, where $M_k\in\{\PP_i,Z_{ij},X_{[ij]}\}$ be an element of $\czxpg$, then the form $\ZZ_a\PP_bZ_BX_A$ for $C$ is the result of
  Algorithm $\cto$  applied to $C$ and $\III$ (\textit{i.e.} $\cto(C,\III)$). Observe that the time complexity of this algorithm is only  $O(n\ell)$ since we use row and column additions instead of matrix product thanks to Proposition \ref{tij-mult}.
  Let us prove the unicity of such a decomposition.  Suppose that $\ZZ_a\PP_bZ_BX_A=\ZZ_{a'}\PP_{b'}Z_{B'}X_{A'}$. If $A\neq A'$, there exists $u\in\F^n$ such that $Au\neq A'u$. But this leads to a contradiction
  because $\ZZ_a\PP_bZ_BX_A\ket{u}=\ZZ_{a'}\PP_{b'}Z_{B'}X_{A'}\ket{u}$, so $\ZZ_a\PP_bZ_B\ket{Au}=\ZZ_{a'}\PP_{b'}Z_{B'}\ket{A'u}$, hence $\ket{Au}$ and $\ket{A'u}$ are two different basis vector that are collinear. So $A=A'$ and $\ZZ_a\PP_bZ_B=\ZZ_{a'}\PP_{b'}Z_{B'}$. If there exists $i$ such that $b_i=1$ and $b'_i=0$, then $\PP_b\ket{e_i}=\ii\ket{e_i}$
  and $\PP_{b'}\ket{e_i}=\ket{e_i}$, so $\ii\ZZ_aZ_B\ket{e_i}=\ZZ_{a'}Z_{B'}\ket{e_i}$, hence $\ii\ket{e_i}=\pm\ket{e_i}$ which is not possible. Thus $b=b'$. Finally, if $\ZZ_aZ_B=\ZZ_{a'}Z_{B'}$, we show that $a=a'$ and $B=B'$ by comparing their action on $\ket{e_i}$ and $\ket{e_i\oplus e_j}$ for any $i,j$. Since $\czpg$ is a normal subgroup of $\czxpg$, the semidirect product structure is a consequence of the existence and uniqueness of the decomposition. The order of $\czxpg$ is computed using Theorem \ref{X-GL}.
\end{proof}

\begin{figure}
    $\mathtt{INPUT}$ $(C,C')$, where

    $\qquad C$ is a circuit of $\ell$ gates under the form $\prod_{k=1}^{\ell}M_k$, where $M_k\in\{\PP_i,Z_{ij},X_{[ij]}\}$,

    $\qquad C'$ is a circuit under the form $\ZZ_a\PP_bZ_BX_A$.

  $\mathtt{OUTPUT}$ An equivalent circuit to $CC'$ under the form $\ZZ_a\PP_bZ_BX_A$.

  $\mathtt{1}\quad \mathtt{for}\ k=\ell\ \mathtt{to}\ 1\ \mathtt{do}$

  $\mathtt{2}\quad\quad \mathtt{if}\  M_k=Z_{ij}\ \mathtt{then}$

  $\mathtt{3}\quad\quad\quad B\leftarrow B \oplus\{\{i,j\}\}\ ; $

  $\mathtt{4}\quad\quad \mathtt{else\ if\ } M_k=\PP_i\ \mathtt{then}$

  $\mathtt{5}\quad\quad\quad a\leftarrow a\oplus b_ie_i\ ; \ b\leftarrow b \oplus e_i\ ; $

  $\mathtt{6}\quad\quad \mathtt{else\ }\ $\quad  // $M_k=X_{[ij]}$

  $\mathtt{7}\quad\quad\quad a\leftarrow [ji]a \oplus b_ib_je_j\oplus B_{ij}e_j\ ;\ b\leftarrow [ji]b\ ;\ B\leftarrow [ji]B[ij]\oplus b_i\{\{i,j\}\}\ ;\ A\leftarrow [ij]A\ ;$

  $\mathtt{8}\quad \mathtt{return}\ \ZZ_a\PP_bZ_BX_A$

  \caption{ Algorithm  $\cto$ \label{C-to-abBA}}
\end{figure}

Algorithm $\cto$ is one the main tools we use in the next section to compute a normal form for stabilizer circuits. The conjugation rules below will also be very helpfull.
Let $\hh=\prod_{i=0}^{n-1}\HH_i$, let $U^{\hh}=\hh U\hh^{-1}=\hh U\hh$ for any $U\in\UG$. We use $U^{-\hh}$ as a shorthand notation for $(U^{\hh})^{-1}$.
\begin{align}
  &\hh X_A\hh^{-1}=X_{A^{-\T}}\label{conj-XA-h}\\
  &\PP_i^{\hh}\PP_i\PP_i^{-\hh}=\ee^{\ii\frac{\pi}{4}}\HH_i\XX_i\label{conj-p-ph}\\
  &\PP_i^{\hh}Z_{ik}\PP_i^{-\hh}=\ee^{-\ii\frac{\pi}{4}}Z_{ik}X_{[ik]}\PP_k\label{conj-z-ph}\\
  &Z_{ij}^{\hh}Z_{ij}Z_{ij}^{\hh}=Z_{ij}Z_{ij}^{\hh}Z_{ij}=\HH_i\HH_jX_{(ij)}=X_{(ij)}\HH_i\HH_j\label{conj-zij-zijh}\\
  &Z_{ij}^{\hh}Z_{ik}Z_{ij}^{\hh}=X_{[jk]}Z_{ik}=Z_{ik}X_{[jk]}\quad (i,j,k\text{ distinct})\label{conj-zik-zijh}\\
  &Z_{ij}^{\hh}\PP_jZ_{ij}^{\hh}=\PP_i^{\hh}X_{[ij]}\PP_j\label{conj-pj-zijh}
\end{align}

Identity \eqref{conj-XA-h} is a straightforward consequence of \eqref{conj-xij-h}. Identity \eqref{conj-p-ph} comes from \eqref{hp3}, \eqref{conj-z-h}, \eqref{conj-x-p} and \eqref{yixz}. We prove Identity \eqref{conj-z-ph} using \eqref{conj-Pi}, \eqref{hp3} and \eqref{zijxij}. We prove  Identity \eqref{conj-zij-zijh} using
\eqref{zijxij} and \eqref{sijxij}. Identity \eqref{conj-zik-zijh} is proved using \eqref{zijxij} and \eqref{conj-xij-xjk}.
Identity \eqref{conj-pj-zijh} is proved using \eqref{zijxij} and \eqref{conj-Pi}.

The last tools we need are the conjugation rules of a product $\XX_{u}\ZZ_{v}$ by the gates $\PP_i$, $X_{[ij]}$, $Z_{ij}$ and $\hh$.
\begin{align}
  &\PP_i\XX_{u}\ZZ_{v}\PP_i^{-1}=\ii^{u_i}\XX_{u}\ZZ_{v\oplus u_i e_i}\label{conj-xz-pi}\\
  &X_{[ij]}\XX_{u}\ZZ_{v}X_{[ij]}=\XX_{[ij]\mathrm{u}}\ZZ_{[ji]\mathrm{v}}\label{conj-xz-xij}\\
  &Z_{ij}\XX_{u}\ZZ_{v}Z_{ij}=(-1)^{u_iu_j}\XX_{u}\ZZ_{v\oplus u_j e_i\oplus u_i e_j}=(-1)^{u_iu_j}\XX_{u}\ZZ_{v\oplus \{\{ij\}\}u}\label{conj-xz-zij}\\
  &\hh\XX_u\ZZ_v\hh=\XX_v\ZZ_u\label{conj-xz-h}
\end{align}
Identity \eqref{conj-xz-pi} comes from \eqref{conj-x-p} and \eqref{yixz},
Identity \eqref{conj-xz-xij} from \eqref{conj-Za-xij}, \eqref{conj-z-h} and \eqref{conj-xij-h}, Identity \eqref{conj-xz-zij} from \eqref{conj-xz-xij}, \eqref{anticom} and \eqref{conj-z-h}, Identity \eqref{conj-xz-h} from \eqref{conj-z-h}.
Finally we generalize below Identities \eqref{conj-xz-pi}, \eqref{conj-xz-xij} and \eqref{conj-xz-zij}.
\begin{align}
  &\PP_b\XX_{u}\ZZ_{v}\PP_b^{-1}=\ii^{\sum u_i\, \mathrm{mod}\, 4}\XX_{u}\ZZ_{v\oplus\sum_i b_i u_i e_i}=\ii^{\sum u_i\, \mathrm{mod}\, 4}\XX_{u}\ZZ_{v\oplus bu}\label{conj-xz-pb}\\
  &X_{A}\XX_{u}\ZZ_{v}X_{A}^{-1}=\XX_{Au}\ZZ_{A^{-\T}v}\label{conj-xz-XA}\\
  &Z_{B}\XX_{u}\ZZ_{v}Z_{B}=(-1)^{q_B(u)}\XX_{u}\ZZ_{v\oplus Bu}\label{conj-xz-ZB}
\end{align}

\section{Computing normal forms\label{NF}}
In this section we provide algorithms to compute two kind of normal forms for stabilizer circuits.
The first normal form we propose  is a generalization of the form $\ZZ_a\PP_bZ_BX_A$ (Theorem \ref{decompo}) to any stabilizer circuit  and the algorithm that build this normal form
is a generalization of Algorithm $\cto$.

\begin{theo}\label{nf-th} \textbf{Normal form for stabilizer circuits}

      Any  stabilizer circuit  $C=\prod_{k=1}^{\ell} M_k $, where $M_k\in\{\PP_i,\HH_i,X_{[ij]}\}$ can be written in polynomial time $O(\ell n^2)$ under the form
     \begin{equation}
     \HH_w\PP_bZ_B\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A\ ,\label{nf}
 \end{equation}

 where     $b,d,u,v,w\in \F^n$, $B,D\in\BG$, $A\in\GL$, $\phi\in\{k\frac{\pi}{4},k\in\Z\}$

 and $\hh$ is the Hadamard gate applied on all qubits.
   \end{theo}

  \begin{proof}
    We prove the result by induction on $\ell$.
    The base case is clear : if $\ell=0$ then $C=\III$ and a normal form for $\III$ is $\hh\hh$. To realize the induction step, we prove that, for any $M\in\{\HH_i,\PP_i,X_{[ij]}\}$ and any $C$ under the form $\HH_w\PP_bZ_B\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A$ , the product $MC$ can be written under the same form.
\medskip

\texttt{Case 1} : $M=\HH_i$ and $\HH_iC=\HH_{w\oplus e_i}\PP_bZ_B\ee^{\ii\phi}\hh\XX_{u}\ZZ_{v}\PP_dZ_DX_A$, so $\HH_iC$ is under normal form.
\medskip

\texttt{Case 2} : $M=\PP_i$ and $\PP_iC=\HH_{w}\cdot\HH_w\PP_i\HH_w\cdot\PP_bZ_B\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_d Z_DX_A$ (we use the dot $\cdot$ to make reading easier).
\medskip

\texttt{Case 2.1} : $w_i=0$. Then $\HH_w\PP_i\HH_w=\PP_i$, so

$\PP_iC\stackrel{\eqref{czpg-mult}}{=}\HH_{w}\ZZ_{b_i e_i}\PP_{b\oplus e_i}Z_B\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A\stackrel{\eqref{conj-z-h}}{=}\HH_{a}\PP_{b\oplus e_i}Z_B\hh\ee^{\ii\phi}\XX_{u\oplus b_i e_i}\ZZ_{v}\PP_dZ_DX_A$  and $\PP_iC$ is under normal form.

\medskip

\texttt{Case 2.2} : $w_i=1$. Then $\HH_w\PP_i\HH_w=\PP_i^{\hh}$, so

$\PP_iC=\HH_{w}\cdot\PP_i^{\hh}\PP_{b}\PP_i^{-\hh}\cdot\PP_i ^{\hh}Z_B\PP_i^{-\hh}\cdot\hh \ee^{\ii\phi}\PP_i\XX_{u}\ZZ_{v}\PP_i^{-1}\cdot \PP_i\PP_dZ_DX_A$,

$\PP_iC\stackrel{\ref{conj-xz-pi},\eqref{czpg-mult}}{=}\HH_{w}\cdot\PP_i^{\hh}\PP_{b}\PP_i^{-\hh}\cdot\PP_i^{\hh} Z_B\PP_i^{-\hh}\cdot
\hh\ee^{\ii\phi}\ii^{u_i}\XX_{u}\ZZ_{v\oplus u_i e_i}\cdot \ZZ_{d_i e_i}\PP_{d\oplus e_i}Z_DX_A$,

$\PP_iC=\HH_{w}\cdot\PP_i^{\hh}\PP_{b}\PP_i^{-\hh}\cdot\PP_i^{\hh} Z_B\PP_i^{-\hh}\cdot
\hh\ee^{\ii\phi}\ii^{u_i}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}\cdot\PP_{d\oplus e_i}Z_DX_A$.

Let $B_i=\{\{p,q\}\in B\mid i\in\{p,q\}\}$ and $K_i=\{k\mid \{k,i\}\in B\}$ then

$\PP_i^{\hh} Z_B\PP_i^{-\hh}=Z_{B\oplus B_i}\PP_i^{\hh}\cdot \prod_{k\in K_i}Z_{ik}\cdot\PP_i^{-\hh}$,

$\PP_i^{\hh} Z_B\PP_i^{-\hh}\stackrel{\eqref{conj-z-ph}}{=}Z_{B\oplus B_i}\prod_{k\in K_i}\left(\ee^{-\ii\frac{\pi}{4}}Z_{ik}X_{ik}\PP_k\right)$.

\medskip

\texttt{Case 2.2.1} : $b_i=0$.  Then $\PP_i^{\hh}\PP_{b}\PP_i^{-\hh}=\PP_{b}$, so

$\PP_iC=\HH_{w}\PP_{b}\cdot Z_{B\oplus B_i}\prod_{k\in K_i}\left(\ee^{-\ii\frac{\pi}{4}}Z_{ik}X_{ik}\PP_k\right)\cdot
\hh\ee^{\ii\phi}\ii^{u_i}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}\cdot\PP_{d\oplus e_i}Z_DX_A$.

Let $\ZZ_{a'}\PP_{b'}Z_{B'}X_{A'}=\cto(\PP_{b}Z_{B\oplus B_i}\prod_{k\in K_i}Z_{ik}X_{ik}\PP_k,\III)$, where $A'=\prod_{k\in K_i}[ik]$.

We merge all the overall phases in a unique phase $\phi'$ and obtain

$\PP_iC=\HH_{w}\ZZ_{a'}\PP_{b'}Z_{B'}X_{A'}\hh\ee^{\ii\phi'}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}\PP_{d\oplus e_i}Z_DX_A$,

$\PP_iC\stackrel{\eqref{conj-XA-h}}{=}\HH_{w}\ZZ_{a'}\PP_{b'}Z_{B'}\hh\ee^{\ii\phi'}\cdot X_{A'^{-\T}}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}X_{A'^{-\T}}^{-1}\cdot X_{A'^{-\T}}\PP_{d\oplus e_i}Z_DX_A$,

where $A'^{-\T}=\prod_{k\in K_i}[ki]$.

Let $\XX_{u'}\ZZ_{v'}\stackrel{\eqref{conj-xz-XA}}{=}X_{A'^{-\T}}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}X_{A'^{-\T}}^{-1}$.

Let $\ZZ_{a''}\PP_{b''}Z_{B''}X_{A''}=\cto\left(X_{A'^{-\T}},\PP_{d\oplus e_i}Z_DX_A\right)$.

Then $\PP_iC=\HH_{w}\ZZ_{a'}\PP_{b'}Z_{B'}\hh\ee^{\ii\phi'}\XX_{u'}\ZZ_{v'}\ZZ_{a''}\PP_{b''}Z_{B''}X_{A''}$, so

$\PP_iC\stackrel{\eqref{conj-z-h}}{=}\HH_{w}\PP_{b'}Z_{B'}\hh\ee^{\ii\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''}\PP_{b''}Z_{B''}X_{A''}$, and $\PP_iC$ is under normal form.

\medskip

\texttt{Case 2.2.2} :  $b_i=1$.  Then $\PP_i^{\hh}\PP_{b}\PP_i^{-\hh}=\PP_i^{\hh}\PP_i\PP_i^{-\hh}\cdot\PP_{b\oplus e_i}
\stackrel{\eqref{conj-p-ph}}{=}\ee^{\ii\frac{\pi}{4}}\HH_i\XX_i\cdot\PP_{b\oplus e_i}$, so

$\PP_iC=\HH_{w}\cdot\ee^{\ii\frac{\pi}{4}}\HH_i\XX_i\PP_{b\oplus e_i}\cdot\PP_i^{\hh} Z_B\PP_i^{-\hh}\cdot\hh\ee^{\ii\phi}\ii^{u_i}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}\cdot\PP_{d\oplus e_i}Z_DX_A$,

$\PP_iC=\HH_{w\oplus e_i}\cdot\XX_i\cdot\PP_{b\oplus e_i}\PP_i^{\hh} Z_B\PP_i^{-\hh}\hh\ee^{\ii(\phi+\frac{\pi}{4})}\ii^{u_i}\XX_{u}\ZZ_{v\oplus u_i e_i\oplus d_i e_i}\PP_{d\oplus e_i}Z_DX_A$.

Using Identity \eqref{conj-xz-pi},\eqref{conj-xz-h},\eqref{conj-xz-ZB} and \eqref{pauli-mult}, we compute $\phi',u',v'$ such that

$\PP_iC=\HH_{w\oplus e_i}\PP_{b\oplus e_i}\PP_i^{\hh} Z_B\PP_i^{-\hh}\hh\ee^{\ii\phi'}\XX_{u'}\ZZ_{v'}\PP_{d\oplus e_i}Z_DX_A$.
Then we proceed as in Case 2.2.1. and we obtain a normal form for $\PP_iC$

\medskip

\texttt{Case 3} : $M=X_{[ij]}$.

$X_{[ij]}C=\HH_{w}\cdot\HH_wX_{[ij]}\HH_w\cdot\PP_bZ_B\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A$.
\medskip

\texttt{Case 3.1} : $w_i=w_j=0$.

Then $\HH_wX_{[ij]}\HH_w=X_{[ij]}$ and
$X_{[ij]}C=\HH_{w}X_{[ij]}\PP_bZ_B \hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A$.

Let $\ZZ_{a'}\PP_{b'}Z_{B'}X_{[ij]}=\cto(X_{[ij]},\PP_bZ_B)$ , then

$X_{[ij]}C=\HH_{w}\ZZ_{a'}\PP_{b'}Z_{B'}X_{[ij]}\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A$,

$X_{[ij]}C\stackrel{\eqref{conj-xij-h}\eqref{conj-xz-xij}}{=}\HH_{w}\ZZ_{a'}\PP_{b'}Z_{B'}\hh\ee^{i\phi}\XX_{[ji]u}\ZZ_{[ij]v}X_{[ji]}\PP_dZ_DX_A$,

$X_{[ij]}C\stackrel{\eqref{conj-z-h}}{=}\HH_{w}\PP_{b'}Z_{B'}\hh\ee^{i\phi}\XX_{[ji]u\oplus a'}\ZZ_{[ij]v}X_{[ji]}\PP_dZ_DX_A$.

Let $\ZZ_{a''}\PP_{b''}Z_{B''}X_{A''}=\cto(X_{[ji]},\PP_dZ_DX_A)$, then

$X_{[ij]}C=\HH_{w}\PP_{b'}Z_{B'}\hh\ee^{i\phi}\XX_{[ji]u\oplus a'}\ZZ_{[ij]v\oplus a''}\PP_{b''}Z_{B''}X_{A''}$ and $X_{[ij]}C$ is under normal form.

\medskip

\texttt{Case 3.2} : $w_i=w_j=1$.

Then $\HH_wX_{[ij]}\HH_w\stackrel{\eqref{conj-xij-h}}{=}X_{[ji]}$ and we proceed as in case 3.1.
\medskip

\texttt{Case 3.3} : $w_i=1$ and $w_j=0$.

Then $\HH_wX_{[ij]}\HH_w\stackrel{\eqref{zijxij}}{=}Z_{ij}$ and a normal form for $X_{[ij]}C$ is

$\HH_{w}\PP_bZ_{B\oplus\{\{i,j\}\}}\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_{A}$.
\medskip

\texttt{Case 3.4} : $w_i=0$ and $w_j=1$.

Then $\HH_wX_{[ij]}\HH_w=Z_{ij}^{\hh}$ and
$X_{[ij]}C=\HH_{w}Z_{ij}^{\hh}\PP_bZ_B\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_{A}$.
\medskip

\texttt{Case 3.4.1} : $B_{ij}=0$.

$X_{[ij]}C=\HH_{w}\cdot Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}\cdot Z_{ij}^{\hh}Z_BZ_{ij}^{\hh}\cdot \hh  \ee^{i\phi}\cdot Z_{ij}\XX_{u}\ZZ_{v}Z_{ij}\cdot Z_{ij}\PP_dZ_{D}X_{A}$.

$X_{[ij]}C\stackrel{\eqref{conj-xz-zij}}{=}\HH_{w}\cdot Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}\cdot Z_{ij}^{\hh}Z_BZ_{ij}^{\hh}\cdot
\hh  \ee^{i\phi}(-1)^{u_iu_j}\XX_{u}\ZZ_{v\oplus \{\{ij\}\}u}\PP_dZ_{D\oplus \{i,j\}}X_{A}$.

Let $B_i=\{\{p,q\}\in B\mid i\in\{p,q\}\}$ and $K_i=\{k\mid \{i,k\}\in B\}$, then

$Z_{ij}^{\hh}Z_BZ_{ij}^{\hh}=Z_{B\oplus B_i\oplus B_j}\cdot Z_{ij}^{\hh}\cdot\prod_{k\in K_i}Z_{ik}\cdot\prod_{k\in K_j}Z_{jk}\cdot Z_{ij}^{\hh}$,

$Z_{ij}^{\hh}Z_BZ_{ij}^{\hh}\stackrel{\eqref{conj-zik-zijh}}{=}Z_{B\oplus B_i\oplus B_j}\cdot\prod_{k\in K_i}Z_{ik}X_{[jk]}\cdot\prod_{k\in K_j}Z_{jk}X_{[ik]}$.

Let $\ZZ_{a'}Z_{B'}X_{A'}=\cto(Z_{ij}^{\hh}Z_BZ_{ij}^{\hh},\III)$, where $A'=\prod_{k\in K_i}[jk]\prod_{k\in K_j}[ik]$, then

$X_{[ij]}C=\HH_{w}\cdot Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}\cdot \ZZ_{a'}Z_{B'}X_{A'} \cdot\hh  \ee^{i\phi}(-1)^{u_iu_j}\XX_{u}\ZZ_{v\oplus \{\{ij\}\}u}\PP_dZ_{D\oplus \{i,j\}}X_{A}$,

$X_{[ij]}C\stackrel{\eqref{conj-XA-h}}{=}\HH_{w}\cdot Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}\cdot\ZZ_{a'}Z_{B'} \hh
\ee^{i\phi}(-1)^{u_iu_j}\cdot X_{A'^{-\T}}\XX_{u}\ZZ_{v\oplus \{\{ij\}\}u}X_{A'^{-\T}}^{-1}\cdot
X_{A'^{-\T}}\PP_dZ_{D\oplus \{i,j\}}X_{A}$,

where $A'^{-\T}=\prod_{k\in K_i}[kj]\prod_{k\in K_j}[ki]$.

Let $\ee^{i\phi'}\XX_{u'}\ZZ_{v'}\stackrel{\eqref{conj-xz-XA}}{=}\ee^{i\phi}(-1)^{u_iu_j}\cdot X_{A'^{-\T}}\XX_{u}\ZZ_{v\oplus \{\{ij\}\}u}X_{A'^{-\T}}^{-1}$.

Let $\ZZ_{a''}\PP_{b''}Z_{B''}X_{A''}=\cto(X_{A'^{-\T}},\PP_dZ_{D\oplus \{i,j\}}X_{A})$.

Then $X_{[ij]}C=\HH_{w}\cdot Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}\cdot\ZZ_{a'}Z_{B'} \hh
\ee^{i\phi'}\XX_{u'}\ZZ_{v'}\ZZ_{a''}\PP_{b''}Z_{B''}X_{A''}$, so

$X_{[ij]}C\stackrel{\eqref{conj-z-h}}{=}\HH_{w}\cdot Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}\cdot Z_{B'} \hh
\ee^{i\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''}\PP_{b''}Z_{B''}X_{A''}$.

\medskip

\texttt{Case 3.4.1.1} : $b_i=b_j=0$.

Then $Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}=\PP_b$ and
$X_{[ij]}C=\HH_{w}\PP_b Z_{B'} \hh \ee^{i\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''} \PP_{b''}Z_{B''}X_{A''}$,

so $X_{ij}C$ is under normal form.
\medskip

\texttt{Case 3.4.1.2} : $b_i=0$ and $b_j=1$.

Then $Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}=Z_{ij}^{\hh}\PP_jZ_{ij}^{\hh}\PP_{b\oplus e_j}\stackrel{\eqref{conj-pj-zijh}}{=}\PP_i^{\hh}X_{ij}\PP_j\PP_{b\oplus e_j}
=\PP_i^{\hh}X_{ij}\PP_{b}$

Hence $X_{[ij]}C=\HH_{w}\cdot\PP_i^{\hh}X_{ij}\PP_{b} \cdot Z_{B'} \hh
\ee^{i\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''}\PP_{b''}Z_{B''}X_{A''}$.

Observe that $\PP_{b} Z_{B'} \hh\ee^{i\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''}\PP_{b''}Z_{B''}X_{A''}$ is already under normal form, so we merge successively
$X_{ij}$ (case 3.1), $\PP_i^{\hh}$ (case 2.2) and $H_w$ (case 1) into that form and  obtain thereby a  normal form for $X_{[ij]}C$.

\medskip

\texttt{Case 3.4.1.3} : $b_i=1$ and $b_j=0$.

We proceed as in Case 3.4.1.2, swapping $i$ and $j$.

\medskip

\texttt{Case 3.4.1.4} : $b_i=b_j=1$.

Then $Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}=Z_{ij}^{\hh}\PP_j\PP_iZ_{ij}^{\hh}P_{b\oplus e_j\oplus e_j}
\stackrel{\eqref{conj-pj-zijh}}{=}\PP_i^{\hh}X_{[ij]}\PP_j \PP_j^{\hh}X_{[ji]}\PP_iP_{b\oplus e_j\oplus e_j}$.

Since Identity \eqref{conj-Pj}, $\PP_j^{\hh}X_{[ji]}$ and $\PP_iP_{b\oplus e_j\oplus e_j}$ commutes, so
$Z_{ij}^{\hh}\PP_bZ_{ij}^{\hh}=\PP_i^{\hh}X_{[ij]}\PP_b\PP_j^{\hh}X_{[ji]}$.

Hence $X_{[ij]}C=\HH_{w}\cdot \PP_i^{\hh}X_{[ij]}\PP_b\PP_j^{\hh}X_{[ji]}\cdot Z_{B'} \hh
\ee^{i\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''}\PP_{b''}Z_{B''}X_{A''}$.

Observe that $Z_{B'} \hh\ee^{i\phi'}\XX_{u'\oplus a'}\ZZ_{v'\oplus a''}\PP_{b''}Z_{B''}X_{A''}$ is under normal form, so we  merge successively
$X_{[ji]}$ (case 3.1), $\PP_j^{\hh}$ (case 2.2.1), $\PP_b$ (case 2.1), $X_{[ij]}$ (case 3.1),  $\PP_i^{\hh}$ (case 2.2) and $H_w$ (case 1) into that form and we
obtain a normal form for $X_{ij}C$ is under normal form.

\medskip

\texttt{Case 3.4.2} : $B_{ij}=1$.

$X_{[ij]}C=\HH_{w}\cdot Z_{ij}^{\hh}Z_{ij}\cdot\PP_bZ_{B'}\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_{A}$, where $B'=B\oplus \{\{i,j\}\}$, hence $B'_{ij}=0$.

$X_{[ij]}C\stackrel{\ref{conj-zij-zijh}}{=}\HH_{w}\cdot \HH_i\HH_jX_{(ij)}Z_{ij}^{\hh}  \cdot\PP_bZ_{B'}\hh\ee^{i\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_{A}$.

We use the conjugations rules \eqref{conj-Za-sij}, \eqref{conj-Pb-sij} and \eqref{conj-ZB-sij} by the $\swap$ gate $X_{(ij)}$ and we merge the Hadamard gates to obtain

$X_{[ij]}C=\HH_{w\oplus e_i\oplus e_j}Z_{ij}^{\hh} \PP_{(ij)b}Z_{(ij)B'(ij)}\hh\ee^{i\phi}\XX_{(ij)u}\ZZ_{(ij)v}\PP_{(ij)d}Z_{(ij)D(ij)}X_{(ij)A}$.

Finally we proceed as in case 3.4.1, since $\{i,j\}\not\in (ij)B'(ij)$.
\medskip

The time complexity of algorithm $\cto$ is $O(\ell n)$, where $\ell$ is the gate count of the input circuit. As we apply this algorithm on circuits of $O(n)$ gates
(cases 2.2 and 3.4.1), the cost of each call to $\cto$ is  $O(n^2)$ operations.
Conjugating a Pauli gate $\XX_u\ZZ_v$ by $X_A$ \eqref{conj-xz-XA} costs only $O(n)$ operations because we use a decomposition in less than $2n$ transvections of matrices  $A$  and $A^{-\T}$ and obtaining this decompostion requires only $n$ operations (case 3.4.1). Conjugating a Pauli gate $\XX_u\ZZ_v$ by $Z_B$ \eqref{conj-xz-ZB} (resp. by $\PP_b$ \eqref{conj-xz-pb}) costs $O(n^2)$ operations (resp. $O(n)$ operations).
Other rewritings require $O(n)$ or $O(1)$ operations. Therefore the cost of merging a $M_k$ gate in the normal form at each induction step is $O(n^2)$ operations.
As we need $\ell$ steps to write $C$ under normal form, we see that the number of operations performed is $O(\ell n^2)$.
\end{proof}

The global phase $\phi$ in the form \ref{nf} is not important since it is physically unobservable. However, we decided  not to neglect it during the computation process of the normal form since calculating its exact value do not require much additional work. Note that the form \ref{nf} is given as a matrix product and corresponds actually to a quantum circuit under the form
$CX\texttt{-}CZ\texttt{-}P\texttt{-}Z\texttt{-}X\texttt{-}H\texttt{-}CZ\texttt{-}P\texttt{-}H$ \footnote{The reader who is not used to quantum circuits must pay attention to the following fact: the circuits act to the right of the state $\ket{\psi}$
  presented to their left but the associated operators act to the left of the ket, so the order of the gates in the circuit is inverted comparing to \ref{nf}.}
, which is similar to the forms proposed
by Duncan \textit{et. al.} \cite{2020DKPV} ($H\texttt{-}Z\texttt{-}P\texttt{-}CZ\texttt{-}CX\texttt{-}H\texttt{-}CZ\texttt{-}P\texttt{-}Z\texttt{-}H$) or
by Bravyi and Maslov \cite{2020BM} ($X\texttt{-}Z\texttt{-}P\texttt{-}CX\texttt{-}CZ\texttt{-}H\texttt{-}CZ\texttt{-}H\texttt{-}P$). In these 3 normal forms, the 2-qubit gate count is asymptotically dominated by the two $\cz$ gate layers which contain together up to $n(n-1)$ 2-qubit gates. Indeed, the $\cnot$ gate layer can be decomposed in $O(n^2/\log n)$ $\cnot$ gates thanks to an algorithm proposed in 2004 by Patel \textit{et. al.} \cite{2004PMH}. Hence it would be interesting for a high number of qubits to compute a normal form where the two $\cz$ gate layers are replaced by two $\cnot$ gate layers. To this end we need the following lemma.

\begin{lem}\label{symplectic}
  Let $p=\frac{n-n\,\mathrm{mod}\,2}{2}$ and $s\in\F^{p}$. Let $B_{s}\in\BG$ be the $n\times n$ matrix
  $\begin{bmatrix}
    \mathbf{0}_{p\times p}&\mathrm{diag}(s)\\
    \mathrm{diag}(s)&\mathbf{0}_{p\times p}
  \end{bmatrix}$
  when $n$ is even or the $n\times n$  matrix
  $\begin{bmatrix}
    \mathbf{0}_{p\times p}&\mathrm{diag}(s)&0\\
    \mathrm{diag}(s)&\mathbf{0}_{p\times p}&0
    \\0&0&0
  \end{bmatrix}$ when $n$ is odd.
  Then, for any $B$ $\in\BG$, there exists $s\in\F^{p}$ and $A\in\GL$ such that $B_{s}=A^{\T}BA$.
\end{lem}

This statement is an adaptation to $\F^n$ of a well-known result about classical groups and the construction of $A$ and $s$ is for instance described in \cite[Section 3.4.4]{2009W}. We recall briefly the principle of the construction and give a complete example \ref{symp-red} of the process. If $B$ is the matrix  of a non degenerated alternating bilinear form with respect to the canonical basis $(e_i)_{i=0\dots n-1}$ (\textit{i.e.} $B$ is invertible), then $n$ is even and  one constructs a symplectic basis of $\F^n$ for the form, that is, the form has matrix  $B_s$ with respect to this basis,
where $s=[\overbrace{1,\dots, 1}^{\times n/2}]^{\T}$. In the context of stabilizer circuits, the matrix $B$ represents a $\cz$-gate circuit $Z_B$, hence $B$ is generally singular. In this case the process leads to the construction of a basis such that the form has matrix $B_s$ with repect to this basis, where $s$ can be any vector in $\F^p$. In both cases, $A$ is the matrix of the new basis and $B_{s}=A^{\T}BA$ is just the change of basis formula. We say that $B_s$ is a \textit{reduction} of $B$ and any matrix in $\BG$ under the form $B_s$ is called a \textit{reduced} matrix.

\begin{example} Computing a reduced matrix in $\BG[7]$. \label{symp-red}\medskip

  Let $B\in\BG[7]$ be the matrix \begin{footnotesize}
    $\begin{bmatrix}
      0&0&0&1&0&1&0\\
      0&0&1&1&0&0&1\\
      0&1&0&0&1&1&0\\
      1&1&0&0&1&0&0\\
      0&0&1&1&0&0&0\\
      1&0&1&0&0&0&1\\
  0&1&0&0&0&1&0\\
\end{bmatrix}$\end{footnotesize}
and let $C_i$ (resp. $R_i$) denote the column (resp. the row) $i$  of matrix $B$, where $i=0,\dots,6$. To obtain a reduced form for $B$, we use Gaussian elimination
(\textit{i.e.} multiplication by transvection matrices) first on $C_i,R_i$, then  on $C_{i+3},R_{i+3}$ , for $i=0,1,2.$\medskip

\begin{footnotesize}
$\bf i=0$

on $C_0,R_0$ : $[53]B[35]=
\begin{bmatrix}
  \bf{0}&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&0&1&1&0&1&1\\
  \bf0&1&0&0&1&1&0\\
  \bf1&1&0&0&1&0&0\\
  \bf0&0&1&1&0&1&0\\
  \bf0&1&1&0&1&0&1\\
  \bf0&1&0&0&0&1&0\\
\end{bmatrix}$

on $C_3,R_3$ : $[40][10][53]B[35][01][04]=
\begin{bmatrix}
  \bf0&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&0&1&\bf0&0&1&1\\
  \bf0&1&0&\bf0&1&1&0\\
  \bf1&\bf0&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&0&1&\bf0&0&1&0\\
  \bf0&1&1&\bf0&1&0&1\\
  \bf0&1&0&\bf0&0&1&0\\
\end{bmatrix}$

$\bf i=1$

on $C_1,R_1$ :

$(42)[40][10][53]B[35][01][04](42)=
\begin{bmatrix}
  \bf0&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&0&0&\bf0&1&1&1\\
  \bf0&0&0&\bf0&1&1&0\\
  \bf1&\bf0&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&1&1&\bf0&0&1&0\\
  \bf0&1&1&\bf0&1&0&1\\
  \bf0&1&0&\bf0&0&1&0\\
\end{bmatrix}$

$[64][54](42)[40][10][53]B[35][01][04](42)[45][46]=
\begin{bmatrix}
  \bf0&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf1&\bf0&\bf0\\
  \bf0&\bf0&0&\bf0&1&0&1\\
  \bf1&\bf0&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf1&1&\bf0&0&1&0\\
  \bf0&\bf0&0&\bf0&1&0&0\\
  \bf0&\bf0&1&\bf0&0&0&0\\
\end{bmatrix}$

on $C_4,R_4$ :

$[51][21][64][54](42)[40][10][53]B[35][01][04](42)[45][46][12][15]=
\begin{bmatrix}
  \bf0&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf1&\bf0&\bf0\\
  \bf0&\bf0&0&\bf0&\bf0&0&1\\
  \bf1&\bf0&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf1&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf0&0&\bf0&\bf0&0&0\\
  \bf0&\bf0&1&\bf0&\bf0&0&0\\
\end{bmatrix}$

$\bf i=2$

on $C_2,R_2$ :

$(56)[51][21][64][54](42)[40][10][53]B[35][01][04](42)[45][46][12][15](56)=
\begin{bmatrix}
  \bf0&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf1&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf0&\bf1&\bf0\\
  \bf1&\bf0&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf1&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf1&\bf0&\bf0&0&0\\
  \bf0&\bf0&\bf0&\bf0&\bf0&0&0\\
\end{bmatrix}$

on $C_5,R_5$ :

$(56)[51][21][64][54](42)[40][10][53]B[35][01][04](42)[45][46][12][15](56)=
\begin{bmatrix}
  \bf0&\bf0&\bf0&\bf1&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf1&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf0&\bf1&\bf0\\
  \bf1&\bf0&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf1&\bf0&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf1&\bf0&\bf0&\bf0&\bf0\\
  \bf0&\bf0&\bf0&\bf0&\bf0&\bf0&0\\
\end{bmatrix}$
\end{footnotesize}

The new basis matrix $A$ is
\begin{footnotesize}
$[35][01][04](42)[45][46][12][15](56)=
\begin{bmatrix}
  1&1&0&0&0&0&1\\
  0&1&1&0&0&0&1\\
  0&0&0&0&1&1&1\\
  0&0&0&1&0&0&1\\
  0&0&1&0&0&0&0\\
  0&0&0&0&0&0&1\\
  0&0&0&0&0&1&0\\
\end{bmatrix}$
\end{footnotesize}
\end{example}

\begin{theo} \textbf{$\cz$-reduced normal form}

  Any  stabilizer circuit  $C=\prod_{k=1}^{\ell} M_k $, where $M_k\in\{\PP_i,\HH_i,X_{[ij]}\}$ can be written  under the form
  \begin{equation}
    \HH_w\PP_bX_{A_{1}}Z_{B_s}\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v} X_{A_{2}}Z_{B_{s'}}X_{A_{3}}\PP_d\ ,\label{red-nf}
  \end{equation}
  where     $b,d,u,v,w\in \F^n$, $B_{s},B_{s'}\in\BG$ are reduced matrices,  $A_1,A_2,A_3\in\GL$, $\phi\in\{k\frac{\pi}{4},k\in\Z\}$
 and $\hh$ is the Hadamard gate applied on all qubits.
  \end{theo}

\begin{proof}
We start from the normal form $C=\HH_w\PP_bZ_B\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v}\PP_dZ_DX_A$. Let $\ZZ_{a'}\PP_{b'}Z_{B'}=X_{A}^{-1}\cdot\PP_dZ_D\cdot X_A$, then
$C=\HH_w\PP_bZ_B\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v}X_A\ZZ_{a'}\PP_{b'}Z_{B'}\stackrel{\ref{conj-xz-XA}}{=}\HH_w\PP_bZ_B\hh\ee^{\ii\phi}\XX_{u}\ZZ_{v\oplus A^{-\T}a'}X_AZ_{B'}\PP_{b'}$. Let $B_s$ (resp. $B_{s'})$ be a reduction of $B$ (resp. $B'$). Let $B_s=A_1^{\T}BA_1$ and
$B_{s'}=A_2^{\T}B'A_2$, where $A_1,A_2\in\GL$. Since \ref{conj-ZB-XA} one has $X_{A_1}Z_{B_s}X_{A_1}^{-1}=\ZZ_{q_{B_{s}}(A_1^{-1})}Z_{B}$ and
$X_{A_2}Z_{B_{s'}}X_{A_2}^{-1}=\ZZ_{q_{B_{s'}}(A_2^{-1})}Z_{B'}$, hence

$C=\HH_w\PP_b  X_{A_1}Z_{B_s}X_{A_1}^{-1}\ZZ_{q_{B_{s}}(A_1^{-1})}   \hh\ee^{\ii\phi}\XX_{u}\ZZ_{v\oplus A^{-\T}a'}X_A \ZZ_{q_{B_{s'}}(A_2^{-1})}X_{A_2}Z_{B_{s'}}X_{A_2}^{-1}\PP_{b'}$.
After merging the $\ZZ$ gates with $\XX_{u}\ZZ_{v\oplus A^{-\T}a'}$, we obtain :

$C=\HH_w\PP_b  X_{A_1}Z_{B_s}X_{A_1}^{-1}\hh\ee^{\ii\phi}\XX_{u'}\ZZ_{v'}X_A X_{A_2}Z_{B_{s'}}X_{A_2}^{-1}\PP_{b'}$,

where $u'=q_{B_{s}}(A_1^{-1})$ and $v'=v\oplus A^{-\T}a'\oplus A^{-T}q_{B_{s'}}(A_2^{-1})$. Hence

$C=\HH_w\PP_b  X_{A_1}Z_{B_s} \hh\cdot X_{A_1^{\T}}\ee^{\ii\phi}\XX_{u'}\ZZ_{v'}X_{A_1^{-\T}}\cdot X_{A_1^{\T}}X_A X_{A_2}Z_{B_{s'}}X_{A_2^{-1}}\PP_{b'}$.

Finally $C\stackrel{\ref{conj-xz-XA}}{=}\HH_w\PP_b  X_{A_1}Z_{B_s} \hh\ee^{\ii\phi}\XX_{A_1^{\T}u'}\ZZ_{A_1^{-1}v'}X_{A_1^{\T}AA_2}Z_{B_{s'}}X_{A_2^{-1}}\PP_{b'}$ and
$C$ is under the form \ref{red-nf}.
\end{proof}

Neglecting the overall phase, the $\cz$-reduced normal form \ref{red-nf} corresponds actually to a quantum circuit under the form
$P\texttt{-}CX\texttt{-}CZ\texttt{-}CX\texttt{-}Z\texttt{-}X\texttt{-}H\texttt{-}CZ\texttt{-}CX\texttt{-}P\texttt{-}H$, where each $\cz$ gate layer contains less than
$\frac n2$
$\cz$ gates.

\section{Conclusion and  future work}
Gottesman proved in his Phd thesis that any unitary matrix in the Clifford group is uniquely defined, up to a global phase, by its action by conjugation on the Pauli gates $\XX_i$ and $\ZZ_i$ \cite[pp.41,42]{1997G}. This central statement of Gottesman stabilizer formalism can be used to compute normal forms for $n$-qubit stabilizer circuits via the symplectic group over $\F$ in dimension $2n$ (\textit{e.g.} \cite{2004AG,2018MR}). In this paper we showed that it is possible to compute normal forms in polynomial time without using this formalism. The reader used to work with the symplectic group will notice that our method can also be applied inside this group, giving rise to a decomposition of type $M_{\sigma}\begin{bmatrix}I_n&B\\0&I_n\end{bmatrix}\begin{bmatrix}0&I_n\\I_n&0\end{bmatrix}        \begin{bmatrix}I_n&B'\\0&I_n\end{bmatrix}\begin{bmatrix}A&0\\0&A^{-\T}\end{bmatrix}$ for the symplectic matrix associated to the form \ref{nf},
where $B$ (resp. $B'$) is a symmetric matrix corresponding to $\PP_bZ_B$ (resp. $\PP_dZ_D$), $A\in\GL$, $M_{\sigma}$ is the permutation matrix corresponding to $\HH_w$ and  $\begin{bmatrix}0&I_n\\I_n&0\end{bmatrix}$ is the  permutation matrix corresponding to $\hh$.

In \cite{2020B} (resp. \cite{2019BL}), we studied the emergence of entanglement in particular stabilizer circuits, namely $\cnot$ (resp.  $\cz$ plus $\swap$) circuits. Our goal was to find out what kind of entanglement can be created when those simple  circuits act on a completely factorized state. It would be interesting to understand how well normal forms could help to extend these works to any stabilizer circuit.

Another usefull study  would be  to benchmark the two normal forms  we proposed in order to determine experimentaly from how many qubits the
$\cz$-reduced normal form \eqref{red-nf}  is clearly better than the normal form \eqref{nf} in terms of 2-qubit gate count.

We leave both topics for future works.

\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv


De novo MDS cannot be passed down through genes from parent to child or transmitted from person to person.
On average, treatment-related MDS happens 5 to 7 years following treatment for other cancers. Overall, the chance of developing MDS as a result of another cancer treatment is very low. Less than 1 in 100 people treated for other cancers develop MDS. The risk increases for patients who have had multiple rounds of chemotherapy and radiation therapy or have had a bone marrow transplant.
People treated for head and neck cancers, gastrointestinal cancers, lung cancers, and possibly men treated for prostate cancer.
Originally published on Thu, 01/21/2016 - 3:35pm. Last updated on Fri, 07/20/2018 - 5:15pm.