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