# Size of the quotient of normalizer by the stabilizer in the Pauli group [closed]

Let $P_n$ be the Pauli group on the $n$-qubit and $S$ be a stabilizer subgroup of it. Let $N$ be the normalizer of $S$ in $P_n$. In p. 69 of Lidar & Brun, Quantum Error Correction, it mentioned that the size of the quotient $N / S$ is $n-(\text{size of } S)$ , where here 'size' means the size of the smallest generating set of the corresponding group.

I want to know why this fact does hold.

Let $S$ be the stabilizer of some $n$-qubit code, with $r$ generators (what you call the size of $S$).

The normalizer $N(S)$ is a group of logical operations on the code space. Given some input code state $|\psi\rangle$, the state $N|\psi\rangle, N\in N(S)$ is also in the code space. Consider that all the elements of the coset $nS, n\in N(S)$ act on the code space in the same way. So $N(S)/S$ represents all the distinct ways you can act on the code space with $N(S)$. In fact, we can show that $N(S)/S$ is isomorphic to $P_{n-r}$, the Pauli group on $n-r$ qubits.

We know that the code space is going to be of dimension $2^{n-r}$. This can be seen by noting that $\Pi_S=\frac{1}{2^r} \sum_{s\in S} s$ is the projector into the code space, and noting that its trace is $2^{n-r}$, which is the dimension of the space it projects into.

Now, given that the code space encodes $n-r$ qubits, we can show that $N(S)/S$ is isomorphic to $P_{n-r}$. We know that the order (number of elements) of $N(S)/S$ can not be any bigger than that of $P_{n-r}$, because $P_{n-r}$ constitutes all possible distinct actions on the code space, so it suffices to show that $|N(S)/S|=|P_{n-r}|$.

$|S||N(S)/S|=|N(S)|$

$|N(S)||P_n/N(S)|=|P_n|$

so

$|S||N(S)/S||P_n/N(S)|=|P_n|$

It's easy to see that $|P_n|=4\cdot4^{n}$. Think 4 Pauli's, n sites, and 4 possible phases.

$|S|=2^r$ where $r$ is the number of generators of $S$.

Finally, $|P_n/N(S)|=2^r$. This is because $|P_n/N(S)|$ counts the number of error syndromes (think of each coset as the set of logical operations associated with $N(S)$ accompanied by a single detectable error). And there are $2^r$ error syndromes because measuring each generator of the stabilizer gives one bit of the error syndrome.

Doing some algebra we find that:

$(2^r)|N(S)/S|(2^r)=(4\cdot4^{n})$

$|N(S)/S|=(4\cdot4^{n-r})=|P_{n-r}|$

So $N(S)/S \simeq P_{n-r}$

Given this, we can ask how many generators there are in $P_{n-r}$. By my count there should be $3^{n-r}$ generators (X, Y, or Z applied at the $n-r$ sites). You are claiming the Lidar & Brun say that there are $n-r$ generators. Are you sure you have quoted Lidar & Brun correctly? I do not have a copy of their book.

Shout-out to Daniel Gottesmann, from whose notes I am getting most of this.

• Nice argument for the isomorphism part, I hadn’t realised the order of those groups being equal implied the isomorphism. As for the number of generators of $P_{n-r}$, $Y$ can be generated by $X$ and $Z$, so the number of generators is actually $2^{n-r}$. I think it is a convention, in some physics texts, to call the $\log_2$ of this number the “size”? Commented Dec 21, 2020 at 15:29