Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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$.
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.
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.
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.
