25

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.

Marco Fellous-Asiani
  • 2,220
  • 2
  • 15
  • 42

4 Answers4

20

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 \mathcal{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.

Jess Riedel
  • 103
  • 5
Niel de Beaudrap
  • 12,522
  • 1
  • 33
  • 73
6

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.

Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
Patrick Fuentes
  • 318
  • 1
  • 4
2

$ \def\dg{^\dagger} \def\0{\bar0} \def\1{\bar1} \def\vk{\varphi_k} \def\vl{\varphi_l} \def\vm{\varphi_m} \def\ket#1{\left\lvert#1\right\rangle} \def\bra#1{\left\langle#1\right\rvert} \def\braket#1#2{\left\langle#1\middle\vert#2\right\rangle} \def\ketbra#1#2{\left\lvert#1\middle\rangle\!\middle\langle#2\right\rvert} $

Resource

Section 3 in this lecture by Daniel Gottesman explains the Knill-Laflamme criterion with the 9-qubit Shor code as an example.


Breakdown of the Knill-Laflamme criteria

Simplification

$P_C$ is the projector onto the coding subspace $C$. If we have a code that protects 1-qubit information, we will have two states in our coding subspace representing logical zero $\ket\0$ and logical one $\ket\1$. As an example, in 3-qubit bit-flip code, $\ket\0 = \ket{000}$ and $\ket\1 = \ket{111}$. In such case, $P_C = \ketbra\0\0 + \ketbra\1\1$. Generally, $$P_C = \sum_k\ketbra\vk\vk$$ where, $\ket\vk \in \text{basis}(C)$. So, an alternative way to represent the criteria:

\begin{align} \sum_{kl} \ketbra\vk\vk E_i\dg E_j \ketbra\vl\vl &= \alpha_{ij} \sum_m \ketbra\vm\vm \\ \Rightarrow \bra\vk\left( \sum_{kl}\ketbra\vk\vk E_i\dg E_j \ketbra\vl\vl \right)\ket\vl &= \alpha_{ij}\bra\vk\left( \sum_m\ketbra\vm\vm \right)\ket\vl \\ \Rightarrow\bra\vk E_i\dg E_j\ket\vl &= \alpha_{ij} \braket\vk\vl = \alpha_{ij} \delta_{kl} \end{align}

Preserve orthogonality between the transformed states

If we encounter an error, we should always be able to discern the transformed states. i.e. $E_i\ket\0$ should always be different from $E_i\ket\1$. Not only that, but different errors should also map the bases orthogonally: $\left(E_i\ket\0\right)\dg E_j\ket\1 = \bra\0E_i\dg E_j\ket\1 = 0$. Otherwise, we won't be able to discern which error took place.

Different errors map to different subspaces

If any two different errors map coding subspace to different error subspaces (sufficient but not necessary), then the coding scheme fulfils the criteria: $\bra\vk E_i\dg E_j \ket\vk = 0 = \alpha_{ij}$. In such cases, we can easily detect which error took place.

But it is not necessary that different correctable errors should always map to different subspaces. This phenomenon is explained later.

Linear combination of correctable errors

If a code is able to correct a set of errors $\{E_i\}$, it should also be able to correct any linear combination of that error. For example, 3-qubit bit-flip code can correct errors with Kraus operators: $\left\{\sqrt{(1-p)^3}I, \sqrt{p(1-p)^2}X_1, \sqrt{p(1-p)^2}X_2, \sqrt{p(1-p)^2}X_3 \right\}$, where $p$ is the probability of single qubit bit-flip error. Any code that is able to correct $\{I, X_1, X_2, X_3\}$ will also be able to correct the above-mentioned set of operators since they are just scaled versions of each other.

Invariance of $\alpha_{ij}$ on basis

The linearity of correctable errors also shows why the $\alpha_{ij}$ is needed in the Knill-Laflamme criteria instead of just $\delta_{ij}$. For example, with $E_1 = \sqrt{p(1-p)^2}X_1$ we see that $\bra\0 E_1\dg E_1 \ket\0 = \bra\0 E_1\dg E_1 \ket\0 = p(1-p)^2 = \alpha_{11}$. Notice how the value of $\alpha_{ij}$ is only dependent on $i$ and $j$, but not the basis: $\bra\vk E_i\dg E_j\ket\vk = \alpha_{ij}$. Recall the fact that unitary operations preserve inner product. Here, the inner product of $E_i\ket\vk$ and $E_j\ket\vk$, $\bra\vk E_i\dg E_j \ket\vk$ remains constant whatever the $\ket\vk$ is. That means we can choose a different set of bases for the error, which might map errors to orthogonal subspaces.

A good example of this is $Z_1$ and $Z_2$ errors in 9-qubit Shor code. Both are correctable by the Shor code. Interestingly, $\bra\vk Z_1\dg Z_2 \ket\vk = 1$, meaning they are not orthogonal errors. But if we took a different basis $B_1 = \frac{Z_1+Z_2}{2}$ and $B_2 = \frac{Z_1 - Z_2}{2}$, we see that, $\bra\vk B_1\dg B_2 \ket\vk = \bra\vk (Z_1^2 - Z_2^2) \ket\vk = \bra\vk (I-I) \ket\vk = 0$, which are orthogonal. Both of these cases are handled well by the Knill-Laflamme criteria.

Hermitian operator $[\alpha_{ij}]$

The fact that $[\alpha_{ij}]$ is a Hermitian matrix can easily be shown by swapping indices $i$ and $j$ in the criteria equation: $\bra\vk E_i\dg E_j \ket\vk = \alpha_{ij} = \left(\bra\vk E_j\dg E_i \ket\vk\right)\dg = \left(\alpha_{ji}\right)\dg$.

One might falsely think different errors need to be mapped to different subspaces for them to be corrected, i.e. $\alpha_{ij} = 0$ is always true if $i \neq j$. Not necessarily. For example, 3-qubit bit-flip code can correct both $X_1$ error and $X_1 Z_2 Z_3$ error. Both of the errors map $\ket\0 = \ket{000}$ to $\ket{100}$ and $\ket\1 = \ket{111}$ to $\ket{011}$. So, which error has occurred is hardly of importance. What matters is the fact that both of them can be corrected by applying the $X_1$ operation. This is possible because both errors have identical effect on the coding subspace. This is reflected in the value of $\alpha_{ij}$: $\bra\vk E_i\dg E_j \ket\vk = \bra\vk X_1\dg X_1 Z_2 Z_3 \ket\vk = 1 = \alpha_{ij}$.

Shawon
  • 71
  • 3
1

To add a visual aid to the great accepted answer I drew an image after reading the KL paper, I hope this helps.

enter image description here

At the top we have the green box showing the codespace $\mathcal{C}$ for a code that satisfies the KL conditions for $\{E_a\}$ error operators (red arrows). We can map each $|i_L\rangle$ logical basis state to the "error-expanded subspaces" $\mathcal{V}^i$ (red disks) that are spanned by the $E_a|i_L\rangle$ (red vectors in the red disks).

The $\langle i_L| E_b^\dagger E_a |i_L\rangle = \langle j_L| E_b^\dagger E_a |j_L\rangle$ statement means that the states that the errors map the states to are not necessarily orthogonal - but the key thing is that we have the same "angle" between the mapped vectors (as seen in the figure, the subspace disks are clones of each other), and thus that these error-expanded subspaces are isomorphic. The KL paper has a nice example where these corrupted states overlap for the same logical state. This just means that if we have, say, $M$ number of error operators that are correctable, then the dimension is at most $M$ of the error expanded subspaces, but it might be less than $M$. Also, the norm of the basis vectors might not be preserved under these error operations, they can shrink (I don't think they can grow under quantum channels). In the picture I have two dimensional error-expanded subspaces, with $|v_0^i\rangle, |v_1^i\rangle$ spanning each.

The orthogonality condition $\langle i_L| E_b^\dagger E_b |j_L\rangle = 0$ for $i\neq j$ is displayed in the image by no overlap between the subspaces.

It is interesting now to see how this picture leads to recoverability, so I'll provide the sketch of the KL-proof for these conditions being sufficient and necessary:

  • for each of the $\mathcal{V}^i$ we can find an orthonormal basis $|v_r^i\rangle$ (purple ones) - these are mutually orthogonal, across both indices
  • due to this orthogonality we can create a unitary recovery operator for each basis vector that maps them back to the original codeword, $V_r | v_r^i \rangle = |i_L \rangle$ - these are the green arrows on the cartoon with $V_0$ and $V_1$ mapping back from the corresponding error basis vectors to the codewords.
  • We can think about each $V_r$ as mapping to a copy of our codespace, in fact logical operators that map between $|i_L \rangle \rightarrow |j_L\rangle$ are going to map between $|v^i_r\rangle \rightarrow |v^j_r\rangle$. We can call these "copies" cosets (not displayed on the cartoon to avoid clutter, but you can see that the upward or leftward pointing purple vectors are isomorphic to the codespace).
  • at this point we're done, we just need to measure which orthogonal subspace the state is at i.e. are we in one of the cosets or in the remaining part of the Hilbert space (which means the codespace $\mathcal{C}$ and maybe some other parts) and then apply conditionally $V_r$.
Balint Pato
  • 1,191
  • 6
  • 16