Make your paper interactiveCreate

Text from the interactive explanation

Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies

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

Original paper

Quantum error correction · an interactive explainer

Qubits are fragile, and you can’t look at them to check for damage. Quantum codes ring alarms instead, and a decoder passes messages between alarms and qubits to work out what went wrong. But quantum rules plant tiny loops in these codes, where messages echo back and confuse the decoder.

Babar, Botsinis, Alanis, Ng and Hanzo surveyed fifteen years of quantum LDPC codes and proposed a simple cure for the worst of those loops: fuse each pair of twin alarms into one.

Echo

Merge

Resolve

An X error (a bit-flip) strikes qubit 1. Only the alarms watching it ring.

no error

X bit-flip

Z phase-flip

Y both

bit-flip alarm

phase-flip alarm

supernode

Live: the paper’s worked example (7-qubit Steane code, X error on qubit 1, noise level p = 0.26) decoded in your browser with both decoders the paper describes. Rings show each qubit’s belief; glowing dots are the messages.

1

Qubits forget

A classical bit is 0 or 1. A qubit can sit in a blend of both at once, called a superposition , and that blend gives quantum computers and quantum communication their power. It also makes qubits fragile. Any stray contact with the surroundings disturbs the state; physicists call this decoherence .

The paper uses the standard model of this damage, the depolarizing channel. Each qubit, independently, is hit with a small probability p, and a hit comes in one of three kinds, each with probability p/3:

X bit-flip : 0 and 1 swap places.

Z phase-flip : the hidden sign that relates 0 and 1 in the blend is reversed. Ordinary bits have nothing like it.

Y both at once.

X hits 0 · Z hits 0 · Y hits 0

Classical computers face noise too, and they beat it with error-correcting codes. The best classical low-density parity-check (LDPC) codes come within 0.13 dB of Shannon’s theoretical limit, so they are almost perfectly efficient. The question behind this paper: can quantum LDPC codes do the same for qubits? Researchers have chased that goal for fifteen years, and one stubborn obstacle sits inside the decoder.

2

Don’t look — ask parity questions

Here is the catch: measuring a qubit collapses its superposition and destroys the information you wanted to protect. So quantum codes never read their qubits directly. They ask indirect yes/no questions about groups of qubits, such as “do these two agree?” The answers reveal damage without revealing the stored content.

The paper’s simplest example spreads one qubit over three (α|000⟩ + β|111⟩). Two alarms compare pairs: alarm A asks whether qubits 1 and 2 agree, alarm B whether qubits 1 and 3 agree. A hidden bit-flip may have struck. Which qubit was it?

Read the alarms, then guess.

Score 0 / 0

The pattern of alarms is called the syndrome . It points at the error without anyone ever reading the stored state. Real codes also need alarms for phase-flips, and many more qubits. In a low-density parity-check code each alarm watches only a handful of qubits, so each qubit joins only a few checks. The paper notes that this sparseness suits quantum hardware, where every extra interaction is a chance for new errors.

3

Seven qubits, six alarms

The paper’s worked example is the 7-qubit Steane code , built from the classic (7,4) Hamming code. It has three bit-flip alarms (B1–B3, which notice X and Y) and three phase-flip alarms (P1–P3, which notice Z and Y). Tap the qubits to plant errors and watch which alarms ring. Try an X on qubit 1, then a Z, then a Y.

No errors planted — all six alarms are quiet.

Notice something? B1 and P1 watch exactly the same four qubits (1, 4, 6 and 7). So do B2/P2 and B3/P3. They are twins .

Codes that reuse one pattern for both kinds of alarm are called homogeneous CSS codes (after Calderbank, Shor and Steane). They include the Steane code, MacKay’s well-known bicycle codes and entanglement-assisted codes built the same way. On the graph, every twin pair closes loops such as qubit 1 → B1 → qubit 4 → P1 → back to qubit 1. That is a loop of length 4, the shortest possible. Each twin pair makes 6 of them, for 18 in all.

Why can’t quantum codes simply avoid short loops?

Quantum alarms must be compatible: mathematically they must commute, or reading one would disturb another. Two alarms commute only if they clash (apply different non-identity operators) on an even number of qubits. Tap the letters to edit the paper’s example pair:

Clashes on qubits 1 and 3.

Because clashes must come in even numbers, two alarms that share a clashing qubit must share at least one more, and that closes a length-4 loop. The paper concludes that every quantum LDPC code’s Tanner graph contains such loops. Twins in homogeneous CSS codes add many more.

4

Gossip on a graph

To name the culprit, the decoder runs belief propagation . Every alarm tells each of its qubits what it now believes about that qubit’s error, given what the other qubits said. Every qubit combines those opinions with its starting odds and replies. Round after round, each belief ring updates: mint means no error, coral X, cyan Z, violet Y. Decoding stops as soon as each qubit’s most likely error, taken together, explains every ringing alarm.

This is the paper’s worked example: an X hits qubit 1, and the noise is deliberately harsh (p = 0.26), so the decoder has to work.

Round 0 · every qubit starts at 74% “no error”.

Qubit 1’s beliefs (vertical axis) round by round (horizontal axis): thin lines with dots show the standard decoder, thick lines the supernode decoder. Re-computed in your browser from the paper’s algorithms (Sections IV-B and V); compare the paper’s Fig. 15.

The echo

Belief propagation is exact on a network without loops. On a loop, a qubit’s own message travels around and comes back two steps later, disguised as fresh evidence (press Trace an echo). Counted twice, beliefs become over-confident and slosh back and forth; the paper calls such messages “over-estimated”. With twin alarms every qubit sits on several of these tight loops, and the standard decoder never settles.

5

Merge the twins

The paper’s idea is disarmingly simple. Twin alarms watch the same qubits, so treat each pair as one supernode that must explain both of its alarms at once. The supernode reasons about the combined error on its qubits, so the twin loops vanish. There are also half as many alarm nodes to update each round, which makes the new decoder cheaper to run, not more expensive.

Merge the pairs (buttons, or drag a cyan alarm onto its coral twin), then press Play. By round 2, X on qubit 1 edges ahead of “no error”, 44.9% to 44.7% . That guess explains every alarm, so decoding stops: won by a whisker and confirmed by the alarms.

6

Try another culprit

One example could be luck. Pick any single error on any qubit and race the two decoders: same code, same harsh noise (p = 0.26), up to 30 rounds each.

Standard decoder

Pick an error above.

Supernode decoder

Pick an error above.

Scoreboard: run all 21 errors to fill it.

Tile badges: left dot = standard, right dot = supernode. ● found the error · ● settled on a wrong explanation that also fits the alarms · ● no answer within 30 rounds. Re-computed in your browser; the paper works through the X-on-qubit-1 case, and the other 20 are our extension of it. Allowing 90 rounds changes no outcome.

7

From seven qubits to eight hundred

Seven qubits are a toy. For their main test the authors used MacKay’s bicycle code : 800 qubits protecting 400, with each alarm watching 30 qubits. A bicycle code glues a random sparse pattern to its own mirror image. That trick automatically satisfies the quantum compatibility rule, and it also makes every alarm a twin.

Run the experiment yourself

Random errors on an 800-qubit bicycle code built the same way (row weight 30). Both decoders repair the same error in each trial.

Simulated in your browser on a code built the same way as MacKay’s, using the decoders described in the paper (up to 90 rounds; a block counts as repaired when the correction matches the real error up to a harmless stabilizer). Short runs are noisy; the paper’s large simulations follow below.

What the paper found

Monte Carlo simulations reported in the paper (up to 90 rounds). Bars show the harshest noise each decoder handles while still repairing at least 9,999 of every 10,000 blocks (word error rate ≤ 10⁻⁴). Longer is better.

Bicycle code: the supernode decoder copes with p = 0.014 instead of 0.01075.

Binary : handles bit-flips and phase-flips as two separate problems, ignoring that a Y error is both.

Standard non-binary : four-way beliefs (none, X, Z, Y), as in the lab above.

Random perturbation and enhanced feedback : earlier heuristics that nudge a stuck decoder and rerun it, at extra cost.

Modified non-binary : the paper’s supernode decoder.

Modified + enhanced feedback : the paper’s decoder combined with the feedback heuristic.

The entanglement-assisted code uses 404 pre-shared entangled pairs and alarms that watch 6 qubits each (paper Table 11).

Paper Table 10. Lower means fewer failed blocks; further left means fewer rounds on average. The supernode decoder needs 2.81 rounds on average and fails on 3.67 blocks in 10,000. Adding enhanced feedback cuts failures to 0.53 in 10,000 for only 2.96 rounds.

8

Turning down the echo

Supernodes remove the twin loops, but other loops remain. A second tool, uniformly-reweighted belief propagation (URW-BP) , softens every incoming message by raising it to a power ρ ≤ 1, so echoed evidence counts a little less. With ρ = 1 it is ordinary belief propagation.

Drag ρ to see what the softening does to one real message from the lab: alarm B1 telling qubit 1 that X or Y is likely.

ρ = 1.00: the message as computed.

What reweighting bought, on top of supernodes

Bicycle code, harshest noise handled at word error rate 10⁻³ (paper Table 14), for three round budgets. Pick a budget:

With up to 10 rounds: p = 0.0125 → 0.0155, a 24% gain in tolerable noise.

The best ρ creeps toward 1 as noise rises or as more rounds are allowed. In the paper’s words, reweighting is “more beneficial at low depolarizing probabilities and for smaller values of the maximum affordable number of iterations.”

9

Fifteen years in one scroll

Most of the paper is a survey of how researchers learned to build quantum LDPC codes despite the compatibility rule. It sorts the designs into four families. Tap a milestone (from the paper’s Fig. 8).

Dual-containing CSS

Non-dual-containing CSS

Non-CSS

Entanglement-assisted

Closing the gap

How far selected codes stayed from the Hashing bound (the quantum counterpart of Shannon’s limit) at word error rate 10⁻³, in decibels; smaller is better (paper Fig. 7).

10

Back to the opening question

Can quantum LDPC codes match their classical cousins? They inherit the sparse alarms and fast message-passing decoders that make classical LDPC codes nearly perfect. But quantum rules plant short loops that classical designers work hard to avoid, and homogeneous CSS codes are riddled with them, because every alarm has a twin.

The supernode decoder removes exactly those twin loops, and it costs less computation than the standard decoder. In the paper’s simulations it tolerated about 30% more noise on the bicycle code and 23% more on the entanglement-assisted code than standard non-binary belief propagation, at a word error rate of 10⁻⁴. It still pairs with enhanced feedback and reweighting for further gains. Every such step brings reliable quantum computation and communication a little closer.

A quantum code of rate k/n can be built from a classical binary code of rate (n+k)/2n, but only if its alarms obey the symplectic (compatibility) criterion.

Ideally rows overlap at most once, yet the rule demands even overlaps, so length-4 loops are unavoidable. Good codes must perform well despite them.

Dual-containing, non-dual-containing, non-CSS or entanglement-assisted: each trades performance against design difficulty, complexity or pre-shared entanglement.

Four-way beliefs capture bit/phase correlations; supernodes tame twin loops in homogeneous CSS codes; feedback and reweighting help further.

Source

Zunaira Babar, Panagiotis Botsinis, Dimitrios Alanis, Soon Xin Ng and Lajos Hanzo (University of Southampton). “Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies.” IEEE Access, vol. 3, pp. 2492–2519, 2015. doi:10.1109/ACCESS.2015.2503267

All graphics on this page are original and drawn in code; no figures are reproduced from the paper. Numbers are quoted from the paper’s Tables 9–14 and Figs. 7–8, and the timeline paraphrases Fig. 8. The Steane-code decoding, the 21-error race and the bicycle-code experiment are re-computed in your browser from the algorithms described in the paper’s Sections IV–VI. Our re-computation reproduces the paper’s Table 6 and Fig. 15.

Topics in this iPaper

Physics
Since decoherence may be characterized either by bit-flips or phase-flips or in fact possibly by both

Section I (Introduction), page 2493

Computer science
We also conceive a modified non-binary decoding algorithm for homogeneous Calderbank–Shor–Steane-type QLDPC codes

Abstract, page 2492

Engineering
General schematic of a quantum communication system.

Section II, Fig. 2 caption, page 2494

quantum error correction
Quantum error correction, low density parity check codes, quantum low density parity check codes, iterative decoding.

Index Terms, page 2492

low density parity check codes
The near-capacity performance of classical low-density parity check (LDPC) codes and their efficient iterative decoding makes quantum LDPC (QLPDC) codes a promising candidate for quantum error correction.

Abstract, page 2492

belief propagation
Belief propagation is capable of providing a reasonably good approximation to the optimization problem of Eq. (24)

Section VI, page 2511

stabilizer codes
QLDPC codes belong to the family of Quantum Stabilizer Codes (QSCs)

Section I (Introduction), page 2493

iterative decoding
our ‘Modified Non-Binary’ BP converges faster than the existing decoding schemes

Section VII-A, page 2513

Fifteen Years of Quantum LDPC Coding and Improved Decoding Strategies — Interactive explanation | iPaper.ai