# Proof that for an $[\![n,k,d]\!]$ code we have $N(S)/S\simeq{\cal G}_k$ with $S$ stabilizer

I am reading about Quantum Error Correction and more specifically about the stabilizer formalism. Nielsen's textbook introduces the selection of logical Pauli as a kind of "ad hoc" process which, although intuitive, I think lacks rigor. Later, they provide justification by considering the standard form of a code. Gottesman's thesis presents some argument on page 20, although I can't fully understand it.

Nevertheless, I tried to come up with a proof of the fact that for a $$[\![n,k,d]\!]$$ code $$N(S)/S \simeq \mathcal{G}_k$$, where $$S$$ is the stabilizer, $$N(S)$$ is the normalizer of $$S$$ and $$\mathcal{G}_k$$ is the Pauli group on $$k$$ qubits. To do so I would like to define a group homomorphism as follows:

Select a basis $$\{ |i\rangle: i=0,1,\dots,k-1 \}$$ of the codespace in a way that the action of any $$E\in N(S)$$ can be described as a Pauli operator acting on the codespace. Then it should be easy to show that the kernel of this homomorphism is precisely $$S$$ so by the first isomorphism theorem $$N(S)/S$$ would be isomorphic to a subgroup of $$\mathcal{G}_k$$. A simple order calculation would then conclude that this subgroup is indeed $$\mathcal{G}_k$$. My question is how do we select the basis in a way that guarantees the existence of such homomorphism?

• Pick $k$ mutually commuting elements of $N(S)\setminus S$. Just use those to define logical $|0\rangle^{\otimes k}$. Aug 24, 2023 at 23:41
• @DaftWullie Could you please elaborate? I could pick a basis that contains eigenvectors of all the elements I chose (simultaneous diagonalization) but how would this determine the map $N(S)\to \mathcal{G}_k$? Aug 25, 2023 at 5:42
• It doesn't determine the map. It determines the logical $Z$ operations. You then have to find other elements that anti-commute with exactly one of those logical $Z$ operators, and choose those to define logical $X$. Only once you've done that is your mapping actually determined. (I don't know how that exactly helps you in what you're trying to do!) Aug 25, 2023 at 7:30
• @DaftWullie I am trying to formally prove the existence of an isomorphism between the groups $N(S)/S$ and $\mathcal{G}_k$. I am aware of the process of finding the logical $Z$ operators and then finding the rest by examining the relations they must obey but this doesn't really prove that we can always do that for any code. Aug 25, 2023 at 7:33
• Section 3.1.4 of Frank Gaitan's book discusses this. His proof idea is similar to yours. Though not the cleanest. If you clean it up, please post the answer here. Aug 26, 2023 at 0:31

TL;DR: This can be seen by decoding the $$k$$ logical qubits out of the code subspace into the first $$k$$ physical qubits while keeping track of the stabilizer group.

## Code subspace

Consider an $$[\![n,k]\!]$$ quantum error correcting code. Let $$\mathcal{H}$$ denote the $$2^n$$-dimensional Hilbert space of the block of $$n$$ physical qubits and $$\mathcal C\subset\mathcal H$$ the $$2^k$$-dimensional code subspace of $$k$$ logical qubits. Note that $$\mathcal H$$ contains $$2^{n-k}$$ mutually orthogonal $$2^k$$-dimensional subspaces isomorphic to $$\mathcal C$$. We can index those subspaces with binary strings $$s=s_1s_2\dots s_{n-k}$$ where $$s_i\in\{0,1\}$$. Let $$\mathcal C^s$$ denote the subspace corresponding to the binary string $$s$$. By convention $$\mathcal C^0=\mathcal C$$. The binary strings $$s$$ are called syndromes due to their role in error diagnostics.

## Decoding unitary

Let $$U$$ denote the decoding unitary acting on a block of $$n$$ qubits. Suppose that $$U$$ sends the encoded state $$|\psi\rangle$$ into qubits $$1\dots k$$ and the syndrome $$s$$ into qubits $$k+1\dots n$$. More precisely, suppose that $$U|\tilde\psi^s\rangle=|\psi\rangle\otimes|s\rangle\tag1$$ for $$|\tilde\psi^s\rangle\in\mathcal C^s$$. In particular, $$U$$ sends every logical state $$|\tilde\psi\rangle\in\mathcal C$$ to $$|\psi\rangle\otimes|0_{n-k}\rangle$$.

## Decode logical subspace out into standalone qubits

Let $$\mathcal C'$$ denote the subspace of $$\mathcal H$$ consisting of states of the form $$|\psi\rangle\otimes|0_{n-k}\rangle$$. The stabilizer group $$S'$$ of $$\mathcal C'$$ consists of all $$2^{n-k}$$ operators of the form $$I_1\otimes I_2\otimes\dots\otimes I_k\otimes Z_{k+1}^{b_1}\otimes\dots\otimes Z_n^{b_{n-k}}\tag2$$ where $$b_i\in\{0,1\}$$. Moreover, the normalizer $$N(S')$$ of $$S'$$ in $$\mathcal G_n$$ is equal to its centralizer in $$\mathcal G_n$$ and hence consists of all $$4^{k+1}\cdot 2^{n-k}$$ operators of the form $$i^fP_1\otimes P_2\otimes\dots\otimes P_k\otimes Z_{k+1}^{b_1}\otimes\dots\otimes Z_n^{b_{n-k}}\tag3$$ where $$f\in\{0,1,2,3\}$$, $$P_i\in\{I,X,Y,Z\}$$ and $$b_i\in\{0,1\}$$. Comparing $$(2)$$ and $$(3)$$ we see that $$N(S')\simeq\mathcal G_k\times S'$$. Consequently, $$N(S')/S'\simeq \mathcal G_k$$.

## Encode standalone qubits back into code subspace

Now, if $$P$$ stabilizes $$|\psi\rangle\otimes|0_{n-k}\rangle=U|\tilde\psi\rangle$$ then $$U^\dagger PU$$ stabilizes $$|\tilde\psi\rangle$$. Therefore, $$U^\dagger S' U$$ stabilizes $$\mathcal C$$ and thus $$U^\dagger S' U=S$$. However, conjugation by $$U^\dagger$$ is a group isomorphism, so $$S\simeq S'$$. Similarly, if $$P$$ and $$Q$$ commute (anti-commute), then $$U^\dagger PU$$ and $$U^\dagger QU$$ commute (anti-commute). Therefore, if $$U$$ is Clifford$$^1$$, then $$N(S)\simeq N(S')$$. Putting it all together we obtain $$N(S)/S\simeq N(S')/S'\simeq\mathcal G_k\tag4$$ as expected.

$$^1$$ There is a subtlety here: the normalizer $$N(S)$$ of $$S$$ is defined with respect to the group containing $$S$$. In particular, the normalizer $$N_{\mathcal G_n}(S)$$ of $$S$$ in $$\mathcal G_n$$ is generally different from its normalizer $$N_{U(2^n)}(S)$$ in $$U(2^n)$$. In our case, we work with $$N_{\mathcal G_n}(S)$$, so the proof requires that $$U$$ be Clifford. This is in fact typically the case since we generally choose the logical Pauli operators from $$\mathcal G_n$$. In the more general case, the proof still works (since conjugation by any unitary, Clifford or otherwise, is a group isomorphism), but rigorous notation gets more complicated since we have to keep track of the subgroup of $$U(2^n)$$ that $$\mathcal G_n$$ gets mapped to.

• Thanks for the detailed answer. May I ask why we can make such assumptions about the decoding unitary? Aug 27, 2023 at 6:22
• Do you mean why it takes the form $(1)$ or why it is Clifford? The equation $(1)$ is just a definition of what I mean by "decoding unitary". It's easy to check that it really defines a unitary using the fact that $\mathcal C^s$ and $\mathcal C^t$ are orthogonal if $s\ne t$. We don't have to assume that $U$ is Clifford, but if we do then the proof gets simpler since we don't have to deal with the technicalities connected with going outside $\mathcal G_n$ (such as keep track of the subgroup the normalizer is defined with respect to). Aug 27, 2023 at 6:42
• But why such unitary exists? Aug 27, 2023 at 7:20
• Because for any two ordered bases $B_1$ and $B_2$ there is a unitary that sends $B_1$ to $B_2$. Aug 27, 2023 at 7:31