Steane code

In plain terms

Classical error correction has a gem called the Hamming code, in which seven bits carry four bits of information, arranged so that if any single bit flips, a few parity checks (does this group of bits contain an even number of ones?) announce which one. Quantum errors come in two flavours, as a bit flip turns a zero into a one, and a phase flip changes the sign between the two branches of a superposition, which no classical code can even see. Steane's insight was that one and the same Hamming code can police both flavours at once, provided its parity checks are compatible with each other in a precise sense.

They are, and the result is seven physical qubits protecting one logical qubit, the encoded qubit whose information is spread across all seven, against any single-qubit error. You measure six stabiliser checks, measurements designed to reveal whether an error has occurred without revealing the protected information itself, and the pattern of answers spells out which qubit went wrong and in which way.

The construction, a classical code and its own dual, used once for each flavour of error, is called CSS after Calderbank, Shor and Steane, and it's the template from which most practical quantum codes descend.

In CSD

The Steane code is the first genuine CSS instance of the corpus's stabiliser layer. The rows of the Hamming parity-check matrix give three bit-flip checks and three phase-flip checks, the compatibility condition CSS codes require is machine-checked, and the general stabiliser machinery then applies wholesale, so the code space has dimension exactly two by the general trace formula, which is one logical qubit.

Both logical states are exhibited concretely, as uniform superpositions over the Hamming code's row space and over its all-ones coset, and they're proved to be left unchanged by all sixty-four elements of the stabiliser group and to be orthonormal. The logical bit-flip and phase-flip operators act on them as a genuine encoded qubit. Single-qubit errors are proved to produce syndromes, patterns of check answers, that are nonzero and pairwise distinct, the distance-three property, which is what makes every single error identifiable.

The recovery side is proved too, in rows that came later. A recovery channel is built from the Knill-Laflamme conditions in encoder form and corrects every single-qubit Pauli error, and then every arbitrary operator on one of the seven qubits, since a recovery for a family corrects the whole span of that family. The code's failure probability with ideal recovery is at most twenty-one times the square of the physical error rate, which is what the concatenated threshold needs. The transversal Hadamard, phase and two-block controlled-not gates are proved to act as the corresponding encoded gates, each with a faulty-gadget theorem behind it, and the twin result puts the whole recovery on the programme's own state space with one channel independent of preparation and weights. What stays open is the fault-tolerant syndrome-extraction circuit and the extended-rectangle accounting.

Mathematically

Take H the 3-by-7 Hamming parity matrix whose columns are the binary expansions of 1 through 7. The rows satisfy H H^T = 0 over F2, so the six Pauli operators X^(h_i) and Z^(h_i) commute and generate a 64-element stabiliser group with trivial signs, and the stabiliser trace formula gives code dimension 2^7/2^6 = 2.

The logical zero is the uniform superposition over the row space C2 (eight strings), and the logical one over the coset C2 + 1111111, the all-ones string being a Hamming codeword outside the row space, so the supports are disjoint. Both are proved stabilised by the full group (steaneZero_stabilised for the logical zero) and orthonormal. X^(all-ones) swaps the two states, and Z^(all-ones) fixes the zero and negates the one, since the all-ones string has odd weight against itself and even against the rows. Single-error syndromes are the columns of H, nonzero and pairwise distinct, hence distance 3.

The name

Andrew Steane, an Oxford atomic physicist, found the seven-qubit code in 1996 within months of Shor's nine-qubit construction, and independently of the Calderbank-Shor paper whose framework it shares, which is why "CSS codes" carries all three names. Steane's version is smaller than Shor's and self-dual, which makes its logical gates unusually clean, as applying a Clifford gate to each of the seven qubits separately implements the same gate on the logical qubit.

Steane went on to become one of the architects of fault-tolerant quantum computation, and the seven-qubit code remains the standard teaching example and a building block of colour codes.

Related entries

• 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.
• 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.
• magic stateA magic state is the fuel of quantum advantage, a single special state that, consumed by otherwise classically trackable Clifford circuits, unlocks the one gate the Gottesman-Knill theorem can't simulate.
• Pauli matricesThree small matrices carry the entire two-level world, and their refusal to commute is the uncertainty principle in its smallest packaging.
• 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.
• 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.
• 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.
• threshold theoremThe threshold theorem says imperfect components suffice, as long as each one fails below a fixed rate you can make a quantum computation as reliable as you like by encoding it inside itself repeatedly, and the price is only a power of a logarithm.
• 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.