Pauli and Clifford Groups, Binary Symplectic Tableaux

Direct multiplication of the displayed $2\times 2$ matrices gives $HXH=Z$ and $HZH=X$. Since $Y=iXZ$, conjugation preserves product order and gives $HYH=i(ZX)=-iXZ=-Y$.

On factor $j$, $H{X}^{x_j}{Z}^{z_j}H=Z^{x_j}{X}^{z_j}=(-1{)}^{x_j{z}_j}{X}^{z_j}{Z}^{x_j}$; all other tensor factors are unchanged by [F4] and [F5]. As $(-1{)}^{x_j{z}_j}=i^{2x_j{z}_j}$, this is $P(k+2x_j{z}_j,x^{\mathrm{\prime }},z^{\mathrm{\prime }})$ with $x_j^{\mathrm{\prime }}=z_j$, $z_j^{\mathrm{\prime }}=x_j$, and all other coordinates unchanged.

Multiplying the matrices gives $SX{S}^{\ast }=Y=iXZ$ and $SZ{S}^{\ast }=Z$. Therefore $SY{S}^{\ast }=i(SX{S}^{\ast })(SZ{S}^{\ast })=iYZ=-X$, using $YZ=iX$.

On factor $j$, $S{X}^{x_j}{Z}^{z_j}{S}^{\ast }=(iXZ{)}^{x_j}{Z}^{z_j}=i^{x_j}{X}^{x_j}{Z}^{z_j+x_j}$; other tensor factors are unchanged. Thus the total phase increases by $x_j$ modulo $4$ and the binary $z_j$ coordinate increases by $x_j$ modulo $2$.

On one factor, $Z^{z_j}{X}^{x_j^{\mathrm{\prime }}}=(-1{)}^{z_j{x}_j^{\mathrm{\prime }}}{X}^{x_j^{\mathrm{\prime }}}{Z}^{z_j}$, since the factors commute unless both exponents are $1$, when $ZX=-XZ$ by [F1]. Multiplying these identities over the ordered factors gives $Z^z{X}^{x^{\mathrm{\prime }}}=(-1{)}^p{X}^{x^{\mathrm{\prime }}}{Z}^z$, where $p$ is the integer representative $0$ or $1$ of $z\cdot x^{\mathrm{\prime }}\in {\mathbb{F}}_2$.

Substituting that reordering into $i^{k+k^{\mathrm{\prime }}}{X}^x{Z}^z{X}^{x^{\mathrm{\prime }}}{Z}^{z^{\mathrm{\prime }}}$ gives $i^{k+k^{\mathrm{\prime }}+2p}{X}^{x+x^{\mathrm{\prime }}}{Z}^{z+z^{\mathrm{\prime }}}$, which is exactly the stated product formula; all binary exponents add modulo $2$, while the phase exponent adds modulo $4$.

The formula proves closure. $P(0,0,0)=I$ is an identity, and associativity is inherited from matrix multiplication, so ${\mathcal{P}}_n$ is a group once inverses are supplied below.

Taking the adjoint reverses the order and conjugates $i^k$: $(i^k{X}^x{Z}^z{)}^{\ast }=i^{-k}{Z}^z{X}^x=i^{-k}(-1{)}^p{X}^x{Z}^z=P(2p-k,x,z)$, where $p$ represents $x\cdot z$. The product formula then gives $P^{\ast }P=P{P}^{\ast }=I$, so this adjoint is the inverse and completes the group proof.

Scalar operators $i^{k}I$ commute with every matrix and belong to ${\mathcal{P}}_n$. Conversely, if $P(k,x,z)$ commutes with every $X_j$, the product law forces $z_j=0$ for each $j$; commuting with every $Z_j$ forces $x_j=0$ for each $j$. Thus every central element is scalar and the center is exactly $Z_n$.

The identity conjugates ${\mathcal{P}}_n$ to itself. If $U,V\in {\mathcal{C}}_n$, then $(UV){\mathcal{P}}_n(UV{)}^{\ast }=U(V{\mathcal{P}}_n{V}^{\ast })U^{\ast }=U{\mathcal{P}}_n{U}^{\ast }={\mathcal{P}}_n$, so $UV\in {\mathcal{C}}_n$.

If $U{\mathcal{P}}_n{U}^{\ast }={\mathcal{P}}_n$, multiplying this equality by $U^{\ast }$ on the left and $U$ on the right gives $U^{\ast }{\mathcal{P}}_{n}U={\mathcal{P}}_n$, so $U^{\ast }\in {\mathcal{C}}_n$ by [F2]. Thus the set is a group. For $\mathrm{\mid }\lambda \mathrm{\mid }=1$, $(\lambda I)P(\lambda I{)}^{\ast }=P$ for every $P$, and conjugation by $\lambda U$ equals conjugation by $U$.

For control $c=1$ and target $t=2$, the controlled-X definition [F3,F4] gives $C\mathrm{\mid }{y}_1,\dots ,y_n⟩=\mathrm{\mid }{y}_1,\dots ,y_t+y_c,\dots ,y_n⟩$. Applying this rule twice gives $C^2=I$; it permutes the ordered orthonormal basis, so $C=C^{\ast }$. On a basis vector, in $C{X}_{c}C$ the right CNOT first changes $y_t$ to $y_t+y_c$, the middle $X_c$ changes $y_c$ to $y_c+1$, and the left CNOT changes the target to $y_t+y_c+(y_c+1)=y_t+1$. Thus $C{X}_{c}C=X_c{X}_t$. In $C{X}_{t}C$, the right CNOT changes the target to $y_t+y_c$, the middle $X_t$ toggles it, and the left CNOT toggles it back by $y_c$, leaving $y_t+1$; hence $C{X}_{t}C=X_t$. The middle $Z_c$ contributes $(-1{)}^{y_c}$ and the two CNOTs restore the bits, giving $C{Z}_{c}C=Z_c$. The middle $Z_t$ contributes $(-1{)}^{y_t+y_c}$, giving $C{Z}_{t}C=Z_c{Z}_t$.

For arbitrary distinct wires $c,t\in \{1,\dots ,n\}$, assign source positions $0,1$ to $c-1,t-1$. This partial assignment is injective; list its remaining source and target positions in increasing order and match them in order to extend it to a permutation $\sigma$. By [F6], $P_{\sigma }$ moves those factors into the first two positions and permutes an orthonormal basis bijectively, so $P_{\sigma }$ is unitary. The operator $P_{\sigma }^{-1}(C_{1\to 2}\otimes I_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}})P_{\sigma }$ therefore has the stated basis action, and its Pauli conjugation rules are the first-two-wire rules of step 1.1 with local wire names $1,2$ replaced by $c,t$.

Write $P(k,x,z)$ as its ordered product of all $X$-factor maps followed by all $Z$-factor maps. Conjugation preserves this product order. Using step 2.1, the images of the $X$ factors combine to $X_c^{x_c}{X}_t^{x_t+x_c}$ with all other $X$ exponents unchanged; the images of the $Z$ factors combine to $Z_c^{z_c+z_t}{Z}_t^{z_t}$ with all other $Z$ exponents unchanged. Tensor-map composition in [F5] justifies these factorwise products, and no $X$ factor is moved past a $Z$ factor. Thus no scalar is introduced, $k$ is unchanged, and the stated binary updates follow.

Put $p=x\cdot z\in {\mathbb{F}}_2$ and use its representative $0$ or $1$. By [F1], equality $P^{\ast }=P$ is equivalent to $2p-k\equiv k(\mathrm{m}\mathrm{o}\mathrm{d}4)$, or $2(k-p)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}4)$, which holds exactly when $k-p$ is even, that is, $k\equiv p(\mathrm{m}\mathrm{o}\mathrm{d}2)$.

The same product formula gives $P^2=i^{2(k+p)}I=(-1{)}^{k+p}I$, which equals $I$ exactly under the parity condition in 1.1. Conversely, if $P$ is Hermitian then 1.1 gives that condition.

The dot product is linear in each variable, and the displayed formula is a sum of two such terms; hence $\omega$ is bilinear in each of its two vector arguments.

For every $(x,z)$, $\omega ((x,z),(x,z))=x\cdot z+z\cdot x=2(x\cdot z)=0$ in ${\mathbb{F}}_2$, so the form is alternating. Swapping the arguments leaves its displayed value unchanged, so it is symmetric.

If $x_j=1$ for some $j$, then $\omega ((x,z),(0,e_j))=1$; if $x=0$ and $z_j=1$, then $\omega ((0,z),(e_j,0))=1$. Thus every nonzero vector pairs nontrivially with some vector, which is nondegeneracy.

The $2n$ vectors $(e_j,0)$ and $(0,e_j)$ span by coordinate expansion; a zero linear combination has every coordinate zero, so they are linearly independent. By [F3] they form a basis, and [F4] gives dimension $2n$.

By the one-factor actions in [F3] and the factorwise tensor-map rules in [F4], $P(k,x,z)\mathrm{\mid }y\text{〉}=i^k(-1{)}^{z\cdot y}\mathrm{\mid }y+x\text{〉}$. Distinct bit strings give distinct basis vectors by [F2], so the output basis index of the image of |0〉 is x.

Suppose $P(k,x,z)=\lambda P(k^{\mathrm{\prime }},x^{\mathrm{\prime }},z^{\mathrm{\prime }})$ for a nonzero scalar $\lambda$. Applying both sides to $\mathrm{\mid }{0}^n⟩$ gives nonzero multiples of $\mathrm{\mid }x⟩$ and $\mathrm{\mid }{x}^{\mathrm{\prime }}⟩$; distinct bit strings index distinct basis vectors by [F2], so $x=x^{\mathrm{\prime }}$. Comparing the coefficients of this common basis vector gives $i^k=\lambda i^{k^{\mathrm{\prime }}}$. Applying the operators to $\mathrm{\mid }{e}_j⟩$ gives the common output basis vector $\mathrm{\mid }{e}_j+x⟩$ with coefficients $i^k(-1{)}^{z_j}$ and $\lambda i^{k^{\mathrm{\prime }}}(-1{)}^{z_j^{\mathrm{\prime }}}$; their equality and the preceding phase equality imply $z_j=z_j^{\mathrm{\prime }}$ for every $j$. Thus operators equal up to scalar exactly when their binary labels agree; when $\lambda =1$, the same coefficient comparison gives $k=k^{\mathrm{\prime }}$ modulo $4$, so the exact parameter triple is unique.

The parameter uniqueness in step 2.1 makes $\pi$ an unambiguous map on operators. The product formula [F1] makes $\pi$ a homomorphism; its kernel is exactly the zero-label operators $P(k,0,0)=i^{k}I=Z_n$, and every $(x,z)$ is the image of $P(0,x,z)$. The scalar set $Z_n$ is a subgroup because it contains $I$ and is closed under products and inverses; it is central by [F1]. Hence $P\sim Q$ is an equivalence relation: $P^{-1}P=I\in Z_n$, $Q^{-1}P=(P^{-1}Q{)}^{-1}\in Z_n$ whenever $P^{-1}Q\in Z_n$, and $P^{-1}R=(P^{-1}Q)(Q^{-1}R)\in Z_n$ whenever both factors lie in $Z_n$. Its class $[P]$ is the right coset $P{Z}_n$, since $P^{-1}Q\in Z_n$ exactly when $Q=Pz$ for some $z\in Z_n$. If representatives change from $P,Q$ to $Pz,Qw$ with $z,w\in Z_n$, centrality gives $PzQw=PQzw$, so $[P][Q]=[PQ]$ is well-defined. Step 2.1 makes the induced coset map injective, while $P(0,x,z)$ gives surjectivity. It is therefore the asserted quotient isomorphism.

The 2n vectors (e_j,0) and (0,e_j) span V_n by coordinate expansion and are linearly independent because a zero linear combination has each x and z coordinate zero. They form a basis by [F5], so dim V_n=2n.

By [F2], each of the $2n$ conjugated generators is some $P(k,x,z)$; [F1] makes this phase and label unique, so the phase vector and binary columns are well-defined.

The labels of $X_1,\dots ,X_n,Z_1,\dots ,Z_n$ are the ordered coordinate basis of $V_n$ by [F3]. Let their image labels be ${\mathrm{\ell }}_1,\dots ,{\mathrm{\ell }}_{2n}$ and define $S_U(a_1,\dots ,a_{2n})={\sum }_{j=1}^{2n}{a}_j{\mathrm{\ell }}_j$. Coordinatewise addition and scalar multiplication distribute over this finite sum, so $S_U$ is linear and takes each ordered basis vector to its prescribed column. Any other linear map with those columns agrees on every vector because every vector is the corresponding finite coordinate combination. Multiplying $U$ by any unit-modulus scalar leaves each conjugation unchanged, so its phase vector and tableau are unchanged.

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.

For $s\in \{0,1,2,3\}$, the standard coordinate vectors form a basis of ${\mathbb{F}}_2^s$ by coordinate expansion and coordinatewise independence, so $\dim {\mathbb{F}}_2^s=s$. Let $d\in \{2,3\}$ and let $U$ be a proper subspace of ${\mathbb{F}}_2^d$. Since $U$ is finite, choose a linearly independent subset $B\subseteq U$ maximal under inclusion; maximality makes it span $U$, since any vector outside its span could be adjoined while preserving independence. If $r=\mathrm{\mid }B\mathrm{\mid }$, its $2^r$ binary coefficient lists give distinct vectors by independence and exhaust $U$ by spanning, so $\mathrm{\mid }U\mathrm{\mid }=2^r$. But $\mathrm{\mid }{\mathbb{F}}_2^d\mathrm{\mid }=2^d$ and $U$ is proper, hence $r<d$. Enumerate $B=(q_1,\dots ,q_r)$ and define $A_B:{\mathbb{F}}_2^d\to {\mathbb{F}}_2^r$ by $A_B(\alpha )=(\alpha \cdot q_1,\dots ,\alpha \cdot q_r)$. Each coordinate dot product is linear in $\alpha$, so $A_B$ is linear [F4]. Its domain and codomain have dimensions $d$ and $r$ by the coordinate-basis calculation. Its image is a finite subspace; a maximal independent subset spans it as above, and its $2^{\mathrm{rank}{A}_B}$ distinct binary combinations lie among the $2^r$ vectors of ${\mathbb{F}}_2^r$, so its rank is at most $r$. Thus rank-nullity [F2] gives $\dim \ker A_B=d-\mathrm{rank}{A}_B\ge d-r>0$. For nonzero $\alpha \in \ker A_B$, every basis vector $q_i$ satisfies $\alpha \cdot q_i=0$, so linearity and spanning give $\alpha \cdot u=0$ for every $u\in U$. The functional $u\mapsto \alpha \cdot u$ is nonzero because its value on a coordinate vector with nonzero corresponding coordinate of $\alpha$ is $1$.

Alternation and bilinearity imply $0=\omega (u+w,u+w)=\omega (u,w)+\omega (w,u)$ for all $u,w$; since subtraction equals addition in ${\mathbb{F}}_2$, $\omega$ is symmetric. For $v=0$, ${\tau }_v$ is the identity. For any $v$, alternation gives $\omega (v,v)=0$, so applying ${\tau }_v$ twice adds $\omega (w,v)v$ twice and returns $w$. For $u,w\in V$, bilinearity gives $\omega ({\tau }_{v}u,{\tau }_{v}w)=\omega (u,w)+\omega (w,v)\omega (u,v)+\omega (u,v)\omega (v,w)\mathrm{.}$ Symmetry from the first sentence makes the last two terms the same product, which sums to zero in ${\mathbb{F}}_2$; therefore ${\tau }_v$ preserves $\omega$.

At $n=0$, $\dim V=0$ implies $V=\{0\}$ by [F3]. Its identity is the only symplectic map and is the empty composition of transvections.

These maps act transitively on nonzero vectors. If $a=b$, no map is needed. If $\omega (a,b)=1$, then $v=a+b$ satisfies $\omega (a,v)=1$, hence ${\tau }_v(a)=b$. If $a\mathrm{\ne }b$ and $\omega (a,b)=0$, then $a,b$ are independent over ${\mathbb{F}}_2$. Their pairing functionals are independent: a relation $r\omega (a,\cdot )+s\omega (b,\cdot )=0$ gives $\omega (ra+sb,w)=0$ for every $w$, so nondegeneracy gives $ra+sb=0$, and independence gives $r=s=0$. The map $L(w)=(\omega (a,w),\omega (b,w))$ is linear by bilinearity. If its image were proper, step 1.1 would give a nonzero $\alpha \in {\mathbb{F}}_2^2$ with $\alpha \cdot L(w)=0$ for every $w$. This would make a nontrivial linear combination of the pairing functionals zero, a contradiction. Thus $L$ is onto; choose $c$ with both pairings $1$. By symmetry from step 1.2, $\omega (c,b)=1$, so ${\tau }_{a+c}(a)=c$ and ${\tau }_{c+b}(c)=b$.

Fix $e,f$ with $\omega (e,f)=1$. If $y$ and $f$ both pair to $1$ with $e$, then transvections fixing $e$ send $y$ to $f$ as follows. If $y=f$, use the identity. If $\omega (y,f)=1$, the center $y+f$ lies in $e^{\perp }$ and ${\tau }_{y+f}(y)=f$. If $y\mathrm{\ne }f$ and $\omega (y,f)=0$, the vectors $e,y,f$ are independent: pairing a relation $re+sy+tf=0$ with $e$ gives $s=t$ by symmetry from step 1.2; if $s=t=1$, then $y+f=re$, which would give either $y=f$ or $\omega (y,f)=\omega (f+re,f)=r=1$, both impossible. Their pairing functionals are independent because a relation among them is the pairing with the corresponding linear combination of $e,y,f$, which nondegeneracy forces to be zero. The map $L(w)=(\omega (e,w),\omega (y,w),\omega (f,w))$ is linear by bilinearity. If its image were proper, step 1.1 would give a nonzero $\alpha \in {\mathbb{F}}_2^3$ annihilating every value of $L$, contradicting independence of the three pairing functionals. Hence $L$ is onto; choose $c$ with all three values $1$. The centers $y+c$ and $c+f$ lie in $e^{\perp }$, and ${\tau }_{c+f}{\tau }_{y+c}(y)=f$; both transvections fix $e$.