The Knill–Laflamme Conditions
Exactly when a code can correct a set of errors.
Which sets of errors can a quantum code undo? Knill and Laflamme answered in one line: a code corrects exactly when the overlaps carry no information about the logical state. This lesson proves the theorem, reads it as "the environment learns nothing", and draws out its consequences for distance, erasures and degeneracy.
What you’ll learn
- State the Knill–Laflamme (KL) conditions and prove both sufficiency, by constructing the recovery, and necessity.
- Reformulate correctability as the complementary channel being constant on the code.
- Derive the relations between distance, correctable errors and correctable erasures.
- Recognize degenerate codes from the rank of the KL matrix, and check the conditions on small examples.
The theorem
Read the conditions in two halves. The factor says errors never make orthogonal codewords overlap, so no logical information is scrambled into indistinguishability. The fact that does not depend on says every codeword "looks the same" to the errors, so the error process carries no information about which logical state is present. Both are needed, and the second one is the genuinely quantum requirement.
Proof
Diagonalize the Hermitian matrix and pass to new error operators . They generate the same CP map (unitary freedom of Kraus operators) and satisfy
Polar decomposition: for each there is a unitary with
The projectors are mutually orthogonal, since for
Measure , completed by , and undo the rotation: plus any CPTP action on the complement. Because :
Let have Kraus operators with , and suppose acts on as . The composite has Kraus operators :
Two Kraus representations of the same CP map are related by an isometry, and has the single Kraus operator . Hence every is a multiple of :
Insert :
Distance, erasures and degeneracy
KL turns distance into correcting power. If and each act on at most qubits, then acts on at most . When it is detectable, so : a distance- code corrects arbitrary errors on any qubits. By linearity this covers every Kraus operator supported on qubits, not just Paulis.
Erasures are errors at known locations. If the set of erased qubits is known, all error operators act on only, and so does every . KL then only requires operators supported on to be detectable: a distance- code corrects any erasures, about twice as many as unlocated errors.
How many erased qubits, at known positions, can the Steane code always recover from?
Show the answer
2
Erasure correction needs only that operators supported on the erased set be detectable, which holds for every set of at most qubits. For unlocated errors the code handles only .
For the bit-flip code , which operator is not detectable?
Show the answer
C.
but , so is not a multiple of . A single acts as a logical operator of this code, which therefore has distance 1 against general errors.
Beyond exact correction
Exact KL can be too strict. Amplitude damping has the Kraus operator , and the four-qubit code , violates KL at order yet still achieves fidelity , using fewer qubits than the five that any code correcting arbitrary single-qubit errors needs (Leung, Nielsen, Chuang & Yamamoto 1997).
Key takeaways
- KL: a code corrects iff ; the matrix is (the transpose of) the environment's state, independent of the logical state.
- Sufficiency is constructive (diagonalize , measure the orthogonal images , apply ); necessity follows from the unitary freedom of Kraus representations.
- A distance- code corrects arbitrary errors on qubits and any erasures; correcting a set of errors implies correcting its linear span.
- Degenerate codes have a singular : distinct errors act identically on the code, a uniquely quantum feature exploited by codes such as Shor's and the surface code.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A code satisfies , except that while . What goes wrong?
- Nothing: KL only constrains the off-diagonal elements
- The probability of error depends on the logical state, so detecting it reveals logical information and the code cannot correct it
- Orthogonal codewords become non-orthogonal
- The recovery map cannot be trace-preserving
Show the answer
B. The probability of error depends on the logical state, so detecting it reveals logical information and the code cannot correct it
is the probability that error 1 occurs on . If it depends on , the syndrome is correlated with the logical state, so detecting the error partially measures the logical qubit and destroys superpositions.
A code has distance . Which statement is guaranteed?
- It corrects arbitrary errors on any 4 qubits
- It corrects arbitrary errors on any 2 qubits, and erasures of any 4 qubits
- It corrects arbitrary errors on any 5 qubits
- It corrects 2 erasures but no unlocated errors
Show the answer
B. It corrects arbitrary errors on any 2 qubits, and erasures of any 4 qubits
Unlocated errors: . Erasures: , since only operators supported on the known set need to be detectable.
In the sufficiency proof, what does diagonalizing achieve?
- It makes the error operators unitary
- It shows that must be the identity matrix
- It produces errors whose images are mutually orthogonal, undistorted copies of , so a projective measurement identifies and a unitary undoes it
- It removes the degenerate errors from the error set
Show the answer
C. It produces errors whose images are mutually orthogonal, undistorted copies of , so a projective measurement identifies and a unitary undoes it
says that each maps isometrically (up to a scale) onto its own subspace, and that these subspaces are orthogonal. Measuring the subspace and applying recovers the state.
Which formulation is equivalent to the KL conditions?
- The noise acts unitarily on the code space
- The complementary channel, the environment's view, outputs the same state for every code state
- Every error operator commutes with the code projector
- The code space is mapped into itself by every error
Show the answer
B. The complementary channel, the environment's view, outputs the same state for every code state
With a Stinespring dilation, the environment ends in for every code state iff KL holds. No information about the logical state reaches the environment, so all of it remains recoverable from the system.
Further reading
- E. Knill & R. Laflamme, "Theory of quantum error-correcting codes", Physical Review A 55, 900 (1997).
- C. H. Bennett, D. P. DiVincenzo, J. A. Smolin & W. K. Wootters, "Mixed-state entanglement and quantum error correction", Physical Review A 54, 3824 (1996).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, Theorem 10.1 and §10.3 (Cambridge, 2010).
- D. W. Leung, M. A. Nielsen, I. L. Chuang & Y. Yamamoto, "Approximate quantum error correction can lead to better codes", Physical Review A 56, 2567 (1997).
- C. Bény & O. Oreshkov, "General conditions for approximate quantum error correction and near-optimal recovery channels", Physical Review Letters 104, 120501 (2010).