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

Question

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?

Answer 1

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:

NullSpace[{{1, 1, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 1}}, Modulus -> 2]

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$.