Given $n-k$ stabiliser generators, how can we find an additional $k$ commuting generators?

I am trying to understand "Stabilizer codes construction" in Nielsen & Chuang (page 465). Below, we're working in a Hilbert space of dimension $$2^n$$, and $$G_n$$ is the $$n$$-qubit Pauli group.

A stabilizer group $$S=\langle g_1,...,g_{n-k} \rangle \subseteq G_n$$ is a commuting subgroup of Pauli operators such that $$-I \notin S$$. Below, we suppose that the operators $$g_j$$ are independent, in which case the stabilised space $$V_S$$ has dimension $$2^k$$.

Given $$n-k$$ generators, from their representation in terms of bit-vectors, it is easy to see that we can always find some $$k$$ additional independent generators. However, how can we be sure that we can always find $$k$$ additional commuting generators?

• Hi StarBucK − I think it would be better if you split your post into separate posts for each question. Apart from both involving stabiliser codes, the two questions don't seem to be closely tied to one another. – Niel de Beaudrap Aug 29 at 14:23
• @NieldeBeaudrap Allright ! I edited this one – StarBucK Aug 29 at 14:35
• I hope you don't mind, but I've condensed your question substantially. – Niel de Beaudrap Aug 29 at 14:46
• @NieldeBeaudrap, sure it's fine =) – StarBucK Aug 29 at 14:48

The way that I tend to think about it is to write out the $$(n-k)\times 2n$$ binary matrices specifying the generators. The first $$n$$ bits of each row are the locations of Pauli $$X$$ matrices, while the second $$n$$ are the locations of the Pauli $$Z$$ matrices. $$G=\left(\begin{array}{c|c} G_x & G_z \end{array}\right)$$
Now, imagine we introduce a new stabilizer $$g=(x|z)$$. It is linearly independent if $$G\cdot G^t\equiv 0\text{ mod }2$$. Also, it commutes if $$G\cdot (z|x)^T\equiv 0\text{ mod }2$$. In other words, we're looking for a vector that satisfies $$\left(\begin{array}{c|c} G_x & G_z \\ G_z & G_x \end{array}\right)\cdot g\equiv 0\text{ mod }2.$$ Hence, we simply seek a member of the Null Space, modulo 2, of the big matrix.
Example: Think of the 3-bit majority vote. It has stabilizers $$Z_1Z_2$$ and $$Z_2Z_3$$. We can perform the necessary computation with Mathematica:
We get two possible answers (note, however, that these do not mutually commute): $$Z_1Z_2Z_3$$ and $$X_1X_2X_3$$. Note, of course, that we can reduce the $$Z$$ terms by removing products of stabilizers, returning something like $$Z_1$$.
• Thanks. To be sure I understood: your condition $G.G^T=0$ is a sufficient (but not necessary) condition for linearly independant $g$ right ? And you are ensured that there exist an element in the Kernel of your big matrix that I call $\widetilde{G}$ that is of size $2(n-(k+1)) \times 2n$ (the $+1$ because I added the new generator) because $Dim(Ker(\widetilde{G}))=2n-Dim(Im(\widetilde{G}))$. As $\widetilde{G}$ has less than $2n$ lines, $Dim(Ker(\widetilde{G})) > 0$ and the $g \neq 0$ we are looking for exists. Would you agree ? – StarBucK Sep 2 at 9:25