Shor code

In plain terms

Classical error correction works by redundancy and inspection, so you store three copies of a bit, look at them, and take the majority. Quantum information resists both halves of that recipe, as a qubit, the quantum unit of information, can't be copied, and measuring it disturbs the very state you're trying to protect, so for a while it looked as if error correction was simply impossible for quantum computers.

Shor's nine-qubit code, published in 1995, showed that it isn't. One qubit is spread across nine physical qubits in such a way that any error on any single one of the nine can be detected and undone without ever learning the protected information. The errors it handles are of two kinds, and their combinations. A flip swaps the two basic values of a qubit, much as a classical bit error turns a zero into a one, and a phase error has no classical counterpart, as a qubit can be in a blend of its two values, and a phase error changes the sign with which the two are combined, which alters the results of later measurements without touching either value on its own.

Detection works through checks that ask joint questions about groups of qubits, such as whether two of them agree, without asking what either value is. The pattern of check results, called the syndrome, points to the error without revealing the stored information, and a correction operation reverses it. The corpus builds all of this explicitly, the checks, the syndrome extraction, the corrections, and the theorems that the encoded state comes back intact for each kind of error.

One subtle feature survives the formalisation intact. Two different phase errors, on different qubits within the same group of three, can produce the same syndrome, and the same correction still works for both. This property, called degeneracy, has no classical analogue and is part of what makes quantum codes stranger than classical ones.

In CSD

CSD reconstructs quantum mechanics from an underlying deterministic description, and its formal corpus also carries a suite of standard quantum results reproduced inside the same formal frame. The error-correction results belong to that suite, and they're labelled as empirical breadth, quantum mechanics' own machinery, checked in the corpus so the programme's operational layer, the part that describes what laboratories actually do, is held to the same standard as the foundational claims. They work as a regression suite, a fixed set of results that must keep holding as the corpus grows.

The code is built by concatenation. A three-qubit code that fixes flips is layered inside a three-qubit code that fixes phase errors, and the nine-qubit code is the result, so the formal development follows the same layering and its structure mirrors the way the code is taught.

For a reader interested in formal methods, the point is the level at which the code exists. Encoders, syndromes and corrections are explicit maps with theorems about them, rather than an abstract framework for such codes cited from outside and assumed to apply.

The bit-flip half of the code is also read on the constraint surface, and every step of that reading is proved. The error isn't posited as a channel, as a volume- preserving flow on the three-qubit register together with a four-level environment, lifting a concrete joint unitary, produces the single-error channel as its environment marginal. The code space is a region of the surface, and the four error images of that region are pairwise disjoint, so the syndrome measurement is a partition of the surface into four regions, and the projective measurement that reads the syndrome is exactly the indicator of those regions. Recovery is one channel, which measures the syndrome and applies the correction it names. That single channel returns every code state, mixed or pure, from the mixed post-error state, and applied to the environment marginal of the flowed preparation it returns the register's density operator whenever the preparation lies in the code region. What the code doesn't do is also stated, as two flips at once are miscorrected, so the independent-noise channel is corrected only to first order.

Mathematically

The recovery theorems shor_corrects_X, shor_corrects_Z_degenerate and shor_corrects_XZ state that for every block position and every logical state, applying the error followed by syndrome-directed correction returns the encoded state. The Z case is proved through the degeneracy (correction at any position within the affected block restores the state), and the combined XZ case composes both recoveries.

The Pauli errors X, Z and XZ span every single-qubit error, so recovery from these three cases covers the single-qubit error set, and stabiliser fixing lemmas certify the code space, as the encoded states are fixed by the stabiliser checks.

For the three-qubit half on the surface, bitFlipFlow_traceRight_barycenter and registerFlow_traceRight_barycenter (Empirical/CSD/QEC/) produce the one-qubit bit- flip channel and the register's single-error channel as environment marginals of flows on the complex projective spaces of dimension three and thirty-one, errorRegion_disjoint and syndromeProj_fixes_errorRegion read the syndrome as a partition of the surface, recoveryChannel_apply_singleFlipChannel_apply (Empirical/QM/QEC/SyndromeRecovery.lean) is the Knill-Laflamme collapse for the recovery channel with Kraus operators E_k P_k, and registerFlow_recovery (Empirical/CSD/QEC/RegisterFlow.lean) composes them into error correction on the surface end to end.

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.
• Pauli matricesThree small matrices carry the entire two-level world, and their refusal to commute is the uncertainty principle in its smallest packaging.
• Stinespring dilationEvery noisy quantum process is a reversible process on a larger system with part of that system ignored, and in CSD the larger system is the constraint surface itself, so every channel the programme uses is the environment's marginal of a volume- preserving flow.
• 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.
• Gottesman-Knill theoremThe Gottesman-Knill theorem marks the boundary of quantum advantage, as circuits built from the Clifford gates can be simulated classically, because in the right picture they're nothing more than linear algebra on bits.
• Knill-Laflamme conditionsQuantum error correction has an exact test, as a set of errors is correctable if and only if the code can't tell those errors apart, and that condition is a piece of algebra you can check before building any 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.