Proof for how logical operators generated systematically will satisfy Pauli commutation

Question

Let me assume a CSS code.

Suppose I have $n$ qubits and have $(n-k)$ stabilizers which we label by the set $S = \{S_1, S_2, .. S_{n-k}\}$. Let me then find $2k$ Pauli operators $L_i$ that are

• Not products of the stabilizers
• Not products of each other and
• Commute with all the stabilizers
• Exclusively $X$-type or $Z$-type operators (not sure if this is a necessary condition)

My understanding is that these are going to be logical $X$ and $Z$ operators on $k$ qubits because of the conditions above. Is this statement true?

If yes, how do I prove it? In particular, how do I show that every $L_i$ commutes with all the other logicals and anticommutes with just one other element from the set of logicals?

Answer 1

The only written proof I know of this is in Gottesman's lecture notes/draft textbook at https://www.cs.umd.edu/class/spring2024/cmsc858G/. This is slightly more general than in your question, as it works for any stabilizer code, not just CSS ones. Specifically, you want Theorem 3.11, whose proof comes right at the end of Chapter 3, after the very handy Lemma 3.15 is given.

A quick summary is: Lemma 3.15 says that given any independent set of Paulis $\{P_1, ..., P_m\}$, and any corresponding set of signs $s_j \in \{-1, +1\}$ for $1 \leq j \leq m$, there are (up to global phase $i^a$) $2^{2n - m}$ Paulis $Q$ such that $QP_j = s_jP_jQ$ for all $j$.

We can then use this to show $N(S)/S \cong P_k$. First we pick the Paulis that will serve as our logical $X$ operators. To pick the first one, we just need any Pauli that commutes with all of the elements of $S$ but isn't already in $S$. By the lemma above, up to global phase, there are $2^{2n-r}$ Paulis with the right commutation relations (where $r = n-k$), but this includes all $2^r$ elements of $S$. So up to global phase there are $2^{2n - r} - 2^{r} = 2^{r}(2^{2n - 2r} - 1)$ Paulis that meet our needs. So long as $n > r$, this is a positive number, and we can choose our first logical $X$ operator $X_1'$.

We can keep doing this until we've picked $k$ logical $X$ operators, at which point the reasoning above tells us there are no more Paulis satisfying the commutativity and independence constraints.

So next we start picking Paulis that will serve as $Z$ logicals. At this point we have an independent set $\{S_1, \ldots, S_r, X_1', \ldots, X_k'\}$ of Paulis, and we first want to pick a $Z_1'$ that commutes with all of these except $X_1'$. Lemma 3.15 says there are $2^{2n - (r + k)} = 2^{2n - (r + n - r)} = 2^{n}$ of these up to global phase - and we don't even need to worry about making sure we pick one that's linearly independent to $\{S_1, \ldots, S_r, X_1', \ldots, X_k'\}$, because the anti-commutation with $X_1'$ takes care of this for us!

So we can carry on doing this until we have the $k$ logical $Z$ operators as well. For more details, see the link above.