7
$\begingroup$

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.

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2023 at 22:49
  • $\begingroup$ Another great catch! Thank you! See the fixes I made. $\endgroup$ Apr 23, 2023 at 0:22
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ this makes the codes in the two posts degenerate : quantumcomputing.stackexchange.com/questions/37744/… quantumcomputing.stackexchange.com/questions/26754/… since $A_2 \neq 0$ and $d=3$ $\endgroup$
    – unknown
    Apr 23 at 17:35
  • $\begingroup$ I think the criterion you stated is equivalent to a code being pure, but not necessarily nondegenerate. A code is pure if it satisfies a stronger QEC condition $\Pi E^\ast F \Pi = tr(E^\ast F)\Pi$ for all correctable errors $E, F$, or that errors with distinct syndromes are orthogonal with respect to the Hilbert-Schmidt inner product. For additive/stabilizer codes, nondegenerate and pure are equivalent [Calderbank et al.]. There are also non-additive codes that are nondegenerate, but not pure [Cao et al.]. $\endgroup$ May 13 at 22:14
  • $\begingroup$ I can't edit my comment anymore, but I just want to clarify that this is a valid answer since nondegenerate and pure are equivalent for stabilizer codes. $\endgroup$ May 14 at 0:06

Your Answer

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

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