# Intuition about Knill-Laflamme QEC conditions

The Knill Laflamme QEC conditions are stated this way:

We consider a code space $$C$$ and its associated projector $$P_C$$.

We consider a noise acting on our system: $$E(\rho)=\sum_a E_a \rho E_a^{\dagger}$$

A necessary & sufficient condition for the existence of an error correction operation correcting $$E$$ is the Knill-Laflamme QEC condition:

$$P_C E_i^{\dagger} E_j P_C=\alpha_{ij} P_C$$

Where $$\alpha_{ij}$$ are coefficient of an Hermitic matrix.

For me this mathematical condition is a little "abstract". I would be interested to have some feeling about what it means geometrically on the Hilbert space.

In Nielsen & Chuang it seems to mean that the different errors $$E_i$$ are associated with orthogonal subspace that preserve the orthogonality (two orthogonal vector of the code space will still be orthogonal after an error). But I don't understand why this is equivalent to Knill-Laflamme QEC condition.

We can try to geometrically interpret the Knill–Laflamme conditions on a code-space $$\mathcal C$$, as follows.$$\def\ket#1{\lvert#1\rangle}\def\bra#1{\langle#1\rvert}$$

### Images of the code-space under an error operation

First, consider any individual error operator $$E_j$$: this is a Kraus operator of some transformation of the system, and so is not necessarily even unitary.

For any input pure state $$\ket\psi \in C$$ and for an arbitrary operator $$E_j$$, the vector $$E_j \ket{\psi}$$ will represent some distorted image of the input state. You might wonder whether different states $$\ket\psi \in \mathcal C$$ could be affected in different ways: specifically, whether some vectors $$E_j \ket\psi$$ will have different norms for various states $$\ket\psi$$. The Knill–Laflamme condition indicates that this isn't possible: as $$P_{\mathcal C} E_{\!\!\:j}^\dagger E_{\!\!\:j}^{\phantom\dagger} \!P_{\mathcal C} = \alpha_{\!\!\:j,j} P_{\mathcal C}$$ for some scalar $$\alpha_{\!\!\:j,j}$$ (which we can show is a non-negative real), it follows that $$\lVert E_j \ket\psi \rVert^2 = \alpha_{\!\!\:j,j}$$ for all $$\ket\psi \in \mathcal C$$.

So: for any set of errors $$\{E_j\}_j$$ satisfying the Knill–Laflamme conditions, each error $$E_j$$ produces some faithful image of the original code-space $$\mathcal C$$i.e., proportional to a unitary transformation on $$\mathcal C$$, even if $$E_j$$ is not itself proportional to a unitary.

### Images of the code-space under different error operations

Next, consider how these images of the code-space compare for two different error operators $$E_j$$ and $$E_k$$, and under what conditions we can hope to recover a state which have been affected by one of the errors.

• In some cases — as with distinct single-qubit Pauli operators on a code with distance 3 or greater — the subspace $$E_{\!\!\:j}\!\: \mathcal C$$ and $$E_k \mathcal C$$ will be orthogonal to one another, and therefore perfectly distinguishable. In particular, we would then have $$E_j\ket\psi \perp E_k\ket\varphi$$ for any $$\ket\psi,\ket\varphi \in \mathcal C$$, so that $$P_{\mathcal C} E_{\!\!\:j}^\dagger E_{\!\!\:k}^{\phantom\dagger}\!\!\: P_{\mathcal C} = 0$$. If all of the error operators $$\{E_j\}_{j}$$ are 'orthogonal' in this sense, there would then be no problem to correct the errors: we could simply perform a measurement of which of the subspaces $$E_r \!\: \mathcal C$$ we were in, and then perform a unitary transformation which maps $$E_r \!\:\mathcal C \mapsto \mathcal C$$. This corresponds to the case where $$\alpha_{j,k} = 0$$ for any $$j \ne k$$.

• However, it is also possible (for instance, in a degenerate code as Patrick Fuentes indicates in his answer) to have errors $$E_j$$ and $$E_k$$ in which $$E_{\!\!\:j}\!\: \mathcal C$$ and $$E_k \mathcal C$$ are not orthogonal: the unit vectors in those subspaces may have non-zero overlap, or the two subspaces may even be the same. In this case, the only hope for us to be able to correct the error is that — to the extent that the effect of $$E_j$$ and $$E_k$$ on the code-space cannot be distinguished — the two images in a sense agree.

What I mean by this is: suppose that you had a state $$\ket\psi \in \mathcal C$$ which (unbeknownst to you) was affected by the error $$E_j$$, yielding the state $$\ket{\psi'} = E_j \ket{\psi}$$. Suppose that you then tried to determine whether it was affected instead by the error $$E_k$$, by measuring whether the state was in the space $$E_k \mathcal C$$. In general, this would disturb the state $$\ket{\psi'}$$. However, if $$\ket{\psi'}$$ collapsed to the state $$\ket{\psi''} = E_k \ket{\psi}$$, there would be no problem: you could simply correct the state as though $$E_k$$ had happened, and thereby recover $$\ket{\psi}$$.

This is what is guaranteed by the Knill–Laflamme conditions: that for any state $$\ket{\psi} \in \mathcal C$$, the projection of $$E_{\!\!\:j}\!\: \ket{\psi}$$ onto $$E_k \mathcal C$$ will be proportional to $$E_k \ket{\psi}$$. Furthermore, that the constant of proportionality $$\alpha_{j,k}$$ involved is the same for all $$\ket{\psi} \in \mathcal C$$.

Thus, the Knill–Laflamme conditions imply that, to the extent that we cannot perfectly distinguish the effects of $$E_j$$ and $$E_k$$ on the entire subspace $$\mathcal C$$, the effects of $$E_j$$ and $$E_k$$ on individual states in $$\mathcal C$$ are also indistinguishable, so that we cannot confuse one error $$E_j$$ for another error $$E_k$$ plus some transformation on the original encoded state.

### In summary

The Knill–Laflamme conditions on a set of error operators $$\{E_j\}_j$$ on a code-space $$\mathcal C$$ indicate that the effect of any one error $$E_j$$ affects the entire space a uniform way (rescaling it uniformly and transforming it unitarily otherwise); and that to the extent that the effects of two errors $$E_j$$ and $$E_k$$ cannot be operationally distinguished from one another, their effect on the code-space is the same as one another, so that you can measure which error occurred and then correct the state as though that error actually is the one that did occur.

• Thank you for your answer. I have a little question: What do you exactly mean by "|ψ⟩∈C could be affected differently". Could you define a transformation that would act "the same" on all state ? I guess you will tell me proportional to unitary but then why do you say it acts the same on all state in contrary to another transformation, I am a little confused. For the second part I understood your first point (very nice!) for the second I roughly see what you mean but I need more work on it atm – StarBucK Aug 29 '19 at 13:18
• Fair question: the wording is a little vague there. Basically I have in mind that the effect of the operator $E_j$ will be the same on the norms of those states: for instance, there won't be a vector $\lvert \psi \rangle \in \mathcal C$ for which $E_j \lvert \psi \rangle = \mathbf 0$, unless all states $\lvert \varphi \rangle \in \mathcal C$ have $E_j \lvert \varphi \rangle = \mathbf 0$. I will try to make my wording clearer there. – Niel de Beaudrap Aug 29 '19 at 13:29
• @Niel de Beaudrap I started writing the same intuitive explanation yesterday and wanted to finish it today but you beat me to it. You did a very good job (probably better than I would). What surprised me is that I came up with it on my own at some point and I have never seen it from any other source. Guess this explanation is not new after all. – oleg Aug 29 '19 at 16:06
• @oleg: When I first saw this picture, I came up with it on my own as well --- though I doubt that I was the first to do so. Some things lie just below the surface, and are available to anyone who can find the way to peel off the top layer. But while the idea doesn't leap straight out at me while skimming Knill and Laflamme's original article [ arxiv.org/abs/quant-ph/9604034 ], some of the commentary (e.g. the top of page 16) suggests that this view may have been available from the very beginning for someone who read it carefully. – Niel de Beaudrap Aug 29 '19 at 16:18
• @Niel de Beaudrap Huh, I actually have never read the original paper. Glancing at it now I see that it is rife with explanations. I really shouldn't be surprised. Thanks again! – oleg Aug 29 '19 at 20:11

Let me begin by reformulating the Knill-Laflamme Theorem, looking at it from a different angle might help in making the matter a little less abstract.

The Knill-Laflamme Theorem for the conditions of quantum error correction can be stated as follows:

Let $$C$$ be a quantum error correcting code defined as a subspace of the n-dimensional Hilbert space, $$\mathcal{H}_2^{\otimes n}$$, and let $$\mathcal{E} \subset \mathbb{C}^{2^n\times2^n}$$ be a set of errors. Then $$\mathcal{C}$$ can correct $$\mathcal{E}$$ if and only if $$\langle\psi_i|E_a^\dagger E_b|\psi_j\rangle = c_{ab}\delta_{ij} ,$$ where {$$|\psi_i\rangle$$} is a base of the subspace that defines the code $$\mathcal{C} \subset \mathcal{H}_2^{\otimes n}$$ and $$E_a$$, $$E_b$$ $$\in \mathcal{E}$$.

By itself, the above statement provides information about the degeneracy of the code. By computing all the possible outputs of parameter $$c_{ab}$$ (this can be done by randomly selecting a basis vector of $$C$$, $$|\psi_i\rangle$$, and setting $$i=j$$.), placing them in a matrix $$C_{ab}$$, and then computing its rank, we can determine if $$C$$ is degenerate or non-degenerate. If $$\mathrm{rank}(C_{ab}) < max$$, the quantum code is degenerate, which means different errors from an error set $$\mathcal{E}$$ map to the same syndrome and cause the same error effect on the codeword, thus, being reversible via the same recovery operation. If $$C_{ab}$$ is full rank, each error $$E_i$$ in the error set $$\mathcal{E}$$ maps to a unique error syndrome.

Placing the matter of degeneracy aside, the following corollary of the Theorem might help in understanding the meaning of the Theorem itself.

For any code $$C$$ defined as a subspace of $$\mathcal{H}_2^{\otimes n}$$, if $$C$$ is capable of correcting all the errors in a set $$\mathcal{E} \subset \mathcal{C}^{2^n\times2^n}$$, then $$C$$ will be able to correct all the errors within the linear span of $$\mathcal{E}$$.

Essentially what this corollary tells us is that if a quantum error correcting code can correct all the errors in the set $$\mathcal{E}$$, it will also be able to correct all the possible linear combinations of the elements within that set. If we now consider that the Pauli matrices define a basis for the $$\mathbb{C}^{2\times2}$$ space, then the $$n$$-fold Pauli group will form a base for the n-dimensional subspace $$(\mathbb{C}^{2\times2})^{\otimes n} = \mathbb{C}^{2^n\times2^n}$$. This last statement, means that all the matrices in $$\mathbb{C}^{2^n\times2^n}$$ can be expressed as linear combinations of the elements of the $$n$$-fold Pauli group, which by the above corollary gives us the groundbreaking condition that to design good quantum error correcting codes we must needs only consider errors that are elements of the $$n$$-fold Pauli group.

Hopefully this approach to the Theorem aids in understanding its utility and importance.