concatenated code

In plain terms

One round of error correction improves matters but doesn't make them arbitrarily good, as a code that survives a single error still fails when two errors land in the same block. If the physical failure rate is small then two errors in one block is a much rarer event than one, which is exactly the improvement a code delivers, and the natural thing is to do it again.

Concatenation does that. Take the seven-qubit code, then replace each of its seven qubits by another seven-qubit block, giving forty-nine physical qubits protecting one logical qubit at level two. A level-two block fails only when two of its seven level-one blocks fail, and each of those fails only when two of its seven physical qubits fail, so the failure probability at each level is about a constant times the square of the level below. Squaring repeatedly is very fast: below the rate where the squaring starts winning, a few levels take a failure probability from one in a hundred to numbers with a great many zeros.

The cost is that qubit counts multiply by seven per level, which is why concatenation is the theoretical backbone of fault tolerance rather than the practical choice, as surface codes achieve a similar effect with a friendlier layout.

In CSD

The corpus builds concatenation as a recursion on pattern types and proves the bound by induction, rather than asserting the usual squaring rule. A level-k fault pattern is a tree of patterns, a level-k block is bad when at least two of its n children are bad, and the measure is the product measure of independent physical faults, so the inductive step is a two-or-more bound on a product measure.

The outcome is the concatenated failure bound, a constant times the physical rate raised to two to the power of the level, divided by that constant. Below one over the constant the bound tends to zero, which is the code-capacity threshold, and the Steane instance supplies the constant twenty-one by counting the weight-two error patterns the code cannot correct. The circuit-level threshold theorem then adds a union bound over the gadgets of a whole circuit on top of this recursion, so the two results are the same induction used at two scales. What stays open is the recovery channel at level k as an operator statement, which needs a tensor layer over blocks, and it's a numbered row rather than an omission.

Mathematically

ConcatPat n k is the level-k pattern type, Bool at level zero and Fin n indexed patterns above, with card_concatPat giving 2^(n^k); concatMeasure is the product measure of Bernoulli p over its coordinates. isBad n is the recursion, true at level zero on a faulty qubit and at level k + 1 when at least two children are bad, and concatMeasure_concatBad_le is the induction: the measure of concatBad n k is at most (c p)^(2^k) / c, with the inductive step supplied by measure_pi_two_or_more_le, a bound on the probability that two or more of n independent events occur.

For the Steane code steane_codeCapacity_failure_le gives c = 21 by counting the twenty-one weight-two patterns on seven qubits, and steane_threshold is the resulting convergence for p < 1/21. The level-k recovery channel is BACKLOG row 86 and is not claimed; the discretisation step that makes one-qubit arbitrary errors correctable at level one is proved (steane_recovery_arbitrary).

The name

Concatenation as a route to arbitrary accuracy is due to Emanuel Knill and Raymond Laflamme, who introduced concatenated codes in 1996, and it became the engine of the first threshold proofs. The idea is older than quantum computing, as classical coding theory had long used codes built from codes, and Forney's concatenated codes of the mid-1960s are the ancestor.

Modern architectures mostly concatenate only shallowly, or not at all, and topological codes have taken over the role, although every threshold estimate still reports the number concatenation made meaningful.

Related entries

• 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.
• 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.
• 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.
• 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.