Knill-Laflamme conditions

In plain terms

A classical computer can check its memory by reading it, and quantum memory doesn't allow that, as reading a quantum state destroys the superposition you were trying to protect. So the first question about any quantum code isn't how to repair it but whether repair is possible at all, given the kinds of damage you expect.

Knill and Laflamme answered that with a condition on the code alone. Write down the set of errors you want to survive, a bit flip on the third qubit, a phase flip on the fifth, and so on, then ask what happens to the overlaps between encoded states when an error hits. Overlap is the quantity that decides whether two states can be told apart by any measurement, so if every error changes all the overlaps in the same way, by a factor that depends on the pair of errors and not on which encoded state you started from, then no measurement on the damaged state reveals anything about the protected information.

That's exactly the situation you want. The damage carries no trace of what was encoded, so the damage can be diagnosed and undone without disturbing the data, and one repair operation works for every error in the set at once. The condition is necessary as well as sufficient, so a code that fails it has no repair, however clever you are.

In CSD

The corpus proves the equivalence in both directions and then builds the repair, so the error-correction layer rests on a theorem rather than on a recipe. From the condition it constructs the recovery channel explicitly, by diagonalising the matrix of overlap factors, recombining the errors into a family whose images of the code space are mutually orthogonal, and reading the repair off those images. In the other direction, any channel that corrects the errors up to scalars is shown to force the condition, which is what makes it a test and not a sufficient condition dressed up as one.

One corollary carries most of the weight downstream. The correction property is linear in each error slot and a channel is linear, so a recovery that handles a family handles every combination of that family as well. Correcting the four basic single-qubit errors therefore corrects every possible single-qubit fault, including ones no one listed, which is how the Steane code's recovery covers arbitrary damage on one of its seven qubits. The encoder form of the condition, stated about the map that builds encoded states rather than about the projector onto them, is what lets the same argument run over several blocks at once in the fault-tolerance rows.

Mathematically

A code is an orthogonal projector P and a family of error operators E i is correctable exactly when P (E i)-dagger (E j) P = c i j times P for some matrix c (knillLaflamme_iff). Forward: c is Hermitian, so the spectral theorem gives c = U D U-dagger, and the canonical errors F k = sum over i of U i k times E i satisfy P (F k)-dagger (F l) P = d k times delta k l times P with d k nonnegative. The Kraus operators R k = d k^(-1/2) P (F k)-dagger have orthogonal ranges summing to a projector Q, and 1 - Q completes the channel, giving R (E i rho (E j)-dagger) = c j i times rho on code states. Converse: each R k E i P sends every code vector to a multiple of itself, via the sandwiched identity sum over k of |<u, R k E i v>|^2 = lam times |<u, v>|^2, hence is a scalar on the code, and trace preservation reassembles the condition.

Degenerate codes are included, as c need not be invertible and errors with d k = 0 act as zero on the code. The recovery is constructed, not shown unique. recovery_apply_lin_comb is the discretisation step: the correction property is bilinear in the two error slots, so a recovery for a family corrects the whole span of that family, up to the scalar the coefficients supply.

The name

Emanuel Knill and Raymond Laflamme published the conditions in 1997 while at Los Alamos, and an equivalent criterion appeared at the same time in work of Bennett, DiVincenzo, Smolin and Wootters. Laflamme had been Stephen Hawking's doctoral student and is remembered for persuading Hawking to change his mind about the arrow of time, before he turned to quantum information and helped build the first small quantum processors.

The conditions arrived a year after the first codes, which is the usual order of events, as Shor and Steane built working examples and the general criterion followed and explained why they worked.

Related entries

• Steane codeSeven qubits protect one, as the Steane code was the first to correct any single- qubit error by using the same classical Hamming code twice, once for bit flips and once for phase flips.
• Shor codeShor's nine-qubit code was the first proof that quantum information can be protected against any error on any single qubit without ever being read, and the corpus verifies that protection as explicit constructed operations, including the subtle case where two different errors share one repair.
• stabiliser codeA stabiliser code describes a quantum code by the measurements that leave it alone, which replaces a list of encoded states by a handful of parity checks and turns error correction into linear algebra over the two-element field.
• Quantum channelThe most general thing that can happen to a quantum state is captured in CSD as a concrete structure, a family of operators with one completeness law, and every certificate of its physicality is proved rather than assumed.
• transversal gateA transversal gate computes on encoded information by acting on each physical qubit separately, so a fault in one qubit stays in one qubit and the code keeps its protection while the computation runs.