Make your paper interactiveCreate

Text from the interactive explanation

The Road From Classical to Quantum Codes: A Hashing Bound Approaching Design Procedure

Zunaira Babar, Panagiotis Botsinis, Dimitrios Alanis, Soon Xin Ng, Lajos Hanzo

Original paper

Quantum error correction · Babar et al. 2015

Qubits are fragile. Information theory sets a benchmark for how much noise a quantum error-correcting code can survive: the hashing bound . This paper is a recipe for codes that come close. In computer simulations, its design kept working with noise only 0.4 dB (about 9 %) below that limit.

Two decoders pass hints back and forth: the amber spark is their conversation. Turn up the noise and watch the tunnel between the glowing curves narrow, then close.

Tunnel open: the decoders agree after 15 rounds.

Across: how much the outer decoder knows about which errors happened. Up: how much the inner decoder knows. The top-right corner means every error has been identified. Qubits at the sides flash red, blue or violet when hit by X, Z or Y errors. Ticks: 0.31 is where an earlier design’s error rate plunges (≈0.9 dB from the limit); 0.345 is this paper’s design (0.4 dB).

Qubits break in two ways

A classical bit is either 0 or 1. A qubit can be a blend of both. Picture it as an arrow inside a sphere: straight up means 0, straight down means 1, and every other direction is a particular blend.

The arrow’s angle around the equator is the qubit’s phase, a hidden ingredient with no classical counterpart. Noise can damage either part. A bit flip (X) turns the arrow upside down. A phase flip (Z) swings it half a turn around the vertical axis. A Y error does both at once.

The paper models the channel as depolarizing : each qubit independently suffers an X, a Z or a Y, each with probability p/3, and passes untouched otherwise. That one number, p, is the noise level used everywhere on this page.

Noise lab

The stream is running. Press Send 1,000 qubits to tally a big batch.

What about gentle, continuous noise? Real disturbances are tiny random nudges, not neat flips. But when a code measures its parity checks, that measurement forces the error itself to “decide”: the continuum of possible errors collapses to a discrete set, so either nothing happened or a full X, Z or Y did. A code that fixes those three discrete errors therefore handles continuous noise too.

Copying is forbidden; looking destroys

Classical codes fight noise with redundancy. The simplest one sends every bit three times and takes a majority vote.

Qubits rule out every step of that trick:

No device can copy an unknown qubit: this is the no-cloning theorem. The “send it three times” step has no quantum version.

A qubit can be nudged by any small angle, not just flipped. There are infinitely many possible errors to undo.

Measuring a qubit collapses its blend into a plain 0 or 1, wiping out the very information you wanted to protect.

The quantum way out is to entangle instead of copy . A qubit α|0⟩ + β|1⟩ is spread over three qubits as α|000⟩ + β|111⟩. That is not three copies. It is one shared state in which the three qubits always agree, whatever α and β are.

Then, instead of reading the qubits, we measure only parity checks : “do qubits 1 and 2 agree?” (written ZZI) and “do qubits 1 and 3 agree?” (ZIZ). Each check answers +1 (agree) or −1 (disagree). Together the answers form the syndrome . It points at the damaged qubit, yet reveals nothing about α or β. Try it.

Parity detective

Encoded as α|000⟩ + β|111⟩. Checks: ZZI, ZIZ. Click a qubit to flip it yourself, or let noise strike in secret.

Syndrome (+1, +1): both checks agree, so no error is detected.

Which qubit needs repair?

Make some damage first, then use the two lamps to decide which qubit to repair.

The protected state

Now press Two flips . The syndrome points at the one qubit that was not hit, the “repair” completes the damage, and α and β swap places: a logical error that no check can see. Stronger codes spread each qubit over many more. Shor’s 1995 code used 9 qubits per message qubit (rate 1/9) to catch any single X, Y or Z error. The code in this paper has the same rate, 1/9, but organises its qubits as long streams decoded by two cooperating decoders.

The parity checks are called stabilizers : measurements that leave the protected state untouched, reading +1, unless an error has disturbed it. Any error pattern can be written as a string of Pauli operators, and each Pauli fits into two classical bits. In the paper’s convention I → (0,0), X → (0,1), Y → (1,1) and Z → (1,0).

This mapping lets quantum codes be designed and decoded with classical binary algebra. It is one of the bridges the paper uses to carry classical coding ideas, such as turbo codes and EXIT charts, into the quantum world.

Different errors can have exactly the same effect on an encoded state. In the paper’s example, for the state |00⟩ + |11⟩ the errors IZ and ZI produce the same corrupted state. A quantum decoder therefore does best by finding the most likely family of equivalent errors, not one specific error.

Degeneracy is also why the true quantum capacity can exceed the hashing bound in principle, a point that returns in the next chapter.

The speed limit

Every code makes a trade. Its rate R is the number of message qubits it carries per transmitted qubit. Rate 1/9 means nine qubits are sent to protect one. A lower rate buys more protection.

For the depolarizing channel, information theory gives a benchmark that links rate and noise, the hashing bound : CQ(p) = 1 − H2(p) − p·log23, where H2 is the binary entropy, a measure of uncertainty. Pick a rate R, find the noise at which the bound falls to R, and you have the noise limit p*: the most noise a code of that rate can be expected to handle.

Strictly, the hashing bound is a lower bound on what is achievable, because degeneracy can push the true capacity higher. But as the paper notes, no code known at the time beat it at practical lengths, so it serves as the benchmark.

Codes can also get help. In entanglement-assisted communication, sender and receiver share entangled qubit pairs in advance, and the receiver’s halves are assumed to arrive without noise. If E such pairs are used per transmitted qubit, the bound becomes 1 − H2(p) − p·log23 + E.

Pick an answer to see what the hashing bound says.

Hashing-bound explorer

Reading decibels. Engineers measure the gap to the limit as 10·log10(p*/p) decibels. The paper’s code works up to p = 0.345 against a limit of 0.3779, so 10·log10(0.3779/0.345) ≈ 0.4 dB. In plain terms it tolerates about 91 % of the limiting noise: about 9 % below the limit.

Two decoders in conversation

The paper’s code is built like a classical turbo code: two simpler codes chained together, with a shuffle in between.

At the receiver, the parity checks give a syndrome. Two decoders then estimate the error pattern , meaning which qubits got X, Z or Y, rather than the message itself. Once the errors are known they can be undone without ever reading the qubits.

The decoders take turns. Each combines its own part of the evidence with the other’s latest hints, and passes back only extrinsic information : what it newly worked out, not what it was just told. Earlier work by Wilde and colleagues found this was key for quantum turbo codes. The shuffle sits between them so that errors clustered in one code look scattered to the other, which keeps their hints independent.

Step through the conversation

Round 0: neither decoder knows anything yet about which errors happened.

In the small chart the exchange becomes a staircase: each vertical step is the inner decoder’s turn, each horizontal step the outer decoder’s. This picture is the EXIT chart (EXtrinsic Information Transfer), the tool the whole paper is built on. Percentages are the information each decoder has about the error pattern; the small squares are a cartoon of the same thing, filling in with each qubit’s actual error (grey: none, red X, blue Z, violet Y) as certainty grows. Illustrative model

For the conversation to keep improving, the inner code must be recursive , meaning each output depends on its own earlier outputs, like a feedback loop. It must also be non-catastrophic , meaning a few errors cannot snowball into endless ones.

The paper recalls that quantum convolutional codes without entanglement cannot be both at once, while entanglement-assisted ones can. That is why the inner code, named PTO1REA, consumes pre-shared entangled pairs: 2/3 of a pair per qubit for the inner code, giving the whole rate-1/9 system an entanglement consumption of 6/9.

When the tunnel closes

Now the full EXIT chart. The inner decoder’s curve depends on the noise: the noisier the channel, the less it can deduce from the syndrome, so its curve sinks. The outer decoder never sees the channel, so its curve does not move.

While the cyan curve stays above the coral one there is an open tunnel , and the staircase can climb all the way to the top-right corner, where the error pattern is fully identified. Once the curves touch, the staircase jams at the pinch, however many more rounds you run.

Pick a guess, then watch the noise sweep upward on the chart below.

Squeeze the tunnel

Tunnel open.

Amber shading is the open tunnel; red shows where the curves have crossed. The narrowest point of this design sits low on the chart, where both decoders still know little.

Illustrative model calibrated to Fig. 22

A wide tunnel sounds safe, but it is wasted margin : with a better-matched partner the same inner code could survive more noise, or carry more message per qubit. A closed tunnel means failure. The best design sits in between, and the paper states the rule plainly:

Through the paper’s quantum-to-classical mapping (each Pauli error becomes two bits), a quantum code of rate R behaves like a classical code of rate (1 + R)/2 (Eq. 39). For a rate-1/3 outer code that is 2/3.

Classical EXIT-chart theory adds an accounting rule: the area under an outer decoder’s (inverted) curve tracks its rate, and an open tunnel needs the inner curve’s area to exceed it. Our illustrative model builds that rule in. Every rate-1/3 mixture has area exactly 2/3, and the inner curve’s area falls to 2/3 precisely at the hashing limit, p = 0.3779. So no rate-1/3 outer code, however clever, can open the tunnel there. A perfectly shaped one could only creep closer.

Mix codes to fit the tunnel

Here is the paper’s central idea. Instead of searching through countless codes for one whose curve happens to hug the inner curve, build the outer code as a mixture : split the message into fractions and protect each fraction with a different small code.

This is a Quantum IRregular Convolutional Code, or QIRCC . The paper uses ten ingredient codes: five strong ones (memory 3, sharper curves) and five weak ones (memory 1, gentler curves), each at rates 1/4, 1/3, 1/2, 2/3 and 3/4. The mixture’s curve is the weighted average of the ingredients’ curves, so choosing the fractions reshapes the coral curve. Two rules apply: the fractions add up to 100 %, and the overall rate stays at 1/3. The desk enforces both by rebalancing the other sliders as you move one.

Your goal: keep the tunnel open at the highest noise you can. The readout searches for the highest p at which your mix still leaves a gap.

Fractions add to 100 % · overall rate 1/3

Best so far: none yet

How the paper finds the fractions. It measures the squared gap between the two curves at many points and repeatedly nudges the fractions downhill (steepest descent). After every nudge it pulls them back onto the two rules and insists the gap stays positive, because the tunnel must stay open. It does this at the highest noise for which a solution still exists. Find best match animates that search in our model, raising the noise step by step until no mixture fits.

The paper’s optimiser ended up using only two of the ten ingredients: 16.8 % strong rate-3/4 plus 83.2 % weak rate-1/4 . That mix keeps the tunnel marginally open up to p = 0.345 , about 0.4 dB from the hashing limit of 0.3779. No single rate-1/3 ingredient comes close.

Illustrative model

The inner curve and the paper’s mix are smooth fits to values read from Fig. 22. The other eight ingredient curves are synthetic stand-ins for Fig. 21, built with the right rates so that the model reproduces the paper’s reported threshold. Numbers from the desk are illustrations, not new results.

What the simulations showed

An EXIT chart is a prediction that assumes extremely long qubit streams. To test it, the authors ran Monte Carlo computer simulations of the complete code: send many frames of qubits through a simulated depolarizing channel, decode them, and count the frames with any error left over. That count is the word error rate (WER).

At p = 0.320 …

With a 3,000-qubit interleaver, extra decoding rounds help only below the threshold. Under p ≈ 0.345 the error rate falls with every round; above it, more rounds change nothing, just as the EXIT chart predicts (Fig. 23). The gains also shrink with each extra round.

The comparison (Fig. 24) is against two earlier rate-1/9 designs. Design A (PTO1REA–PTO1R, from Wilde and colleagues) has its turbo cliff, the steep plunge in error rate, around p ≈ 0.31, within 0.9 dB of the limit. The new design reaches a WER of 10⁻³ at p = 0.322 instead of 0.29, about 0.5 dB better . Design B , a quantum turbo code the authors had found earlier by exhaustive search, has a similar threshold but a much higher error floor, the level where the curve flattens at low noise. Design A may have a lower error floor than the new one, but the new design wins in the turbo-cliff region.

Back to the opening question

How close can a real code get to the limit? For this design, in simulation, about 0.4 dB : it keeps working with noise about 9 % below the hashing limit for its rate and entanglement budget.

The recipe boils down to the authors’ three design guidelines:

From the target rate and the entanglement budget, compute the noise limit p* with the hashing bound. For this code: rate 1/9 with 6/9 entanglement gives 0.3779.

Choose a recursive, non-catastrophic inner code (which takes entanglement assistance) with the largest area under its EXIT curve at p*.

Mix QIRCC subcodes until the outer curve matches the inner one: a narrow but still open tunnel at the highest possible noise.

Every gain costs something. The paper’s stylised trade-off diagram (Fig. 4) lists the competing demands of quantum code design:

Longer codes lower the error rate but add delay. Cleverer codes add complexity. Lower rates and more entanglement buy robustness at the price of throughput and resources.

What this brings closer. A QIRCC can be re-tuned to match any given inner code using EXIT charts, with no exhaustive search through codes, and the resulting design operated within about 0.4 dB of the limit in simulation. That matters because quantum computers and quantum communication links, such as secure key distribution, both depend on keeping qubits intact long enough to be useful.

There is a pleasing symmetry here. Decoherence happens when qubits become entangled with their surroundings, and quantum codes counter it with deliberate entanglement among qubits, here even with pre-shared entangled pairs. As John Preskill put it, quoted in the paper, we are “fighting entanglement with entanglement”.

What kind of evidence is this? All performance figures come from EXIT-chart analysis and Monte Carlo computer simulation of an idealised depolarizing channel, with pre-shared entangled qubits assumed to reach the receiver without noise. No hardware experiment is involved.

Source & credits

Paper: Zunaira Babar, Panagiotis Botsinis, Dimitrios Alanis, Soon Xin Ng and Lajos Hanzo, “The Road From Classical to Quantum Codes: A Hashing Bound Approaching Design Procedure.” arXiv:1503.02372v1 [quant-ph], 9 March 2015, the preprint version read for this page: arxiv.org/abs/1503.02372 (DOI 10.48550/arXiv.1503.02372), distributed under arXiv’s non-exclusive licence. Published version: IEEE Access (2015), doi.org/10.1109/ACCESS.2015.2405533.

About the visuals. All charts and animations are original illustrations and re-plots, not reproductions of the paper’s figures. The hashing-bound chart is computed from the paper’s Eqs. 3, 5 and 6. The EXIT curves in the interactive sections are an illustrative model: the inner curve and the paper’s QIRCC curve are smooth fits to approximate values read from Fig. 22, the remaining subcode curves are synthetic, and the model is calibrated so that the paper’s mix closes at p = 0.345 and no rate-1/3 mix can pass the 0.3779 limit. Word-error-rate values are approximate readings from Figs. 23–24 (simulated results), modified and simplified. The noise lab and parity detective illustrate textbook concepts described in Secs. II and IV of the paper.

Topics in this iPaper

Physics
Powerful Quantum Error Correction Codes (QECCs) are required for stabilizing and protecting fragile qubits against the undesirable effects of quantum decoherence

Abstract, page 1

Computer science
we provide an extensive step-by-step tutorial for designing EXtrinsic Information Transfer (EXIT) chart aided concatenated quantum codes

Abstract, page 1

Engineering
Fig. 16 shows the general schematic of a quantum communication system relying on a pair of concatenated quantum stabilizer codes

Section V-B (System Model: Concatenated Quantum Codes), page 20

quantum error correction
Keywords—Quantum Error Correction, Turbo Codes, EXIT Charts, Hashing Bound

Keywords, page 1

turbo codes
hashing bound approaching QECCs may be designed by exploiting a concatenated code structure, which invokes iterative decoding

Abstract, page 1

extrinsic information transfer charts
we provide an extensive step-by-step tutorial for designing EXtrinsic Information Transfer (EXIT) chart aided concatenated quantum codes

Abstract, page 1

convolutional codes
our proposed Quantum Irregular Convolutional Code (QIRCC), which constitutes the outer component of a concatenated quantum code

Abstract, page 1

stabilizer codes
Most of the quantum codes developed to date owe their existence to the theory of stabilizer codes

Section IV (Stabilizer Formalism), page 9

hashing bound
the relationship between p and RQ for the depolarizing channel is defined by the hashing bound

Section II (Design Objectives), page 4

The Road From Classical to Quantum Codes: A Hashing Bound Approaching Design Procedure — Interactive explanation | iPaper.ai