Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Wiley eBooks

Revisiting Classical Syndrome Decoding

Zunaira Babar, Daryus Chandra, Soon Xin Ng, Lajos Hanzo

Published Dec 18, 2025• 0 citations
Publisher

Abstract

We commence by discussing classical syndrome decoding techniques that form the foundation for quantum error correction. Explicitly, they allow us to ascertain where the depolarization-induced errors occur and then to correct them without observing the quantum bits themselves. We then continue with a review of look-up table-based syndrome decoding designed for linear block codes, followed by the construction of syndrome-based error trellises for both block and convolutional codes. The chapter introduces trellis-based decoding using both the Viterbi and the Maximum A Posteriori algorithms, emphasizing their role in estimating the error patterns encountered from syndrome sequences. A reduced-complexity block syndrome decoding-based technique is presented for improving the decoding efficiency of turbo trellis coded modulation (TTCM) schemes. Simulation results recorded for transmission over AWGN and Rayleigh fading channels demonstrate significant complexity reductions, quantified in terms of the number of non-decoded blocks and the average number of iterations. The chapter concludes by highlighting the block syndrome decoder's potential for future designs.

DOI
10.1002/9781394331963.ch04

Related papers

Quantum convolutional codes: Practical syndrome decoder

Peiyu Tan, Jing Li

Quantum convolutional codes are predicted by many to offer higher error correction performance than quantum block codes of equivalent encoding complexity. However, to decode a quantum convolutional code is challenging, because the decoder does not have a measurement of the received codeword (due to the quantum mechanic rule “measurement destroys quantum states”), but only a measurement of the syndrome. Although quantum Viterbi decoding (QVD) has been proposed, its high complexity makes it rather difficult to implement or simulate. Exploiting useful ideas from classical coding theory, this paper develops a practical quantum syndrome decoder (QSD) by introducing two innovations that drastically reduce the decoding complexity compared to the existing QVD. The new decoder uses an efficient linear-circuits-based mechanism to map a syndrome to a candidate vector, obviating the need of a cumbersome lookup table. It is also cleverly engineered such that only one run of the Viterbi algorithm suffices to locate the most-likely error pattern, rather than have to run many rounds as in the previous QVD algorithm. The efficiency of the new decoder allows us to simulate and present the first performance curve of a general quantum convolutional code.

Conference on Information Sciences and Systems•Mar 1, 2012•0 citations

Iterative quantum coding systems

David Poulin

Introduction This chapter concerns quantum coding schemes based on iterative decoding. So far, most of the focus of this book has been on quantum error-correcting codes (QECCs) that use a relatively small number of qubits, and concatenation thereof. The decoding strategy adopted for these codes consists of identifying the lowest-weight error that is consistent with the syndrome and reversing its effect. The lowest-weight error associated with each syndrome can, in the worst case, be found by exhaustive search and stored in a look-up table for future reference. Each time a syndrome is measured, the appropriate recovery can be rapidly extracted from the table to complete the error-correction cycle. In contrast, the codes described in this chapter use a very large number of qubits; the larger the better! For a fixed rate r = k / n , the performance of the codes improves as n increases. For such large codes however, more clever decoding schemes are required. For a code with parameters [[ n, k, d ]], the size of the look-up table – i.e. the number of distinct syndromes – is 2 n−k = 2(1− r ) n . Thus, look-up tables are only suitable for codes of a few dozen qubits. For larger codes, the decoding process involves a highly nontrivial computation that needs to be executed “on the fly,” so fast and reliable algorithms are needed. Iterative decoding is one such algorithm and it has produced some of the best coding schemes – in particular turbo-codes and sparse codes – widely used in classical wireless communication.

Cambridge University Press eBooks•Sep 5, 2013•0 citations

Quantum Block Turbo Codes

Khaled Jebari, Luiz Anet Neto, Ramesh Pyndiah +1 more

In the early nineties, the introduction of turbo codes revolutionized classical error correction. The idea was mainly applied on two types of codes: convolutional turbo codes and turbo product codes. The first type of codes was adapted to quantum error correction which initiated the theory of quantum serial turbo codes. In this paper, we present a theory for quantum block turbo codes, the quantum analog of the second type of turbo codes. We describe their iterative decoding algorithm and simulate their performances on a depolarizing channel for different constituent codes.

quant-pharXiv:2608.30775•Sep 1, 2026•2 citations

Efficient ML Decoding for Quantum Convolutional Codes

Peiyu Tan, Jing Li

A novel decoding algorithm is developed for general quantum convolutional codes. Exploiting useful ideas from classical coding theory, the new decoder introduces two innovations that drastically reduce the decoding complexity compared to the existing quantum Viterbi decoder. First, the new decoder uses an efficient linear-circuits-based mechanism to map a syndrome to a candidate vector, whereas the existing algorithm relies on a non-trivial lookup table. Second, the new algorithm is cleverly engineered such that only one run of the Viterbi algorithm suffices to locate the most-likely error pattern, whereas the existing algorithm must run the Viterbi algorithm many times. The efficiency of the proposed algorithm allows us to simulate and present the first performance curve of a general quantum convolutional code.

arXiv:1004.0174•Apr 1, 2010•1 citation

From Classical to Quantum Coding

Zunaira Babar, Daryus Chandra, Soon Xin Ng +1 more

An expert discussion of the potential evolution of quantum codes In From Classical to Quantum Coding, a team of distinguished researchers deliver a seamless book on the subject of quantum error correction codes (QECC) designed for mitigating the environment-induced decoherence imposed on quantum computing and communications. Commencing from first principles, Part I is dedicated to readers familiar with classical coding and wishing to move into quantum coding. Part II focuses on near-term quantum codes requiring a modest to moderate number of qubits. Finally, Part III of the book offers an outlook on the classical to quantum evolution of QECCs, to advanced codes that rely on numerous qubits as quantum technology matures. The book incorporates several advanced topics, including the universal decoding of arbitrary linear codes, iterative short turbo block codes, turbo convolutional codes, and the family of low-density parity check codes. The powerful design tool of extrinsic information transfer charts plays a central role in the associated near-hashing-bound designs. Readers will also find: An easy-reading introduction to quantum information processing and quantum coding An evolutionary portrayal of the classical to quantum coding paradigm Practical discussions of near-term quantum topological error correction codes and how they protect quantum gates from decoherence Detailed treatments of syndrome-based decoding of diverse quantum turbo codes and quantum low-density parity check codes From Classical to Quantum Coding will benefit doctoral students, and industrial and academic researchers wishing to expand their expertise from the classical to the quantum field of signal processing, computing and communications.

Wiley eBooks•Dec 18, 2025•0 citations

Degenerate Viterbi Decoding

Émilie Pelchat, David Poulin

We present a decoding algorithm for quantum convolutional codes that finds the class of degenerate errors with the largest probability conditioned on a given error syndrome. The algorithm runs in time linear with the number of qubits. Previous decoding algorithms for quantum convolutional codes optimized the probability over individual errors instead of classes of degenerate errors. Using Monte Carlo simulations, we show that this modification to the decoding algorithm results in a significantly lower block error rate.

arXiv:1204.2439•IEEE Transactions on Information Theory•Apr 25, 2013•28 citations
We commence by discussing classical syndrome decoding techniques that form the foundation for quantum error correction. Explicitly, they allow us to ascertain where the depolarization-induced errors occur and then to correct them without observing the quantum bits themselves. We then continue with a review of look-up table-based syndrome decoding designed for linear block codes, followed by the construction of syndrome-based error trellises for both block and convolutional codes. The chapter introduces trellis-based decoding using both the Viterbi and the Maximum A Posteriori algorithms, emphasizing their role in estimating the error patterns encountered from syndrome sequences. A reduced-complexity block syndrome decoding-based technique is presented for improving the decoding efficiency of turbo trellis coded modulation (TTCM) schemes. Simulation results recorded for transmission over AWGN and Rayleigh fading channels demonstrate significant complexity reductions, quantified in terms of the number of non-decoded blocks and the average number of iterations. The chapter concludes by highlighting the block syndrome decoder's potential for future designs.
Quantum convolutional codes are predicted by many to offer higher error correction performance than quantum block codes of equivalent encoding complexity. However, to decode a quantum convolutional code is challenging, because the decoder does not have a measurement of the received codeword (due to the quantum mechanic rule “measurement destroys quantum states”), but only a measurement of the syndrome. Although quantum Viterbi decoding (QVD) has been proposed, its high complexity makes it rather difficult to implement or simulate. Exploiting useful ideas from classical coding theory, this paper develops a practical quantum syndrome decoder (QSD) by introducing two innovations that drastically reduce the decoding complexity compared to the existing QVD. The new decoder uses an efficient linear-circuits-based mechanism to map a syndrome to a candidate vector, obviating the need of a cumbersome lookup table. It is also cleverly engineered such that only one run of the Viterbi algorithm suffices to locate the most-likely error pattern, rather than have to run many rounds as in the previous QVD algorithm. The efficiency of the new decoder allows us to simulate and present the first performance curve of a general quantum convolutional code.
Introduction This chapter concerns quantum coding schemes based on iterative decoding. So far, most of the focus of this book has been on quantum error-correcting codes (QECCs) that use a relatively small number of qubits, and concatenation thereof. The decoding strategy adopted for these codes consists of identifying the lowest-weight error that is consistent with the syndrome and reversing its effect. The lowest-weight error associated with each syndrome can, in the worst case, be found by exhaustive search and stored in a look-up table for future reference. Each time a syndrome is measured, the appropriate recovery can be rapidly extracted from the table to complete the error-correction cycle. In contrast, the codes described in this chapter use a very large number of qubits; the larger the better! For a fixed rate r = k / n , the performance of the codes improves as n increases. For such large codes however, more clever decoding schemes are required. For a code with parameters [[ n, k, d ]], the size of the look-up table – i.e. the number of distinct syndromes – is 2 n−k = 2(1− r ) n . Thus, look-up tables are only suitable for codes of a few dozen qubits. For larger codes, the decoding process involves a highly nontrivial computation that needs to be executed “on the fly,” so fast and reliable algorithms are needed. Iterative decoding is one such algorithm and it has produced some of the best coding schemes – in particular turbo-codes and sparse codes – widely used in classical wireless communication.
In the early nineties, the introduction of turbo codes revolutionized classical error correction. The idea was mainly applied on two types of codes: convolutional turbo codes and turbo product codes. The first type of codes was adapted to quantum error correction which initiated the theory of quantum serial turbo codes. In this paper, we present a theory for quantum block turbo codes, the quantum analog of the second type of turbo codes. We describe their iterative decoding algorithm and simulate their performances on a depolarizing channel for different constituent codes.
A novel decoding algorithm is developed for general quantum convolutional codes. Exploiting useful ideas from classical coding theory, the new decoder introduces two innovations that drastically reduce the decoding complexity compared to the existing quantum Viterbi decoder. First, the new decoder uses an efficient linear-circuits-based mechanism to map a syndrome to a candidate vector, whereas the existing algorithm relies on a non-trivial lookup table. Second, the new algorithm is cleverly engineered such that only one run of the Viterbi algorithm suffices to locate the most-likely error pattern, whereas the existing algorithm must run the Viterbi algorithm many times. The efficiency of the proposed algorithm allows us to simulate and present the first performance curve of a general quantum convolutional code.
An expert discussion of the potential evolution of quantum codes In From Classical to Quantum Coding, a team of distinguished researchers deliver a seamless book on the subject of quantum error correction codes (QECC) designed for mitigating the environment-induced decoherence imposed on quantum computing and communications. Commencing from first principles, Part I is dedicated to readers familiar with classical coding and wishing to move into quantum coding. Part II focuses on near-term quantum codes requiring a modest to moderate number of qubits. Finally, Part III of the book offers an outlook on the classical to quantum evolution of QECCs, to advanced codes that rely on numerous qubits as quantum technology matures. The book incorporates several advanced topics, including the universal decoding of arbitrary linear codes, iterative short turbo block codes, turbo convolutional codes, and the family of low-density parity check codes. The powerful design tool of extrinsic information transfer charts plays a central role in the associated near-hashing-bound designs. Readers will also find: An easy-reading introduction to quantum information processing and quantum coding An evolutionary portrayal of the classical to quantum coding paradigm Practical discussions of near-term quantum topological error correction codes and how they protect quantum gates from decoherence Detailed treatments of syndrome-based decoding of diverse quantum turbo codes and quantum low-density parity check codes From Classical to Quantum Coding will benefit doctoral students, and industrial and academic researchers wishing to expand their expertise from the classical to the quantum field of signal processing, computing and communications.
We present a decoding algorithm for quantum convolutional codes that finds the class of degenerate errors with the largest probability conditioned on a given error syndrome. The algorithm runs in time linear with the number of qubits. Previous decoding algorithms for quantum convolutional codes optimized the probability over individual errors instead of classes of degenerate errors. Using Monte Carlo simulations, we show that this modification to the decoding algorithm results in a significantly lower block error rate.