# Proof for how logical operators generated systematically will satisfy Pauli commutation

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?

• I don't have time for a full answer right now, but two comments: You need that the $S_i$ in your set $S$ are linearly independent (i.e. not products of each other). Also, under those conditions you cannot guarantee that the set of logical operators you happen to write down wiill have pairwise anticommutation. Instead, the $X$-type elements, and the $Z$-type elements each generate a group. WIthin that group, you'll find a presentation such that there are pairs of anti-commutations. (In a 2 qubit system, there's nothing to say you wouldn't pick $X_1,X_2,Z_1,Z_2Z_2$.) Commented Sep 5 at 9:06
• I guess you meant $Z_1Z_2$ in the last bit there but yes, that makes sense! Thanks for the comment. I guess my question asks how to show that the group so generated has pairs of anticommutations and all other elements in it commute
– JRT
Commented Sep 5 at 9:26
• Sure, I just wanted to make sure you weren't trying to prove something that wasn't actually true! Commented Sep 5 at 9:56
• Indeed, thank you!!
– JRT
Commented Sep 5 at 16:20
• Section 10.5.7 of Nielsen & Chuang for construction of the logical operators or stabilizer codes. Exclusively X or Z-type stabilizers is not necessary. But I am not sure what you mean by "these are going to be logical X and Z operators on k qubits". Commented Sep 6 at 0:22

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.