Is there a "simple" way to tell if a stabilizer code is degenerate?

Question

Suppose I have a stabilizer code defined by $m$ independent Pauli strings. Is there a "simple" way to check if the code is degenerate or not?

As test cases the $[[5,1,3]]$ code is not degenerate, and Shor's $[[9,1,3]]$ code is.

Answer 1

Set of errors

It is somewhat imprecise to say that a quantum error correcting code is degenerate. Degeneracy means that the code assigns the same syndrome to two different errors, but that is of course true of every code$^1$. Therefore, one should specify the set of errors to be considered. Then the code $C$ is degenerate for the set of errors $\mathcal{E}$ if two distinct errors $e_1,e_2\in\mathcal{E}$ have the same syndrome. Often, $\mathcal{E}$ is implicitly taken to be the set of correctable errors of the code.

(Interestingly, it is impossible for a classical error correcting code to be degenerate for any set of correctable errors.)

Single-qubit errors

It is particularly easy to check if a stabilizer code is degenerate for the set of single-qubit $X$ and $Z$ errors. All we need to do is write down the check matrix $H=[H_Z|H_X]$ and see whether it has two identical columns. We can extend this to all single-qubit errors by expanding the check matrix to $H'=[H_Z|H_X|H_Y]$ where$^2$ $H_Y=H_Z+H_X$ and verifying that all columns of $H'$ are distinct.

For example, the check matrix for the $[[5,1,3]]$ code is

$$ \left[ \begin{array}{ccccc|ccccc} 0&1&1&0&0 & 1&0&0&1&0\\ 0&0&1&1&0 & 0&1&0&0&1\\ 0&0&0&1&1 & 1&0&1&0&0\\ 1&0&0&0&1 & 0&1&0&1&0\\ \end{array} \right] $$ where all columns are distinct. Moreover, $H_Y=H_Z+H_X$ consists of distinct columns with Hamming weight three and four, so $H'$ has distinct columns, too. Therefore, this code is not degenerate for single-qubit errors.

On the other hand, the check matrix for the $[[9,1,3]]$ code is

$$ \left[ \begin{array}{ccccccccc|ccccccccc} 1&1&0& 0&0&0& 0&0&0 & 0&0&0& 0&0&0& 0&0&0\\ 0&1&1& 0&0&0& 0&0&0 & 0&0&0& 0&0&0& 0&0&0\\ 0&0&0& 1&1&0& 0&0&0 & 0&0&0& 0&0&0& 0&0&0\\ 0&0&0& 0&1&1& 0&0&0 & 0&0&0& 0&0&0& 0&0&0\\ 0&0&0& 0&0&0& 1&1&0 & 0&0&0& 0&0&0& 0&0&0\\ 0&0&0& 0&0&0& 0&1&1 & 0&0&0& 0&0&0& 0&0&0\\ 0&0&0& 0&0&0& 0&0&0 & 1&1&1& 1&1&1& 0&0&0\\ 0&0&0& 0&0&0& 0&0&0 & 0&0&0& 1&1&1& 1&1&1\\ \end{array} \right] $$ where some columns, e.g. tenth and eleventh, are identical. Therefore, the $[[9,1,3]]$ code is degenerate.

The reason this procedure works is that the syndrome $S$ of an error given as a binary vector $e=[z_1,\dots,z_n,x_1,\dots,x_n]$ can be computed as

$$ S = H\Lambda e $$

where $H$ is the check matrix and $\Lambda=\begin{bmatrix}0&I\\I&0\end{bmatrix}$ is a matrix that realizes the standard symplectic inner product in $\mathbb{Z}_2^{2n}$.

General procedure

The above procedure directly generalizes to more complicated sets of errors, but instead of comparing columns of the check matrix, we now need to compare their linear combinations.

The most general way to state the above procedures is the following simple algorithm

def is_degenerate(code, errors):
    syndromes = set()
    for e in errors:
        s = code.get_syndrome(e)
        if s in syndromes:
            return True
        syndromes.add(s)
    return False

---

^{$^1$ This is easiest to see for stabilizer codes. Take an error $e$ and a stabilizer $g$. Then $e\ne eg$, but $e$ and $eg$ have the same syndrome, because $g$'s syndrome is trivial.
$^2$ Addition in $H_Y=H_Z+H_X$ is modulo two.}

Answer 2

A distance $ d $ code is nondegenerate (with respect to its set of correctable errors) if and only if the weight enumerator values $ A_i=0 $ for all $ 0<i<d $. This criterion has the advantage that it also works for non-stabilizer codes.

So you can check degeneracy by seeing if any of the $ A_i \neq 0 $ for some $ 0 < i < d $.

Applying this criterion to the stabilizer case we see that a distance $ d $ stabilizer code is degenerate if and only if the stabilizer contains a Pauli error $ E $ of weight $ 0< wt(E)<d $.

Using this we can see that the $ [[9,1,3]] $ Shor code is clearly degenerate since it has stabilizers of weight $ 2 $, and $ 0<2<3 $. On the other hand the $ [[5,1,3]] $ code is nondegenerate because it has no stabilizers of weight $ 1 $ or $ 2 $.

Aside on weight enumerators: The weight enumerators of a code are defined by \begin{align*} A_i &= \frac{1}{(Tr(\Pi))^2} \sum_{E \in \mathcal{E}_i} Tr(E \Pi)Tr(E^\dagger \Pi) \\ B_i &= \frac{1}{Tr(\Pi)} \sum_{E \in \mathcal{E}_i} Tr( E \Pi E^\dagger \Pi) \end{align*} Here $\Pi$ is the code projector and $\mathcal{E}_i$ are the Pauli errors with weight $i$. The code has at least distance $ d $ if and only if both $ A_d < B_d $ and $$ A_i=B_i $$ for all $ i \leq d-1 $.

To construct a code projector for an $ ((n,2,d)) $ with logical code words $ | \overline{0} \rangle $ and $ | \overline{1} \rangle $ the code projector $ \Pi $ is given by $$ \Pi= | \overline{0} \rangle \langle \overline{0} | + | \overline{1} \rangle \langle \overline{1} | $$