Minimum-weight presentation for stabilizer group $S$ and logical Pauli group $N(S)/S$

Question

Given some stabilizer group $S$ with presentation $\langle s_1, \dots, s_r \rangle$, what is known about finding a minimal-weight presentation for it? By this, I mean a new presentation $\langle s_1', \dots, s_r' \rangle$ such that $\sum_{j=1}^{r} wt(s_j')$ is minimised over all possible presentations, where the weight $wt(s_j')$ of a generator is the number of qubits on which $s_j'$ isn't the identity. Can this be done efficiently? Or if not, can an approximate version of the problem be solved efficiently?

Furthermore, what is known about doing a similar thing for $N(S)/ S$? Specifically, suppose we have a presentation $\langle \overline{i}, \overline{x_1}, \overline{z_1}, \ldots, \overline{x_k}, \overline{z_k} \rangle$ for this group, where $k=n-r$, and the representatives $x_j, z_j \in N(S)$ obey the Pauli commutativity relations $[x_j, x_l] = [z_j, z_l] = 0$ and $[x_j, z_l] = 2\delta_{jl}x_jz_l$. What is known about finding a new presentation $\langle \overline{i}, \overline{x_1'}, \overline{z_1'}, \ldots, \overline{x_k'}, \overline{z_k'} \rangle$ such that the commutativity relations are maintained, but the total weights of the representatives $x_j'$ and $z_j'$ are minimised over all possible such presentations?

The first half of this question, about the group $S$, was asked a few years ago on this site: Obtaining low weight stabilizer generators. My real interest is in the second half of this question, about the group $N(S)/S$. I would imagine that solving these problems both efficiently and exactly is too much to ask, but I am equally interested in how good of an approximate answer can be found efficiently.

Any thoughts/references appreciated.

Answer 1

The standard form of the generator matrix is $$ H = \left(\begin{array}{ccc|ccc} I & A_1 & A_2 & B & 0 & C_2 \\ 0 & 0 & 0 & D & I & E_2 \end{array}\right). $$ Here, the columns of the blocks are of size $R$, $r-R$ and $k$ respectively, where $R$ is the rank of the $X$-part of the augmented matrix, $r$ is the number of generators and $k$ is the number of logical qubits. See Nielson and Chuang as reference.

This is obtained by using Guassian reduction operations on the canonical generator matrix of the code, which reduces the total weight of the presentation. This form is lower or equal weight than the canonical form of a code. I suspect that you won't be able to generically do much better than this, if at all.

Your second questions is more difficult to answer. The standard form above yields the logical bit-flips as $$ \begin{pmatrix} 0 & E_2^T & I & | & C_2^T & 0 & 0 \end{pmatrix}, $$ and logical phase-flips as $$ \begin{pmatrix} 0 & 0 & 0 & | & A_2^T & 0 & I \end{pmatrix}. $$ While, the phase-flips are low weight ($(R+1)k$ total weight in the worst case), the bit-flips are high weight ($(n-R+1)k$ in the worst case).

To find lower weight represetantions of these operators one would need to check against the $2^r$ different representations of each operator to find the lowest weight one. This is clearly inefficient. This problem is not even in NP, as one can't test if a given representation is the lowest weight, so one can't even employ approximate SAT solvers.