Quotient of Pauli group isomorphism

Question

This question arose when studying about quantum error correction and the stabilizer formalism but I will formulate it in a purely group-theoretic way. Let $$\mathcal{G}_n = \{I, X, Y, Z\}^{\otimes n} \times \{\pm 1, \pm i\}$$
be the $n$-qubit Pauli group, where $I$ is the identity and $X$, $Y$, $Z$ are the Pauli matrices.

Consider now a subgroup $S=\langle g_1, \dotsc, g_{n-k}\rangle$ of $\mathcal{G}_n$, such that these generators are independent and commute with each other, and $-I^{\otimes n} \notin S$.

Let $N(S)$ denote the normalizer of $S$ in $\mathcal{G}_n$ and $\mathcal{G}_k$ the $k$-qubit Pauli group. I would like to show that $N(S)/S \simeq \mathcal{G}_k$. This fact is mentioned in a few papers (for example Gottesman - Stabilizer Codes and Quantum Error Correction) but without rigorous proof.

In Verdon - Fault tolerant quantum computation document it is briefly discussed and justified by claiming the existence of an automorphism of $\mathcal{G}_n$ that maps the generators of $S$ to $\{X_1, X_2, \dotsc, X_{n-k}\}$ but I cannot see how to prove this.

I have posted this question on Quantum Computing SE but I'm posting it here as well because it seems more complicated than I initially thought it was.

Answer 1

Here is a sketch of a similar answer to @MichalJan's but from a group-theoretic angle.

Define a group $G$ to be of "Pauli type" if and only if (a) $Z(G)$ is cyclic of order $4$ and (b) $G/\langle t^2\rangle$ is an elementary abelian $2$-group, where $t$ is a generator of $Z(G)$.

Lemma 1. $G$ is of Pauli type if and only if $G\cong {\cal G}_n$ for some $n\ge0$. (By convention let's say ${\cal G}_0=Z_4$.)

This is pretty routine in the reverse direction. In the forward direction, the case $|G|=2^4$ is instructive. (Take $x,y$ generating $G$ modulo $Z(G)$, then after possibly replacing $x$ by $xt$ and/or $y$ by $yt$, map $x$ to $X$ and $y$ to $Y$. Note that $[G,G]=\langle t^2\rangle$ and $[x,y]=t^2$ as consequences of neither $x$ nor $y$ being in $Z(G)$.) For general $G$ in the forward direction, the form $(xZ(G),yZ(G))=[x,y]$ is a bilinear $F_2$-valued form on $G/Z(G)$ -- identify $\langle t^2\rangle$ with $F_2$. This form is also alternating. It is also nondegenerate, since we've factored out $Z(G)$. A well-known theorem asserts that any finite-dimensional vector space admitting a nondegenerate alternating bilinear form is the orthogonal sum of nondegenerate $2$-subspaces. It follows that $G=G_1\cdots G_n$ for some $n$ (namely, $|G|=2^{2n+2}$) where each $G_i\cong{\cal G}_1$, $[G_i,G_j]=1$ for $i\ne j$, and $Z(G_1)=\cdots=Z(G_n)=Z(G)$. This implies $G$ is unique up to isomorphism, proving the lemma.

Now let $G={\cal G}_n$ and $S\le G$ with $S\cap Z(G)=1$. Then $S\cong SZ(G)/Z(G)$ is elementary abelian. Let's assume $|S|=2$, since the general case $|S|=2^k$ ought to follow by an induction argument, taking one generator at a time. So say $S=\langle s \rangle$.

Lemma 2. $N_G(S)=C_G(S)$.

This is because $[N_G(S),S]\le S\cap[G,G]\le S\cap Z(G)=1$.

Lemma 3. $N_G(\langle s \rangle)/\langle s\rangle $ is of Pauli type, and isomorphic to ${\cal G}_{n-1}$.

Let $N=N_G(S)$ and $\overline N=N/S$. Then using the form defined above, and Lemma 2, $N/Z(G)$ is the orthogonal of the $1$-dimensional subspace $SZ(G)/Z(G)$. By nondegeneracy, the orthogonal of the orthogonal of any subspace is the original space. So $C_{G/Z(G)}(N/Z(G))=SZ(G)/Z(G)$ and this implies that $Z(N/S)=SZ(G)/S$, which is cyclic of order $4$. Also it is obvious that $N/S\langle t^2\rangle$ is elementary abelian.

Note that $N/SZ(G)$ is a hyperplane of $G/Z(G)$, so $|N/S|=|G|/4$.

Lemma 3 implies your result.

Answer 2

TL;DR: Go to Majorana representation, and then it's a bunch of linear algebra.

---

This turned out a lot lengthier then I expected. I'm sure that there is some clever group-theoretic one-line proof, but here I also provide a construction of the isomorphism, which I think might be useful. I believe there is a lot that can be improved, so I'm open to all comments and suggestions!

---

Lemma: $N(S)$ is equal to the centralizer $C(S)$.

Proof: Let $h$ be an element of $N(S)$. By definition $N(S) = \{h\in\mathcal{G}_n\;|\;\forall s\in S: hsh^{-1} \in S\}$. For any $g,g'\in\mathcal{G}_n$, we have $gg' = \pm g'g$. Then, we know that $h g_i h^{-1} = \pm g_i \in S$, However, $-1\notin S$, so it must be that $h g_i h^{-1} = g_i$. Hence, the normalizer of $S$ is equal to its centralizer $C(S)$.

---

Majorana representation

Let's use Majorana representation for the Pauli group. We define Majorana operators \begin{align} \gamma_1 &= X\otimes I^{\otimes(n-1)} \\ \gamma_2 &= Y\otimes I^{\otimes(n-1)} \\ \gamma_3 &= Z\otimes X \otimes I^{\otimes(n-2)} \\ \gamma_4 &= Z\otimes Y \otimes I^{\otimes(n-2)} \\ &\vdots \\ \gamma_{2n-1} &= Z^{\otimes(n-1)}\otimes X \\ \gamma_{2n} &= Z^{\otimes(n-1)}\otimes Y \end{align}

In general \begin{equation} \gamma_{2i-1} = Z^{\otimes (i-1)}\otimes X \otimes I^{\otimes (n-i)}\,,\qquad \gamma_{2i} = Z^{\otimes (i-1)}\otimes Y \otimes I^{\otimes (n-i)}\,. \end{equation} We have $\gamma_i^2 = 1$ and $\gamma_i\gamma_j = -\gamma_j\gamma_i$ for $i\neq j$. We can also write down an inverse relation \begin{equation} Z^{(i)} = \gamma_{2i-1}\gamma_{2i}\,,\qquad X^{(i)} = \gamma_1\dots \gamma_{2i-1}\,,\qquad Y^{(i)} = \gamma_1\dots \gamma_{2i}\,,\qquad \end{equation} where $P^{(i)} = I^{\otimes(i-1)}\otimes P \otimes I^{\otimes(n-i)}$, $P\in\{I,X,Y,Z\}$ denotes Pauli operator acting on $i$th qubit, and we use convention $XY=Z$.

Any Pauli string can be written a product of Majorana operators: \begin{equation} \mathcal{G}_n \ni \alpha g_{\boldsymbol{a}} = \alpha \gamma_1^{a^1}\dots \gamma_{2n}^{a^{2n}}\,,\qquad a^i\in\{0,1\}\,,\qquad \alpha\in\{\pm 1,\pm i\} \end{equation} so we can represent any Pauli string using a vector $\boldsymbol{a} = (a^1,\dots, a^{2n})^T$ and the global phase $\alpha$. Multiplication of two Pauli strings $\boldsymbol{a}$ and $\boldsymbol{b}$ is equivalent to addition of their vectors $\boldsymbol{a} + \boldsymbol{b}$ modulo 2. We will thus treat $\boldsymbol{a}$ as elements of a vector space over a $\mathbb{Z}_2$ field. Then, the set of generators $g_i$ is independent iff their corresponding vectors $\boldsymbol{a}_i$ are linearly independent (again, modulo 2).

A product of two Majorana strings is \begin{equation} g_{\boldsymbol{a}} g_{\boldsymbol{b}} = (-1)^{b^1(a^2+\dots+a^{2n}) + b^2(a^1 + a^3+\dots+a^{2n})+ \dots} g_{\boldsymbol{b}} g_{\boldsymbol{a}} \,. \end{equation} $g_{\boldsymbol{a}}$,$g_{\boldsymbol{b}}$ thus commute iff \begin{equation} \boldsymbol{a}^T Q \boldsymbol{b} = 0\,,\qquad Q = \begin{pmatrix} 0 & 1 & 1 & \dots \\ 1 & 0 & 1 & \dots \\ 1 & 1 & 0 & \dots \\ \vdots &\vdots &\vdots &\ddots \end{pmatrix}\,. \end{equation} Matrix $Q$ is invertible ($Q^2 = 1$).

Finding the centralizer

We introduce an $(n-k)\times 2n$ matrix \begin{equation} A = \begin{pmatrix} \boldsymbol{a}_1^T \\ \vdots \\ \boldsymbol{a}_{n-k}^T \end{pmatrix} = \begin{pmatrix} a_1^1 & a_1^2 & \dots & a_1^{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n-k}^1 & a_{n-k}^2 & \dots & a_{n-k}^{2n} \\ \end{pmatrix}\,, \end{equation} whose rows are linearly independent (because $g_i$ are independent). The nullspace of this matrix is $(2n-(n-k))=(n+k)$-dimensional. The condition for Pauli string $\boldsymbol{b}$ to commute with all $\boldsymbol{a}_i$ (i.e. to be in the centralizer $C(S)$) is \begin{equation} AQ \boldsymbol{b} = 0\,. \end{equation} Since $Q$ is invertible, the dimension of nullspace of $AQ$ (which is the dimension of $C(S)$), is same as $A$, which is $(n+k)$. $S$ is $(n-k)$-dimensional, thus $C(S)/S$ has $\dim C(S) - \dim(S) = 2k$ independent generators.

Isomorphism

Now we will construct the isomorphism with $\mathcal{G}_k$.

We proceed as follows:

Take from the nullspace of $AQ$ an element $\boldsymbol{z}_1$ linearly independent of $\boldsymbol{a}_i$s, and let \begin{equation} A_1 = \begin{pmatrix} \boldsymbol{a}_1^T \\ \vdots \\ \boldsymbol{a}_{n-k}^T \\ \boldsymbol{z}_1^T \end{pmatrix}\,. \end{equation} We find the nullspace of $A_1 Q$ (which is $(n+k-1)$-dimensional), and take from it an element $\boldsymbol{z}_2$ linearly independent of $\boldsymbol{z}_1$ and $\boldsymbol{a}_i$. Now let \begin{equation} A_2 = \begin{pmatrix} \boldsymbol{a}_1^T \\ \vdots \\ \boldsymbol{a}_{n-k}^T \\ \boldsymbol{z}_1^T \\ \boldsymbol{z}_2^T \end{pmatrix}\,. \end{equation} and repeat until you get $\boldsymbol{z}_1,\dots, \boldsymbol{z}_k$. At this point $A_k$ will be a $n\times 2n$ matrix, thus the nullspace of $A_kQ$ ($n$-dimensional) will not have any elements liearly independent of $\boldsymbol{z}_j$ and $\boldsymbol{a}_i$.

We use $\boldsymbol z_i$ to construct operators $\tilde Z_i = g_{\boldsymbol{z}_i}$. By construction $\tilde Z_i$ all pairwise commute, and commute with all $g_i$. They will be $Z$ operators of $\mathcal{G}_k$. To find the $X$ operators, we must find $\tilde X_i$ such that,

1. $\tilde X_i \tilde Z_i = -\tilde Z_i \tilde X_i$ and
2. $\tilde X_i \tilde Z_j = \tilde Z_j \tilde X_i$ for $i\neq j$ and
3. $\tilde X_i g_j = g_j \tilde X_i$ and
4. $\tilde X_i \tilde X_j = \tilde X_j \tilde X_i$

We proceed similar as before. We find $\boldsymbol x_i$ ($i=1,\dots k$) by solving \begin{equation} A_k Q \boldsymbol x_i = (\underbrace{0,\dots, 0}_{n-k+i-1},1,0\dots)^T \equiv \boldsymbol e_{n-k+i}\,, \end{equation} where $1$ on the right hand sides accounts for anticommutation condition 1. $\boldsymbol x_i$s are only defined up to the nullspace of $A_kQ$. This will be necessary to satisfy condition 4.

The generators of nullspace of $A_k Q$ are the rows of $A_k$. Thus for our solutions $\boldsymbol x_i$, which satisfy condition 1-3, we can take \begin{equation} \boldsymbol x'_i = \boldsymbol x_i + A_k^T \boldsymbol r_i\,, \end{equation} which also satisfy these conditions. Now we want to make sure that $\tilde X_i \equiv g_{\boldsymbol x'_i}$ commute with each other (condition 4). This is equivalent to \begin{equation} \boldsymbol x'^T_j Q\boldsymbol x'_i = 0 \\ (\boldsymbol x_j^T + \boldsymbol r_j A_k) Q (\boldsymbol x_i + A_k^T \boldsymbol r_i) = 0 \\ \boldsymbol x_j^T Q \boldsymbol x_i + \boldsymbol x_j^T Q A_k^T \boldsymbol r_i + \boldsymbol r_j^T A_k Q \boldsymbol x_i = 0 \\ \boldsymbol x_j^T Q \boldsymbol x_i + \boldsymbol e_{n-k+j}^T \boldsymbol r_i + \boldsymbol r_j^T \boldsymbol e_{n-k+i} = 0 \\ \boldsymbol x_j^T Q \boldsymbol x_i + r_{i,n-k+j} + r_{j,n-k+i} = 0\,. \end{equation} $i,j=1,\dots k$, and each pair $i<j$ corresponds an independent equation. This gives $k(k-1)/2$ independent equations. $r_{i,1},\dots,r_{i,n-k}$ are arbitrary, since they correspond to multiplying $\tilde X_i$ by one of the stabilizers $g_i$. This leaves $r_{i,n-k+1},\dots,r_{i,n}$, $i=1\dots k$, as variables, of which there are $k\times k$. Thus the (relevant) solution space is $k(k+1)/2$ dimensional.

---

We can check our counting for a simple example $n=k=2$. $k(k+1)/2=3$, so there should be $2^3=8$ independent solutions. Let $\tilde Z_1 = Z\otimes I$, $\tilde Z_2 = I\otimes Z$. The possible choices for $\tilde X_1$, $\tilde X_2$ are then $\tilde X_1 = P_1 \otimes P_2$, $\tilde X_2 = P_2\otimes P_3$, where $P_1,P_3 \in \{X,Y\}$ and $P_2 \in \{1,Z\}$.