Shor code

The first quantum error-correcting code that fixes everything, verified gate by gate: nine qubits, the Pauli errors that span every single-qubit error, built by concatenation and proved including its famous degeneracy.

proved in corpus · proved here, no imported axiomsLean shor_corrects_XZ

In plain terms

Here is the problem. Quantum information cannot be copied, and measuring it disturbs it -- so error correction, which classically works by redundancy and inspection, looks impossible. Shor's nine-qubit code was the 1995 proof that it is not: encode one qubit across nine, and any error on any single qubit -- flip, phase, or both -- can be detected and undone without ever learning the protected information.

The corpus verifies the code as built objects, not as prose: the stabiliser checks, the syndrome extraction, the correction operations, and the recovery theorems for each error type.

The subtle point survives formalisation intact: two different phase errors can produce the same syndrome and the same correction still works -- the degeneracy that makes quantum codes stranger than classical ones.

In CSD

The QEC suite is empirical breadth, labelled as such: quantum mechanics' own machinery reproduced inside the corpus's formal frame, part of the regression suite that keeps the programme's operational layer honest. The code is built by concatenation -- the phase-flip code layered over the bit-flip code -- so the module structure mirrors the pedagogy.

For the formal-methods reader the interest is the object level: encoders, syndromes and corrections are explicit maps with theorems, not a stabiliser formalism cited from outside.

Mathematically

shor_corrects_X, shor_corrects_Z_degenerate, shor_corrects_XZ: for every block position and every logical state, applying the error followed by syndrome-directed correction returns the encoded state -- with the Z case proved through the degeneracy (correction at any position within the affected block) and the combined XZ case composing both recoveries. Stabiliser fixing lemmas certify the code space.

Module
CsdLean4/Empirical/QM/QEC/ShorNine.lean
Related
shor algorithm, pauli matrices, quantum channel

Source links are pinned to a commit, so they do not drift. The anchors above are checked mechanically against the Lean tree on every build. The mathematics is not, and cannot be: that is a human responsibility and it rests with the author.

Part of Constraint-Surface Dynamics · Formalised in csd-lean4.

Privacy policy