Clifford circuits lift binary symplectic transvections

Each listed gate and its inverse normalizes ${\mathcal{P}}_n$ by its exact Pauli action. On binary labels, $H_j$ preserves $\omega$ because swapping $x_j,z_j$ in both arguments leaves $x_j{z}_j^{\mathrm{\prime }}+z_j{x}_j^{\mathrm{\prime }}$ unchanged by [F6]. For $S_j$, the local pairing becomes $x_j(z_j^{\mathrm{\prime }}+x_j^{\mathrm{\prime }})+(z_j+x_j)x_j^{\mathrm{\prime }}=x_j{z}_j^{\mathrm{\prime }}+z_j{x}_j^{\mathrm{\prime }}+2x_j{x}_j^{\mathrm{\prime }}$, equal to the old value in ${\mathbb{F}}_2$; its inverse has the same label action. For CNOT $c\to t$, write $a=(x,z)$ and $b=(u,w)$, with $w$ the $z$-part of $b$. The affected contribution after the updates in [F3] is $x_c(w_c+w_t)+(x_t+x_c)w_t+(z_c+z_t)u_c+z_t(u_t+u_c)$. The added terms $x_c{w}_t$ and $z_t{u}_c$ each occur twice and cancel, leaving the original pairing. By [F5], wire swaps permute the paired coordinate summands and preserve the form. Hadamard and swap are involutions, CNOT is self-inverse, and $S_j^{\ast }$ is the inverse of $S_j$; hence each binary gate map is invertible. Thus every finite gate word $G$ has an invertible symplectic map $M_G$, and its unitary lies in ${\mathcal{C}}_n$ by [F7].

Let $h\in \{0,1\}$ be the representative of $x\cdot z\in {\mathbb{F}}_2$, so $P(h,x,z)$ is Hermitian by [F4]. Choose a wire $p$ on which $v$ is nonzero and swap it to wire $1$. On each supported wire, the local factor is proportional to $X$, $Y$, or $Z$. Apply no gate to an $X$ factor, $H$ to a $Z$ factor, and $S^{\ast }$ to a $Y$ factor; [F1] and [F2] send each local binary label to $X$, while their phase updates compute the accumulated scalar exactly modulo $4$. The resulting binary label is the nonempty product of $X$ on the support of $v$.

For each other supported wire $j$, apply CNOT $1\to j$. By [F3], it sends $X_1{X}_j$ to $X_1$, so the finite list removes all $X_j$ labels while retaining $X_1$; then apply $H_1$ to change $X_1$ to $Z_1$. This constructs a circuit $C$ with $CP(h,x,z)C^{\ast }=\pm Z_1$: conjugation preserves Hermiticity, so the phase of an image with label $(0,e_1)$ is $0$ or $2$ modulo $4$. For $D=C^{\ast }$, the induced symplectic map sends the label $z_1=(0,e_1)$ of $Z_1$ to $v$.

The binary action of $S_1$ is ${\tau }_{z_1}$ by [F2], since [F6] gives $\omega ((x,z),(0,e_1))=x_1$. Therefore $D{S}_1{D}^{\ast }$ acts by $M_D{\tau }_{z_1}{M}_D^{-1}={\tau }_v$: for any $w$, symplecticity of $M_D$ gives $M_D(M_D^{-1}w+\omega (M_D^{-1}w,z_1)z_1)=w+\omega (w,v)v$. The circuit lies in ${\mathcal{C}}_n$ by step 1.1.

Each gate formula in [F1]–[F3] gives the exact image phase in $\mathbb{Z}\mathrm{/}4\mathbb{Z}$ as well as the binary label; [F5] gives the exact no-change phase for swaps. Induction on the finite gate list for $D{S}_1{D}^{\ast }$ therefore computes each generator-image phase by repeated application of those formulas, without replacing it by its binary parity.