3
$\begingroup$

To my understanding, the Steane code cannot fix all possible combinations of errors. It is a $[\![7,1,3]\!]$ code and it is stabilized by $IIIXXXX$, $IXXIIXX$, $XIXIXIX$, $IIIZZZZ$, $IZZIIZZ$, $ZIZIZIZ$.

What are the X errors and the Z errors that this code cannot correct? how can I find these combinations?

$\endgroup$

1 Answer 1

3
$\begingroup$

TL;DR: For every $[\![n,1]\!]$ stabilizer code, such as Steane code, three quarters of all Pauli strings represent uncorrectable erros. We can find the set of uncorrectable errors as the complement of the set of correctable errors which we can find in turn by taking the union of the cosets of the stabilizer group by all corrections known to the decoder. More precisely, the set of uncorrectable errors is $$ \tilde{\mathcal{P}}_n\setminus\bigcup_{v=0}^{2^{n-1}-1}e_v\tilde{S}\tag1 $$ where $\tilde{\mathcal{P}}_n$ is the $n$-qubit projective$^1$ Pauli group, $v=0,\dots,2^{n-1}-1$ are all possible syndromes that may be obtained by measuring stabilizer generators, $e_v$ is the correction the decoder chooses for syndrome $v$ and $\tilde{S}$ is the stabilizer group sans the $\pm$ signs. The cosets $e_v\tilde{S}$ use the (commutative) multiplication in the projective Pauli group.

Syndrome and decoding maps

Let $\sigma:\tilde{\mathcal{P}}_n\to\mathbb{Z}_{2^{n-1}}$ denote the syndrome map that sends an error to the syndrome it produces and $D:\mathbb{Z}_{2^{n-1}}\to\tilde{\mathcal{P}}_n$ the decoding map that sends a syndrome to the correction chosen by the decoder. Note that our definition of $\tilde{\mathcal{P}}_n$ ignores the global phase. Formally, $\tilde{\mathcal{P}}_n$ is the quotient of the $n$-qubit Pauli group $\mathcal{P}_n$ by its center $F=\{+1,+i,-1,-i\}$. The group $\tilde{\mathcal{P}}$ is abelian and all its non-identity elements have order two, so we can think of it as a vector space over $\mathbb{Z}_2$. Similarly, we will think of the set of syndromes $\mathbb{Z}_{2^{n-1}}$ as the set of bit strings of length $n-1$ which is also a vector space over $\mathbb{Z}_2$. For stabilizer codes, $\sigma$ is a linear map$^2$.

Normalizer

The kernel of $\sigma$ is the quotient $N(S)/F$ where $N(S)$ is the normalizer of the stabilizer group $S$ in the Pauli group $\mathcal{P}_n$. We can write any $e\in\ker\sigma$ as $$ e=\overline{X}^x\overline{Z}^zg_1^{k_1}\dots g_{n-1}^{k_{n-1}}\tag2 $$ where $x,z,k_i\in\{0,1\}$. If $x=z=0$ then $e\in\tilde{S}$ is not an actual error since it acts as identity on the code subspace. If at least one of $x$ or $z$ is $1$ then $e$ is a logical operator, i.e. an operator that gives rise to the zero syndrome, but acts non-trivially on the code subspace. If such an operator is applied by the noise then an undetectable and hence uncorrectable error occurs.

Thus, there are $3\cdot 2^{n-1}$ uncorrectable Pauli errors in $\ker\sigma$. Since there are $2^{n+1}$ operators in $\ker\sigma$, we see that three quarters of them are uncorrectable errors.

Errors with non-trivial syndrome

Now consider an error $e$ with non-trivial syndrome $v=\sigma(e)\ne 0$. The error belongs to one of the cosets of $\ker\sigma$, namely $e\in e\ker\sigma$. Assume$^3$ that $D(\sigma(e))=e$. Thus, $e$ is correctable. By equation $(2)$, any other error $e'\in e\ker\sigma$ may be written as $$ e'=e\overline{X}^x\overline{Z}^zg_1^{k_1}\dots g_{n-1}^{k_{n-1}}\tag3 $$ and once again we obtain that $e'$ is correctable if and only if $x=z=0$. In more detail, this follows from the fact that if error $e'=eg_1^{k_1}\dots g_{n-1}^{k_{n-1}}$ occurs then even though the decoder misidentifies it as $e$ the resulting correction $D(\sigma(e'))=e$ differs from $e'$ by a stabilizer. Similarly, if error $e'=e\overline{X}^x\overline{Z}^zg_1^{k_1}\dots g_{n-1}^{k_{n-1}}$ with $x$ or $z$ non-zero occurs then the resulting correction $D(\sigma(e'))=e$ differs from $e'$ by a logical operator.

Thus, the fact - which we saw above - that $\ker\sigma$ splits into four subsets: the stabilizer and the three non-identity logical Pauli operators has its counterpart in every coset $e\ker\sigma$. Namely, the coset splits into four subsets: correctable errors $e\tilde{S}$ and three sets of uncorrectable errors $e\overline{X}\tilde{S}$, $e\overline{Y}\tilde{S}$, $e\overline{Z}\tilde{S}$. Consequently, in every coset of the kernel of $\sigma$ three quarters of Pauli strings represent uncorrectable errors. Thus, three quarters of Pauli strings overall represent uncorrectable errors.

Summary

We can visualize the argument above as a table $$ \begin{array}{c|c|c|c|} \sigma(e)&\overline{I}&\overline{X}&\overline{Y}&\overline{Z}\\ \hline 0 & \tilde{S} & \overline{X}\tilde{S} & \overline{Y}\tilde{S} & \overline{Z}\tilde{S}\\ \hline 1 & e_1\tilde{S} & e_1\overline{X}\tilde{S} & e_1\overline{Y}\tilde{S} & e_1\overline{Z}\tilde{S}\\ \hline \dots&\dots&\dots&\dots&\dots\\ \hline 2^{n-1}-1 & e_{2^{n-1}-1}\tilde{S} & e_{2^{n-1}-1}\overline{X}\tilde{S} & e_{2^{n-1}-1}\overline{Y}\tilde{S} & e_{2^{n-1}-1}\overline{Z}\tilde{S}\\ \hline \end{array} $$ where $e_v$ is a correctable error with syndrome $v$. Thus, we can find all uncorrectable errors by taking the complement of the set of all correctable errors in $\tilde{\mathcal{P}}_n$. We can find all correctable errors as the union of all cosets of the stabilizer group $\tilde{S}$ by every correction known to the decoder, i.e. by every error in the image of the function $D$. This is a restatement of formula $(1)$.

Consequently, three quarters of all Pauli strings are uncorrectable by every $[\![n,1]\!]$ stabilizer code. More generally, the fraction of Pauli strings that represent uncorrectable errors in a $[\![n,k]\!]$ stabilizer code is $\frac{4^n-1}{4^n}$.

Finally, note that even though majority of Pauli strings represent uncorrectable errors the overall probability of those errors may very well be small, especially if error probability decreases quickly with weight, as it does in many practical error models.


$^1$ Projective Pauli group $\tilde{\mathcal{P}}_n$ is a variant of the Pauli group $\mathcal{P}_n$ where the global phase factors are ignored. In particular, $|\tilde{\mathcal{P}}_n|=4^n$ while $|\mathcal{P}_n|=4^{n+1}$.
$^2$ The map $\sigma$ is given by the multiplication with the check matrix and the standard symplectic matrix.
$^3$ This assumption is valid since any sensible decoder can correct at least one error for any given syndrome.

$\endgroup$
6
  • $\begingroup$ Thanks, I appreciate the clear explanation but with $XXXXXXX\circ IIIXXXX=XXXIIII$ repeat for the 2 other stabilizers with X: $IXXIIXX, XIXIXIX$ you get 4 (the XXXXXXX and the 3 ${X,I}$ flipped from the stablizer which means that non-correctable errors are : $XXXXXXX, XXXIIII, XIIXXII, IXIXIXI$ aren't there more non-correctable errors in X? $\endgroup$
    – user206904
    Dec 14, 2022 at 8:48
  • $\begingroup$ is there a formula to know how many non-correctable errors exist? for Steane, I didn't know which ones and how to find them + how many are there (therefore the question) $\endgroup$
    – user206904
    Dec 14, 2022 at 8:49
  • 1
    $\begingroup$ Added a formula counting uncorrectable Pauli errors. You can restrict to $X$ or $Z$ sector by setting the exponents $x$, $z$, $k_i$ associated with the other sector to zero. $\endgroup$ Dec 15, 2022 at 7:58
  • 2
    $\begingroup$ Should we consider something like $XXIIIII$ as an error it cannot correct because it will always be corrected "the wrong way", leading to a logical error? $\endgroup$
    – DaftWullie
    Dec 15, 2022 at 8:12
  • 1
    $\begingroup$ @user206904 Please have a look at the new version of the answer. As DaftWullie pointed out my original answer was incorrect (it discussed undetectable errors, instead of uncorrectable errors). The new analysis covers both (undetectable errors are a special case of uncorrectable errors that have zero syndrome). $\endgroup$ Dec 19, 2022 at 20:32

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.