# Knill-Laflamme condition and requirements for error correction

Suppose we have a stabilizer group $$\mathcal{M}$$, the Knill-Laflamme condition for error correction states

An error with Kraus operators $$\{E_k\}$$ is correctable if either $$E^\dagger_kE_l\in\mathcal{M}\quad\forall\, k,l$$ or there exists $$M\in\mathcal{M}$$ such that $$\{M,E_k^\dagger E_l\}=0\quad\forall \,k,l$$

I really don't understand how either of these conditions being true helps us correct errors. Every source I can find then goes on and talks about if an error $$E$$ occurs that anticommutes with some $$M$$, then

$$ME|\psi\rangle=-E|\psi\rangle$$

so we measure $$-1$$ for $$M$$ and hence we can correct $$E$$. But I fail to see how this is what the condition is talking about, $$E$$ here seems to be some unitary and $$M$$ anticommutes with it, while the condition talks about Kraus operators and $$M$$ anticommuting with products of them, if the error of the condition occurs I expect a transformation like

$$\rho=|\psi\rangle\langle \psi|\rightarrow\rho'=\sum_k E_k|\psi\rangle\langle\psi|E_k^\dagger$$

Which in general cannot be expressed as $$E|\psi\rangle$$ for some unitary $$E$$. Moreover, in this case I cannot see how $$M$$ anticommuting with $$E_k^\dagger E_k$$ helps us correcting the error, or for that matter how $$E_k^\dagger E_l$$ being in $$\mathcal{M}$$ helps.

How can I see how the conditions allow us to detect and correct errors?

• for anybody stumbling upon this question, in addition to the accepted answer and discussion witht the answerer there is a very useful discussion in Nielsen and Chuang that explicitely show how a very similar condition to this is necessary and sufficient for error correction – user2723984 Jul 30 '19 at 17:40

I believe that this is actually two separate questions; I'll try to explain the issue concerning errors as channels with multiple Kraus operators instead of unitaries first:

You are correct in saying that errors, in general, are not unitary operations. Rather, they are quantum channels that most often have more than 1 Kraus operators. Consider, for instance, the dephasing channel, which has Kraus operators:

$$$$A_{1} = (\sqrt{1-p}I, A_{2} = \sqrt{p}Z,$$$$ i.e. some channel that does nothing with probability $$1-p$$ and applies a $$Z$$ operation that is applied with probability $$p$$.

If we start with some pure state $$|\psi\rangle\langle\psi|$$, after this channel we will have some statistical mixture $$\rho$$ of $$I|\psi\rangle\langle\psi|I$$ and $$Z|\psi\rangle\langle\psi|Z^{\dagger}$$. How can we ever happen to correct this?

The trick is, that we measure (for instance, by stabilizer measurement) if an error has happened. Lets say that we have entangled the qubit with another qubit (the ancilla) in such a way that the ancilla is in the $$|1\rangle$$ state when a $$Z$$ error/unitary has happened, whereas it is in the $$|1\rangle$$ state when nothing (i.e. $$I$$) has happened. What does our state look like, before measurement?. Well:

$$$$\rho_{total} = (1-p)I|\psi\rangle\langle\psi|I \otimes |0\rangle_{anc} + pZ|\psi\rangle\langle\psi|Z^{\dagger} \otimes |1\rangle_{anc}.$$$$

Now comes the trick: we only measure the ancilla. Upon this measurement, our (data) qubit state collapses to either $$I|\psi\rangle$$ or $$Z|\psi\rangle$$. By measuring the (possible) error, we have forced it to discretise itself into a unitary error! If our code is actually well designed, we can now infer from only the ancilla measurements (called the error syndrome) if, and what kind of error there happed.

Now, on to the first part: we can always write any set of Kraus operators as a linear combination of unitaries; for simplicity we always use the Paulis. If our code can correct these Paulis, it can also correct any linear combination of these Paulis (because measuring if anything happened discretises the error into these Paulis. So we don't need to keep track of all possible (literally uncountably many) different Kraus operations, but only a (relatively) small discrete set of Paulis (or other unitaries if you want to)!

Can we then correct all errors? No, unfortunately not. We can never, with one stabilizer code, correct for all different Paulis, but only a subset $$\mathcal{E}$$, called the set of correctable errors. So if (at least) one of our Kraus operators can't be written as a linear combination of only elements of $$\mathcal{E}$$, we can't correct for that Kraus operator.

The conditions you use for QECC's are a bit finicky I believe; the first one is (somewhat) like the actual Knill-LaFlamme conditions, the other one only applies to the (subclass) of stabilizer codes (although most people only consider these types of codes). Also, I don't think it matters very much concerning your confusion.

• By the way, this link contains the lectures of Daniel Gottesman (the inventor of stabilizer codes) on QECC's. It is awesome, but also awesomely detailed, very thorough and very mathematical. If you want a somewhat more straightforward introduction there are myriad introductory texts to be found on the arxiv, like this one. – JSdJ Jul 30 '19 at 15:21
• Hi, thank you for the answer. What I still don't understand is why these conditions allow for correction. Based on what you wrote, I would say that the condition is roughly $\{M_k, E_k\}=0$, in the sense that we must be able to distinguish Kraus operators from one another, or more precisely the condition would be that each Pauli (that we take as Kraus ops) anticommutes with some subset of $\mathcal{M}$, and no two such subsets are equal, so that with each stabilizer measurement we are sure of which error has occurred. Why do the conditions I gave matter? – user2723984 Jul 30 '19 at 15:22
• By the way, you can use \rangle for $\rangle$ and \langle for $\langle$ to write kets and bras – user2723984 Jul 30 '19 at 15:23
• Ha, thanks for that tip, I tried using \ket{} etc. but that didn't work! What you're saying in the comment is exactly right, and is pretty much how I would actually try to explain the conditions. So please keep what you're saying in mind and use that as a leading condition; I find it way more intuitive. However, something like that doesn't account for the fact that two errors $E_{k}$ and $E_{l}$ might very well be different errors, with the same syndrome, but that they don't act differently on the codespace. – JSdJ Jul 30 '19 at 15:28
• Thank you! I still would like to understand it though (you know, exams). I guess the first condition is the relevant one, as the second one is always false for Pauli operators as Kraus... – user2723984 Jul 30 '19 at 15:31