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

arXiv:1204.2439 · IEEE Transactions on Information Theory

Degenerate Viterbi Decoding

Émilie Pelchat, David Poulin

Published Apr 25, 2013• 28 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2013.2246815

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

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

Quantum convolutional stabilizer codes

Neelima Chinthamani

Quantum error correction codes were introduced as a means to protect quantum information from decoherance and operational errors. Based on their approach to error control, error correcting codes can be divided into two different classes: block codes and convolutional codes. There has been significant development towards finding quantum block codes, since they were first discovered in 1995. In contrast, quantum convolutional codes remained mainly uninvestigated. In this thesis, we develop the stabilizer formalism for quantum convolutional codes. We define distance properties of these codes and give a general method for constructing encoding circuits, given a set of generators of the stabilizer of a quantum convolutional stabilizer code, is shown. The resulting encoding circuit enables online encoding of the qubits, i.e., the encoder does not have to wait for the input transmission to end before starting the encoding process. We develop the quantum analogue of the Viterbi algorithm. The quantum Viterbi algorithm (QVA) is a maximum likehood error estimation algorithm, the complexity of which grows linearly with the number of encoded qubits. A variation of the quantum Viterbi algorithm, the Windowed QVA, is also discussed. Using Windowed QVA, we can estimate the most likely error without waiting for the entire received sequence.

•Sep 30, 2004•0 citations

Revisiting Classical Syndrome Decoding

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

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.

Wiley eBooks•Dec 18, 2025•0 citations

Good quantum-convolutional error-correction codes and their decoding algorithm exist

H. F. Chau

A quantum-convolutional code was introduced recently as an alternative way to protect vital quantum information. To complete the analysis of the quantum-convolutional code, I report a way to decode certain quantum-convolutional codes based on the classical Viterbi decoding algorithm. This decoding algorithm is optimal for a memoryless channel. I also report three simple criteria to test if decoding errors in a quantum-convolutional code will terminate after a finite number of decoding steps whenever the Hilbert space dimension of each quantum register is a prime power. Finally, I show that certain quantum-convolutional codes are in fact stabilizer codes. And hence, these quantum stabilizer convolutional codes have fault-tolerant implementations.

arXiv:quant-ph/9806032•Physical Review A•Sep 1, 1999•26 citations

Syndrome decoding by quantum approximate optimization

Ching–Yi Lai, Kao-Yueh Kuo, Bo-Jyun Liao

Abstract The syndrome decoding problem is known to be NP-complete. The goal of the decoder is to find an error of low weight that corresponds to a given syndrome obtained from a parity-check matrix. We use the quantum approximate optimization algorithm (QAOA) to address the syndrome decoding problem with elegantly-designed reward Hamiltonians based on both generator and check matrices for classical and quantum codes.We evaluate the level-4 check-based QAOA decoding of the [7,4,3] Hamming code, as well as the level-4 generator-based QAOA decoding of the [[5,1,3]] quantum code.Remarkably, the simulation results demonstrate that the decoding performances match those of the maximum likelihood decoding. Moreover, we explore the possibility of enhancing QAOA by introducing additional redundant clauses to a combinatorial optimization problem while keeping the number of qubits unchanged. Finally, we study QAOA decoding of degenerate quantum codes.Typically, conventional decoders aim to find a unique error of minimum weight that matches a given syndrome. However, our observations reveal that QAOA has the intriguing ability to identify degenerate errors of comparable weight, providing multiple potential solutions that match the given syndrome with comparable probabilities.This is illustrated through simulations of the generator-based QAOA decoding of the [[9,1,3]] Shor code on specific error syndromes.

arXiv:2207.05942•Quantum Information Processing•Nov 1, 2024•9 citations
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.
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.
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.
Quantum error correction codes were introduced as a means to protect quantum information from decoherance and operational errors. Based on their approach to error control, error correcting codes can be divided into two different classes: block codes and convolutional codes. There has been significant development towards finding quantum block codes, since they were first discovered in 1995. In contrast, quantum convolutional codes remained mainly uninvestigated. In this thesis, we develop the stabilizer formalism for quantum convolutional codes. We define distance properties of these codes and give a general method for constructing encoding circuits, given a set of generators of the stabilizer of a quantum convolutional stabilizer code, is shown. The resulting encoding circuit enables online encoding of the qubits, i.e., the encoder does not have to wait for the input transmission to end before starting the encoding process. We develop the quantum analogue of the Viterbi algorithm. The quantum Viterbi algorithm (QVA) is a maximum likehood error estimation algorithm, the complexity of which grows linearly with the number of encoded qubits. A variation of the quantum Viterbi algorithm, the Windowed QVA, is also discussed. Using Windowed QVA, we can estimate the most likely error without waiting for the entire received sequence.
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.
A quantum-convolutional code was introduced recently as an alternative way to protect vital quantum information. To complete the analysis of the quantum-convolutional code, I report a way to decode certain quantum-convolutional codes based on the classical Viterbi decoding algorithm. This decoding algorithm is optimal for a memoryless channel. I also report three simple criteria to test if decoding errors in a quantum-convolutional code will terminate after a finite number of decoding steps whenever the Hilbert space dimension of each quantum register is a prime power. Finally, I show that certain quantum-convolutional codes are in fact stabilizer codes. And hence, these quantum stabilizer convolutional codes have fault-tolerant implementations.
Abstract The syndrome decoding problem is known to be NP-complete. The goal of the decoder is to find an error of low weight that corresponds to a given syndrome obtained from a parity-check matrix. We use the quantum approximate optimization algorithm (QAOA) to address the syndrome decoding problem with elegantly-designed reward Hamiltonians based on both generator and check matrices for classical and quantum codes.We evaluate the level-4 check-based QAOA decoding of the [7,4,3] Hamming code, as well as the level-4 generator-based QAOA decoding of the [[5,1,3]] quantum code.Remarkably, the simulation results demonstrate that the decoding performances match those of the maximum likelihood decoding. Moreover, we explore the possibility of enhancing QAOA by introducing additional redundant clauses to a combinatorial optimization problem while keeping the number of qubits unchanged. Finally, we study QAOA decoding of degenerate quantum codes.Typically, conventional decoders aim to find a unique error of minimum weight that matches a given syndrome. However, our observations reveal that QAOA has the intriguing ability to identify degenerate errors of comparable weight, providing multiple potential solutions that match the given syndrome with comparable probabilities.This is illustrated through simulations of the generator-based QAOA decoding of the [[9,1,3]] Shor code on specific error syndromes.