Given an abelian subgroup $S$ of the Pauli group on $n$ qubits with $r$ independent generators we obtain an $2^{n-r}$-dimensional subspace stabilized by $S$. By picking a basis for this space, it is easy to build a representation of the Pauli group on $k$ qubits generated by some set of matrices $\overline{X_i}, \overline{Z_i}$. However, I fail to see how to do so in a way that ensures that $\overline{X_i}, \overline{Z_i}$ are Pauli matrices in the original basis. The common way to build these logicals is to consider the quotient $\mathcal{N}(S)/S$, and note that it corresponds to the Pauli group on $k$ qubits, but I cannot quite prove it.
1 Answer
$\begingroup$
$\endgroup$
To answer your first question, as to why $N(S)/S \cong P_{n-r}$: this is hinted at in Gottesman's lecture notes (Section 3.4, https://arxiv.org/abs/0904.2557), and more detail is given on Physics SE at https://physics.stackexchange.com/questions/261030/size-of-the-quotient-of-normalizer-by-the-stabilizer-in-the-pauli-group (where the answerer says they are following Gottesman's lecture notes). There's also a fuller proof in his unpublished textbook, which I'll sketch here. I'll follow his notation and use $c(p, q) = 0$ to mean two Paulis $p$ and $q$ commute, or $c(p, q) = 1$ if they anti-commute. Also recall that a Pauli $p = i^k (X_1^{a_1} Z_1^{b_1} \otimes \ldots \otimes X_n^{a_n} Z_n^{b_n}) \in P_n$ can be represented (up to a sign) by a $2n$-bit vector $(a_1, \ldots, a_n, b_1, \ldots, b_n)$.
The key lemma is the following: given independent Paulis $\{p_1, \ldots, p_m\}$ and $m$ bits $\{c_1, \ldots, c_m\}$, there exist $2^{2n-m}$ Paulis $q$ such that $ \forall j$ we have $c(p_j, q) = c_j$. A proof sketch is that, when converting to vector representations, each condition $c(p_j, q) = c_j$ is a linear constraint. Since the Paulis were independent, this gives a non-singular system of $m$ linear equations in a $2n$-dim binary vector space. This has $2^{2n-m}$ solutions.
Then to prove that $N(S)/S \cong P_{n-r}$, we can repeatedly pick cosets $\overline{x_j}$ and $\overline{z_j}$ in $N(S)/S$ whose representatives satisfy the commutativity relations $c(x_j, x_k) = 0, c(z_j, z_k) = 0$ and $c(x_j, z_j) = \delta_{jk}$. This will give us an inclusion of $P_{n-r}$ in $N(S)/S$. But also we can show $|N(S)/S| = |P_{n-r}|$ (see e.g. the Physics SE answer), so inclusion must mean isomorphism.
So suppose we've chosen some independent set of $\overline{x_j}$ and $\overline{z_j}$ cosets and we want to pick one more. We can pick a representative for it; this must be in $N(S)$, so must commute with all $r$ stabilizer generators. It must also commute/anti-commute as desired with the already-chosen coset representatives $x_j$ and $z_j$. By the lemma above, we can find a Pauli that satisfies these linear constraints.
Remains just to ensure that this new coset is independent of the previously chosen ones. I'll be pretentious and leave this as an exercise, because I've got to get back to work...
A question about the rest of your post: almost certainly my fault, but I'm not quite following what you mean about building a representation of $P_k$ generated by $\overline{X_j}$ and $\overline{Z_j}$ such that these are Pauli matrices in the original basis. If you're still curious about this, maybe I can ask more questions and try and help. What's $k$ here, for example?
