Simple Algorithm
Quantum Computing · Rydberg State · 30 min

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 {Ea}\{E_a\} exactly when the overlaps ⟨iL|Ea†Eb|jL⟩\mel{i_L}{E_a^\dagger E_b}{j_L} 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 δij\delta_{ij} says errors never make orthogonal codewords overlap, so no logical information is scrambled into indistinguishability. The fact that cabc_{ab} does not depend on ii 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

DerivationSufficiency: constructing the recovery
  1. P Fk†Fl P=dkk δkl PP\,F_k^\dagger F_l\,P = d_{kk}\,\delta_{kl}\,P

    Diagonalize the Hermitian matrix c=udu†c = udu^\dagger and pass to new error operators Fk=∑auakEaF_k = \sum_au_{ak}E_a. They generate the same CP map (unitary freedom of Kraus operators) and satisfy

  2. FkP=dkk  UkPF_kP = \sqrt{d_{kk}}\;U_kP

    Polar decomposition: for each dkk>0d_{kk}>0 there is a unitary UkU_k with

  3. PkPl=Uk(PUk†UlP)Ul†=Uk (PFk†FlP) Ul†dkkdll=0P_kP_l = U_k\big(PU_k^\dagger U_lP\big)U_l^\dagger = \frac{U_k\,\big(PF_k^\dagger F_lP\big)\,U_l^\dagger}{\sqrt{d_{kk}d_{ll}}} = 0

    The projectors Pk:=UkPUk†=FkPFk†/dkkP_k := U_kPU_k^\dagger = F_kPF_k^\dagger/d_{kk} are mutually orthogonal, since for k≠lk\ne l

  4. R(E(ρ))=∑k,lUk†PkFl ρ Fl†PkUk=(∑ldll)ρ=(Tr⁡c) ρ\mathcal{R}\big(\mathcal{E}(\rho)\big) = \sum_{k,l}U_k^\dagger P_kF_l\,\rho\,F_l^\dagger P_kU_k = \Big(\sum_ld_{ll}\Big)\rho = (\Tr c)\,\rho

    Measure {Pk}\{P_k\}, completed by I−∑kPk\id-\sum_kP_k, and undo the rotation: R(σ)=∑kUk†PkσPkUk\mathcal{R}(\sigma) = \sum_kU_k^\dagger P_k\sigma P_kU_k plus any CPTP action on the complement. Because Uk†PkFlP=δkldll PU_k^\dagger P_kF_lP = \delta_{kl}\sqrt{d_{ll}}\,P:

DerivationNecessity
  1. ∑r,a(RrEaP) ρ (RrEaP)†=λ PρPfor all ρ\sum_{r,a}(R_rE_aP)\,\rho\,(R_rE_aP)^\dagger = \lambda\,P\rho P\qquad\text{for all }\rho

    Let R\mathcal{R} have Kraus operators RrR_r with ∑rRr†Rr=I\sum_rR_r^\dagger R_r = \id, and suppose R∘E\mathcal{R}\circ\mathcal{E} acts on CC as ρ↦λρ\rho\mapsto\lambda\rho. The composite has Kraus operators RrEaPR_rE_aP:

  2. RrEaP=μra PR_rE_aP = \mu_{ra}\,P

    Two Kraus representations of the same CP map are related by an isometry, and ρ↦λPρP\rho\mapsto\lambda P\rho P has the single Kraus operator λP\sqrt\lambda P. Hence every RrEaPR_rE_aP is a multiple of PP:

  3. PEa†EbP=∑rPEa†Rr†RrEbP=∑rμra∗μrb P=cabP,c=μ†μ≥0□PE_a^\dagger E_bP = \sum_rPE_a^\dagger R_r^\dagger R_rE_bP = \sum_r\mu_{ra}^*\mu_{rb}\,P = c_{ab}P,\qquad c = \mu^\dagger\mu\ge0\qquad\square

    Insert ∑rRr†Rr=I\sum_rR_r^\dagger R_r = \id:

Distance, erasures and degeneracy

KL turns distance into correcting power. If EaE_a and EbE_b each act on at most tt qubits, then Ea†EbE_a^\dagger E_b acts on at most 2t2t. When 2t≤d−12t\le d-1 it is detectable, so PEa†EbP=cabPPE_a^\dagger E_bP = c_{ab}P: a distance-dd code corrects arbitrary errors on any t=⌊(d−1)/2⌋t = \lfloor(d-1)/2\rfloor qubits. By linearity this covers every Kraus operator supported on tt qubits, not just Paulis.

Erasures are errors at known locations. If the set SS of erased qubits is known, all error operators act on SS only, and so does every Ea†EbE_a^\dagger E_b. KL then only requires operators supported on SS to be detectable: a distance-dd code corrects any d−1d-1 erasures, about twice as many as unlocated errors.

Predict before you look

How many erased qubits, at known positions, can the Steane code [[7,1,3]][[7,1,3]] 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 d−1=2d-1 = 2 qubits. For unlocated errors the code handles only ⌊(3−1)/2⌋=1\lfloor(3-1)/2\rfloor = 1.

Check your understanding

For the bit-flip code {∣000⟩,∣111⟩}\{\ket{000},\ket{111}\}, which operator is not detectable?

  1. X1X_1
  2. X1X2X_1X_2
  3. Z1Z_1
  4. Z1Z2Z_1Z_2
Show the answer

C. Z1Z_1

⟨000|Z1|000⟩=+1\mel{000}{Z_1}{000} = +1 but ⟨111|Z1|111⟩=−1\mel{111}{Z_1}{111} = -1, so PZ1PPZ_1P is not a multiple of PP. A single ZZ 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 γ ∣0⟩ ⁣⟨1∣\sqrt\gamma\,\ketbra{0}{1}, and the four-qubit code ∣0L⟩=(∣0000⟩+∣1111⟩)/2\ket{0_L} = (\ket{0000}+\ket{1111})/\sqrt2, ∣1L⟩=(∣0011⟩+∣1100⟩)/2\ket{1_L} = (\ket{0011}+\ket{1100})/\sqrt2 violates KL at order γ\gamma yet still achieves fidelity 1−O(γ2)1-\order{\gamma^2}, 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 {Ea}\{E_a\} iff PEa†EbP=cabPPE_a^\dagger E_bP = c_{ab}P; the matrix c≥0c\ge0 is (the transpose of) the environment's state, independent of the logical state.
  • Sufficiency is constructive (diagonalize cc, measure the orthogonal images FkCF_kC, apply Uk†U_k^\dagger); necessity follows from the unitary freedom of Kraus representations.
  • A distance-dd code corrects arbitrary errors on ⌊(d−1)/2⌋\lfloor(d-1)/2\rfloor qubits and any d−1d-1 erasures; correcting a set of errors implies correcting its linear span.
  • Degenerate codes have a singular cc: 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.

Question 1

A code satisfies ⟨iL|Ea†Eb|jL⟩=cabδij\mel{i_L}{E_a^\dagger E_b}{j_L} = c_{ab}\delta_{ij}, except that ⟨0L|E1†E1|0L⟩=0.6\mel{0_L}{E_1^\dagger E_1}{0_L} = 0.6 while ⟨1L|E1†E1|1L⟩=0.4\mel{1_L}{E_1^\dagger E_1}{1_L} = 0.4. What goes wrong?

  1. Nothing: KL only constrains the off-diagonal elements
  2. The probability of error E1E_1 depends on the logical state, so detecting it reveals logical information and the code cannot correct it
  3. Orthogonal codewords become non-orthogonal
  4. The recovery map cannot be trace-preserving
Show the answer

B. The probability of error E1E_1 depends on the logical state, so detecting it reveals logical information and the code cannot correct it

⟨iL|E1†E1|iL⟩\mel{i_L}{E_1^\dagger E_1}{i_L} is the probability that error 1 occurs on ∣iL⟩\ket{i_L}. If it depends on ii, the syndrome is correlated with the logical state, so detecting the error partially measures the logical qubit and destroys superpositions.

Question 2

A code has distance d=5d = 5. Which statement is guaranteed?

  1. It corrects arbitrary errors on any 4 qubits
  2. It corrects arbitrary errors on any 2 qubits, and erasures of any 4 qubits
  3. It corrects arbitrary errors on any 5 qubits
  4. 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: t=⌊(d−1)/2⌋=2t = \lfloor(d-1)/2\rfloor = 2. Erasures: d−1=4d-1 = 4, since only operators supported on the known set need to be detectable.

Question 3

In the sufficiency proof, what does diagonalizing cc achieve?

  1. It makes the error operators unitary
  2. It shows that cc must be the identity matrix
  3. It produces errors FkF_k whose images FkCF_kC are mutually orthogonal, undistorted copies of CC, so a projective measurement identifies kk and a unitary undoes it
  4. It removes the degenerate errors from the error set
Show the answer

C. It produces errors FkF_k whose images FkCF_kC are mutually orthogonal, undistorted copies of CC, so a projective measurement identifies kk and a unitary undoes it

PFk†FlP=dkkδklPPF_k^\dagger F_lP = d_{kk}\delta_{kl}P says that each FkF_k maps CC isometrically (up to a scale) onto its own subspace, and that these subspaces are orthogonal. Measuring the subspace and applying Uk†U_k^\dagger recovers the state.

Question 4

Which formulation is equivalent to the KL conditions?

  1. The noise acts unitarily on the code space
  2. The complementary channel, the environment's view, outputs the same state for every code state
  3. Every error operator commutes with the code projector PP
  4. 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 Ec(ρ)=cT\mathcal{E}^c(\rho) = c^T 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).