Text from the interactive explanation
Fully-Parallel Quantum Turbo Decoder
Zunaira Babar, Hung Viet Nguyen, Panagiotis Botsinis, Dimitrios Alanis, Daryus Chandra, Soon Xin Ng, Robert G. Maunder, Lajos Hanzo
Original paperBabar, Nguyen, Botsinis, Alanis, Chandra, Ng, Maunder & Hanzo · “Fully-Parallel Quantum Turbo Decoder” · IEEE Access 2016
Qubits forget. Noise scrambles them, and after a short coherence time they lose their quantum information altogether, so error correction has to finish first. Here the same noisy block of qubits is decoded two ways on the same clock: one decoder takes its steps one at a time, the other runs every step at once.
One block at a time
All blocks at once
Race on: both decoders started on the identical noisy block of qubits.
Amber comet: the conventional decoder’s single active block, one per tick
Cyan glow: every block of the fully-parallel decoder works every tick
Top row: guess for each data qubit, right / wrong / none yet
Sparks: physical qubits hit by channel noise (bottom row brightness = decoder confidence)
Pips at right: blocks of qubits finished this round
Glow and fuse: an illustrative coherence clock that fades with the ticks spent on the current block (time constant 150 ticks; not a measured value)
Simulated live The paper’s own code (two [3,1,3] quantum convolutional codes, rate 1/9) and decoding equations, run in your browser on frames much shorter than the paper’s 1000 data qubits. One tick is one decoding time period. Each decoder stops once every guess is right (the simulation knows the true errors) or at 16 / 160 iterations.
Predict: if you double the frame length, what happens to each lane?
Three ways a qubit goes wrong
Picture each qubit as a small compass with two dials. The arrow is its bit value. The ring is its phase, a purely quantum property with no everyday counterpart. In the paper’s noise model, the depolarizing channel, every qubit is hit independently with total probability p: a bit flip X turns the arrow over, a phase flip Z flips the ring, and Y does both. Each of the three happens with probability p/3.
X 0 · Z 0 · Y 0 → 0 of 30 qubits hit
After decoding, what counts is the qubit error rate (QBER) : the fraction of data qubits that are still wrong. The paper’s benchmark is a QBER of 10−4, one wrong qubit in ten thousand.
The second enemy is time. Even untouched by noise, a qubit gradually loses its quantum state (it decoheres) within its coherence time. That is why slow decoding is dangerous; as the authors put it, “the qubits may decohere faster than they can be corrected. This would in turn render the error correction procedure useless.”
Why not just look?
With ordinary bits you could read each one and check. Measuring a qubit, though, collapses its superposition and destroys exactly the information you want to protect. Stabilizer codes sidestep this: extra helper qubits (ancillas) are coupled to the data, and only the helpers are measured. The result, the syndrome , gives clues about which errors happened, never about the data itself.
One more twist: different errors can have exactly the same effect on the encoded data. Quantum decoding is therefore degenerate. The decoder looks for the most likely class of error rather than one exact culprit.
Clues without looking
The paper’s code is built from quantum convolutional codes . Block by block, the encoder turns each data qubit into 3 physical qubits, while 3 memory qubits carry information from each block into the next. Below is one such chain of 16 blocks, using the paper’s own encoder (the “PTO1R” seed, Eq. 33). Tap a qubit to give it an error (none → X → Z → Y). The lamps under each block are its clues: the syndrome bits measured from that block’s helper qubits.
No errors → every clue lamp is dark. Tap a qubit to add one.
Notice how a single error lights a trail of lamps stretching back toward block 1: the encoder’s memory qubits spread its influence across other blocks. So one clue depends on many errors, and one error touches many clues. The decoder cannot judge a block on its own. It has to reason along the whole chain, passing messages from each block to its neighbours, and that is where the time goes .
Two codes passing notes
A quantum turbo code chains two of these convolutional codes. The outer code turns each data qubit into 3; a quantum interleaver shuffles those qubits; the inner code turns each of them into 3 more. Every data qubit ends up spread over 9 physical qubits (a rate-1/9 code).
Decoding runs the other way, as a conversation. The inner decoder reads the channel clues and forms soft guesses (probabilities, not verdicts) about its qubits. Through the shuffle it hands them to the outer decoder , which combines them with its own clues and sends improved guesses back. Like two detectives comparing notes, each round, called an iteration, sharpens both. Here is the conventional decoder on 32 data qubits: the amber comet sweeps the inner row forward and back, then the outer row.
No guesses yet.
Predict: will more iterations always fix everything? Try p = 0.12.
A relay race inside the decoder
Zoom in on one decoder’s chain of blocks. In the conventional decoder (the paper’s Fig. 4), block t needs a fresh message from block t − 1 (the forward message, α) and from block t + 1 (the backward message, β). So the blocks must take turns: a forward sweep from the first block to the last, then a backward sweep home. That costs 2N time periods for one decoder, and inner plus outer makes 2N1 + 2N2 per iteration . With N2 = 3N1, that is 8N1 periods. Double the frame, double the wait.
Relay · tick 0
Schematic Each row is one tick, time running down; each column is one block of the chain. Tap a block (or press Drop a clue) to plant a strong piece of evidence there and watch which blocks hear about it, shown in mint.
Everyone at once
The fully-parallel decoder breaks the chain of waiting. Every block of both decoders runs in every time period , using the messages its neighbours (and the other decoder) produced in the previous period (Eqs. 30–32). One iteration becomes a single time period, whatever the frame length. Switch the diagram above to All at once: whole rows light up.
The price shows in the light cone. News now travels just one block per iteration, whereas one relay sweep carries a clue along the whole chain in a single iteration. So the parallel decoder needs more iterations: about 10 to 12 times more in the authors’ simulations (Table 1). But 50 iterations of one period each beat 4.6 iterations of 8000 periods each by a wide margin.
How much faster? Paper’s numbers
≈ 736× fewer time periods
Iteration counts are the averages the authors obtained in simulations at N1 = 1000 (Table 1); here they are held fixed for other frame lengths. The paper’s rule of thumb, about ten times more iterations, gives a reduction of (2N1 + 2N2)/10 = 0.8·N1 for any frame length: 800× at this N1.
The checkerboard trick
Colour the blocks in two sets, as the paper’s Fig. 5 does: odd-numbered inner blocks plus even-numbered outer blocks are dark , the rest are light . Along each chain, neighbours always have opposite colours. The interleaver threads are the wild card: shuffled at random, many of them join two blocks of the same colour.
–
Tick A: dark blocks compute
The odd–even interleaver connects odd blocks only to odd blocks and even only to even, so every thread joins dark to light. Then something neat happens. In the all-at-once schedule, dark blocks only ever listen to light blocks from the previous tick, and vice versa, so the computation splits into two identical copies that never exchange information . Switch the space-time diagram to Checkerboard to watch one copy form a chessboard pattern in space and time.
Only one copy needs computing. Run the dark blocks in one period and the light ones in the next: each iteration takes two periods, but half as many iterations are needed. Same delay, half the work , and the paper’s Table 2 confirms it.
Average iterations needed, fully-parallel decoder Table 2
At every noise level the odd–even interleaver roughly halves the iterations (80→41, 50→26, 35→18, 28→15) while reaching the same QBER (the paper’s Fig. 8). Two periods per iteration keep the delay unchanged.
Run the experiment yourself
Here the paper’s decoding equations run in your browser on fresh random noise. For every frame, three decoders see exactly the same channel errors : the conventional decoder, the fully-parallel decoder, and the fully-parallel decoder with an odd–even interleaver. Each stops once all its guesses are right (the simulation knows the true errors) or at a cap of 16, 160 and 100 iterations respectively.
Simulated in your browser frames shorter than the paper’s (N1 = 24–192 instead of 1000), so the numbers differ from Table 1, but the pattern is the same.
No frames yet. Press Run.
(a) Wrong data qubits vs iteration
QBER after each iteration, averaged over all frames. A curve that drops to the bottom edge means every frame was fixed; a frame that never finishes leaves a plateau. The parallel decoders need many more iterations.
(b) Wrong data qubits vs elapsed time periods
The same curves on the clock. The cyan and violet curves reach the floor far sooner, because each of their iterations costs 1 or 2 periods instead of 8·N1.
(c) Cost to finish a frame (finished frames only)
What the paper found
The authors simulated a rate-1/9 quantum turbo code built from two [3,1,3] convolutional codes over the depolarizing channel, with frames of 1000 data qubits (an interleaver of 3000 qubits) and approximate-log decoding. The charts below re-plot their reported values.
Average iterations to converge Table 1
At each noise level the fully-parallel decoder needs 10–12 times more iterations. That is its price, paid in computation, not in time.
Distance from the Hashing bound at QBER 10−4 Fig. 7
Given 10× the iterations, the two decoders land on identical points for every frame length tested, so the speed costs no accuracy. Longer frames get closer to the limit.
The Hashing bound is a theoretical ceiling: the most noise a code of this rate (1/9) could ever cope with in principle, p ≈ 0.160 for the depolarizing channel. A distance of 1.5 dB means the decoder reaches QBER 10−4 up to p ≈ 0.113.
The paper’s Fig. 6 tells the same story curve by curve: with I = 10, 20, 40, 60, 80 parallel iterations against I = 1, 2, 4, 6, 8 conventional ones, the error-rate curves match pairwise, both for 3000-qubit and 1500-qubit interleavers.
Go deeper
Each algorithmic block t scores every valid transition of the encoder circuit: previous memory error μ, logical error λ, and helper (ancilla) error σ consistent with the measured syndrome. The a-priori transition metric adds the log-probabilities of the logical and physical errors:
The forward message runs left to right, the backward message right to left:
Because ᾱₜ needs ᾱₜ₋₁ and β̄ₜ₋₁ needs β̄ₜ, the conventional decoder must compute them one block after another: N periods forward, N backward.
In the fully-parallel decoder every block uses the messages and a-priori information from the previous iteration, so all N1 + N2 blocks can run at the same time:
The new ᾱₜ is handed to block t + 1 and the new β̄ₜ₋₁ to block t − 1 for use in the next iteration. Messages not yet available are initialised to zero (equiprobable).
Working with log-probabilities turns sums of probabilities into a special operation:
The correction term is read from a small precomputed table, the “approximate-log” variant used in the paper and in this page’s simulator.
Errors that differ only by an element of the stabilizer group act identically on the encoded data and are fixed by the same recovery. The syndrome-based decoders therefore estimate the most likely error coset on the outer code’s logical qubits, using only the X-component of the measured syndromes, and a final MAP decision picks the recovery.
Back to the race
Stretch the frame and watch the two delays. The conventional decoder’s latency grows in step with the number of data qubits; the fully-parallel decoder’s stays flat.
This is the paper’s point in one picture: error correction whose delay no longer grows with the size of the block of qubits . That matters most where qubits have short coherence times. The price is about ten times more computation, and the odd–even interleaver wins half of that back.
Faster quantum error correction serves the applications the authors list as motivation:
quantum key distribution
quantum teleportation
quantum secure direct communication
distributed quantum computing networks
protecting quantum computers from faulty gates and decoherence
Back to the top and race the decoders once more, this time with N1 = 48.
Source and credits
Z. Babar, H. V. Nguyen, P. Botsinis, D. Alanis, D. Chandra, S. X. Ng, R. G. Maunder and L. Hanzo, “Fully-Parallel Quantum Turbo Decoder,” IEEE Access, vol. 4, pp. 6073–6085, 2016. DOI: 10.1109/ACCESS.2016.2581978
Article published open access; Crossref lists the licence as CC BY 3.0.
All visuals on this page are original. The charts re-plot values reported in the paper (Tables 1–2 and Fig. 7); no figures are reproduced. The in-browser simulator implements the paper’s decoding equations (Eqs. 21–32) with its PTO1R seed transformation (Eq. 33) and approximate-log max*, on frames shorter than the paper’s. It assumes an error-free tail for the outer code and stops decoding once every guess is right, because the simulation knows the true errors (or at an iteration cap). The coherence glow in the race is illustrative, not a measured coherence time.
Topics in this iPaper
Physics
Quantum Error Correction Codes (QECCs) are indispensable for the reliable transmission of fragile quantum information (or qubits) over noisy quantum channels.
Section I, page 6073
Engineering
we conceive a fully-parallel quantum turbo decoder (FPQTD), which eliminates the inherent time dependences of the conventional decoder by executing all the associated processes concurrently.
Abstract, page 6073
Computer science
Quantum error correction, turbo codes, fully-parallel decoding, iterative decoding.
Index terms, page 6073
quantum error correction
Quantum error correction, turbo codes, fully-parallel decoding, iterative decoding.
Index terms, page 6073
turbo codes
Quantum turbo codes (QTCs) are known to operate close to the achievable Hashing bound.
Abstract, page 6073
iterative decoding
both the inner as well as the outer decoders operate on the basis of the a-priori information gathered from the previous decoding iteration
Section IV-B, page 6080
parallel computing
allowing all the constituent algorithmic blocks to operate concurrently
Section VI, page 6083
quantum convolutional codes
a rate-1/9 QTC, consisting of two serially concatenated [3, 1, 3] QCCs
Section V, page 6081
depolarizing channel
each qubit may independently experience either a bit-flip (X), a phase-flip (Z) or both (Y) with a probability of p/3 each
Section II-C, page 6074