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.


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

  • $\begingroup$ This is nice; at least it gives a systematic way to find the answer. I do assume that the set of errors is the correctable ones. One caveat with this approach is that the set of errors can grow very quickly...for example 20 qubits, 4 errors gives 392445 possibilities (Binomial(20,4)*3^4)...but maybe there's no simpler way. $\endgroup$
    – unknown
    Jul 9, 2022 at 23:06
  • 2
    $\begingroup$ The ideas above may be used to develop other methods that may work better for multi-qubit errors. For example, you can compute the kernel of the check matrix and pick a vector $v\in\ker H$ with the smallest Hamming weight. Then any errors $e$ and $e+v$ have the same syndrome, so if both $e$ and $e+v$ are correctable then you found degeneracy. This approach might be easier for multi-qubit errors. That said, 392445 sounds like something a computer can handle. $\endgroup$ Jul 12, 2022 at 5:44
  • 1
    $\begingroup$ Great answer! So this shows that the Steane code is nondegenerate. It seems that extending a code by a junk qubit is always degenerate. Also it is clear why this method shows nondegeneracy for $ X $ and $ Z $ type errors, could you perhaps comment on how it shows nondegeneracy for $ Y $ type errors? $\endgroup$ Apr 20 at 22:49
  • $\begingroup$ Another great catch! Thank you! See the fixes I made. $\endgroup$ Apr 23 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.