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

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.

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.
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.
• It's just $C_2^T$ in the place of $E_2^TC_2^T$ May 2 at 19:44