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:2411.13509 · npj Quantum Information

Degenerate quantum erasure decoding

Kao-Yueh Kuo, Yingkai Ouyang

Published Mar 13, 2026• 5 citations
arXivHTMLPDF

Abstract

Abstract Erasures are the primary type of errors in physical systems dominated by leakage errors. While quantum error correction (QEC) using stabilizer codes can combat erasure errors, it remains unknown which constructions achieve capacity performance. If such codes exist, decoders with linear runtime in the code length are also desired. In this paper, we present erasure capacity-achieving quantum codes under maximum-likelihood decoding (MLD), though MLD requires cubic runtime in the code length. For QEC, using an accurate decoder with the shortest possible runtime will minimize the degradation of quantum information while awaiting the decoder’s decision. To address this, we propose belief propagation (BP) decoders that run in linear time and exploit error degeneracy in stabilizer codes, achieving capacity or near-capacity performance for a broad class of codes, including bicycle codes, product codes, and topological codes. We furthermore explore the potential of our BP decoders to handle mixed erasure and depolarizing errors, and also local deletion errors via concatenation with permutation invariant codes.

DOI
10.1038/s41534-026-01212-3

Related papers

Exploiting degeneracy in belief propagation decoding of quantum codes

Kao-Yueh Kuo, Ching–Yi Lai

Abstract Quantum information needs to be protected by quantum error-correcting codes due to imperfect physical devices and operations. One would like to have an efficient and high-performance decoding procedure for the class of quantum stabilizer codes. A potential candidate is Gallager’s sum-product algorithm, also known as Pearl’s belief propagation (BP), but its performance suffers from the many short cycles inherent in a quantum stabilizer code, especially highly-degenerate codes. A general impression exists that BP is not effective for topological codes. In this paper, we propose a decoding algorithm for quantum codes based on quaternary BP with additional memory effects (called MBP). This MBP is like a recursive neural network with inhibitions between neurons (edges with negative weights), which enhance the perception capability of a network. Moreover, MBP exploits the degeneracy of a quantum code so that the most probable error or its degenerate errors can be found with high probability. The decoding performance is significantly improved over the conventional BP for various quantum codes, including quantum bicycle, hypergraph-product, surface and toric codes. For MBP on the surface and toric codes over depolarizing errors, we observe error thresholds of 16% and 17.5%, respectively.

arXiv:2104.13659•npj Quantum Information•Sep 14, 2022•47 citations

Affine Subcode Ensemble Decoding for Degeneracy-Aware Quantum Error Correction

Leo Wursthorn, Jonathan Mandelbaum, Sisi Miao +4 more

Quantum low-density parity-check codes are promising candidates for low-overhead fault-tolerant quantum computing, but degeneracy is known to impair the convergence of belief-propagation (BP) decoding of these codes. In this work, we show that appending linearly independent rows to a check matrix of a stabilizer code can reduce the search space for a valid degenerate solution. Motivated by this, we extend the recently proposed affine subcode ensemble decoding technique from the classical to the quantum setting. Moreover, we employ overcomplete matrices for each decoding path. Monte-Carlo simulations on toric and generalized bicycle codes demonstrate improved convergence and reduced logical error rate.

cs.ITCross-listedarXiv:2605.06547•May 8, 2026•0 citations

Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation

Hanwen Yao, Waleed Abu Laban, Christian Häger +2 more

Quantum low-density parity-check (QLDPC) codes have emerged as a promising technique for quantum error correction. A variety of decoders have been proposed for QLDPC codes and many utilize belief propagation (BP) decoding in some fashion. However, the use of BP decoding for degenerate QLDPC codes is known to have issues with convergence. These issues are typically attributed to short cycles in the Tanner graph and error patterns with the same syndrome due to code degeneracy. In this work, we propose a decoder for QLDPC codes based on BP guided decimation (BPGD), which has been previously studied for constraint satisfaction and lossy compression problems. This decimation process is applicable to both binary and quaternary BP and it involves sequentially freezing the value of the most reliable qubits to encourage BP convergence. We find that BPGD significantly reduces the BP failure rate due to non-convergence, achieving performance on par with BP with ordered statistics decoding and BP with stabilizer inactivation, without the need to solve systems of linear equations. To explore how and why BPGD improves performance, we discuss several interpretations of BPGD and their connection to BP syndrome decoding.

arXiv:2312.10950•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•29 citations

Degenerate Quantum LDPC Codes With Good Finite Length Performance

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

We study the performance of medium-length quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes with the maximal stabilizer weight much smaller than their minimum distance are considered. It is shown that with the help of OSD-like post-processing the performance of the standard belief propagation (BP) decoder on many QLDPC codes can be improved by several orders of magnitude. Using this new BP-OSD decoder we study the performance of several known classes of degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah's cubic codes. We also construct several interesting examples of short generalized bicycle codes. Some of them have an additional property that their syndromes are protected by small BCH codes, which may be useful for the fault-tolerant syndrome measurement. We also propose a new large family of QLDPC codes that contains the class of hypergraph product codes, where one of the used parity-check matrices is square. It is shown that in some cases such codes have better performance than hypergraph product codes. Finally, we demonstrate that the performance of the proposed BP-OSD decoder for some of the constructed codes is better than for a relatively large surface code decoded by a near-optimal decoder.

arXiv:1904.02703•Quantum•Nov 22, 2021•257 citations

Erasure Decoding for Quantum LDPC Codes via Belief Propagation with Guided Decimation

Mert Gökduman, Hanwen Yao, Henry D. Pfister

Quantum low-density parity-check (LDPC) codes are a promising family of quantum error-correcting codes for fault tolerant quantum computing with low overhead. Decoding quantum LDPC codes on quantum erasure channels has received more attention recently due to advances in erasure conversion for various types of qubits including neutral atoms, trapped ions, and superconducting qubits. Belief propagation with guided decimation (BPGD) decoding of quantum LDPC codes has demonstrated good performance in bit-flip and depolarizing noise. In this work, we apply BPGD decoding to quantum erasure channels. Using a natural modification, we show that BPGD offers competitive performance on quantum erasure channels for multiple families of quantum LDPC codes. Furthermore, we show that the performance of BPGD decoding on erasure channels can sometimes be improved significantly by either adding damping or adjusting the initial channel log-likelihood ratio for bits that are not erased. More generally, our results demonstrate BPGD is an effective general-purpose solution for erasure decoding across the quantum LDPC landscape.

arXiv:2411.08177•Allerton Conference on Communication, Control, and Computing•Sep 24, 2024•12 citations

Decimation Strategies for Belief Propagation Decoding of Quantum LDPC Codes

Masoumeh Alinia, David G. M. Mitchell, Hanwen Yao +1 more

Due to code degeneracy and the graph structure of quantum low-density parity-check (QLDPC) codes, the performance of conventional belief propagation (BP) decoding can be poor. Recently, belief propagation guided decimation (BPGD) has shown promise to combat these challenges. In this paper, we investigate various decimation approaches to improve the error correcting performance and convergence speed of BPGD. We first consider soft decimation, where the BP equations are modified via several tuneable parameters. This approach exhibits linear complexity relative to the length of the block code and is shown to outperform hard decimation approaches for careful selection of the algorithm parameters. We then combine the approaches in a "soft-hard" BPGD variant, where hard decisions are periodically made and those symbols are permanently fixed throughout the remainder of the decoding process. Simulation results show that further performance improvement can be observed in this case at the cost of increasing the algorithmic complexity.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•1 citation
Abstract Erasures are the primary type of errors in physical systems dominated by leakage errors. While quantum error correction (QEC) using stabilizer codes can combat erasure errors, it remains unknown which constructions achieve capacity performance. If such codes exist, decoders with linear runtime in the code length are also desired. In this paper, we present erasure capacity-achieving quantum codes under maximum-likelihood decoding (MLD), though MLD requires cubic runtime in the code length. For QEC, using an accurate decoder with the shortest possible runtime will minimize the degradation of quantum information while awaiting the decoder’s decision. To address this, we propose belief propagation (BP) decoders that run in linear time and exploit error degeneracy in stabilizer codes, achieving capacity or near-capacity performance for a broad class of codes, including bicycle codes, product codes, and topological codes. We furthermore explore the potential of our BP decoders to handle mixed erasure and depolarizing errors, and also local deletion errors via concatenation with permutation invariant codes.
Abstract Quantum information needs to be protected by quantum error-correcting codes due to imperfect physical devices and operations. One would like to have an efficient and high-performance decoding procedure for the class of quantum stabilizer codes. A potential candidate is Gallager’s sum-product algorithm, also known as Pearl’s belief propagation (BP), but its performance suffers from the many short cycles inherent in a quantum stabilizer code, especially highly-degenerate codes. A general impression exists that BP is not effective for topological codes. In this paper, we propose a decoding algorithm for quantum codes based on quaternary BP with additional memory effects (called MBP). This MBP is like a recursive neural network with inhibitions between neurons (edges with negative weights), which enhance the perception capability of a network. Moreover, MBP exploits the degeneracy of a quantum code so that the most probable error or its degenerate errors can be found with high probability. The decoding performance is significantly improved over the conventional BP for various quantum codes, including quantum bicycle, hypergraph-product, surface and toric codes. For MBP on the surface and toric codes over depolarizing errors, we observe error thresholds of 16% and 17.5%, respectively.
Quantum low-density parity-check codes are promising candidates for low-overhead fault-tolerant quantum computing, but degeneracy is known to impair the convergence of belief-propagation (BP) decoding of these codes. In this work, we show that appending linearly independent rows to a check matrix of a stabilizer code can reduce the search space for a valid degenerate solution. Motivated by this, we extend the recently proposed affine subcode ensemble decoding technique from the classical to the quantum setting. Moreover, we employ overcomplete matrices for each decoding path. Monte-Carlo simulations on toric and generalized bicycle codes demonstrate improved convergence and reduced logical error rate.
Quantum low-density parity-check (QLDPC) codes have emerged as a promising technique for quantum error correction. A variety of decoders have been proposed for QLDPC codes and many utilize belief propagation (BP) decoding in some fashion. However, the use of BP decoding for degenerate QLDPC codes is known to have issues with convergence. These issues are typically attributed to short cycles in the Tanner graph and error patterns with the same syndrome due to code degeneracy. In this work, we propose a decoder for QLDPC codes based on BP guided decimation (BPGD), which has been previously studied for constraint satisfaction and lossy compression problems. This decimation process is applicable to both binary and quaternary BP and it involves sequentially freezing the value of the most reliable qubits to encourage BP convergence. We find that BPGD significantly reduces the BP failure rate due to non-convergence, achieving performance on par with BP with ordered statistics decoding and BP with stabilizer inactivation, without the need to solve systems of linear equations. To explore how and why BPGD improves performance, we discuss several interpretations of BPGD and their connection to BP syndrome decoding.
We study the performance of medium-length quantum LDPC (QLDPC) codes in the depolarizing channel. Only degenerate codes with the maximal stabilizer weight much smaller than their minimum distance are considered. It is shown that with the help of OSD-like post-processing the performance of the standard belief propagation (BP) decoder on many QLDPC codes can be improved by several orders of magnitude. Using this new BP-OSD decoder we study the performance of several known classes of degenerate QLDPC codes including hypergraph product codes, hyperbicycle codes, homological product codes, and Haah's cubic codes. We also construct several interesting examples of short generalized bicycle codes. Some of them have an additional property that their syndromes are protected by small BCH codes, which may be useful for the fault-tolerant syndrome measurement. We also propose a new large family of QLDPC codes that contains the class of hypergraph product codes, where one of the used parity-check matrices is square. It is shown that in some cases such codes have better performance than hypergraph product codes. Finally, we demonstrate that the performance of the proposed BP-OSD decoder for some of the constructed codes is better than for a relatively large surface code decoded by a near-optimal decoder.
Quantum low-density parity-check (LDPC) codes are a promising family of quantum error-correcting codes for fault tolerant quantum computing with low overhead. Decoding quantum LDPC codes on quantum erasure channels has received more attention recently due to advances in erasure conversion for various types of qubits including neutral atoms, trapped ions, and superconducting qubits. Belief propagation with guided decimation (BPGD) decoding of quantum LDPC codes has demonstrated good performance in bit-flip and depolarizing noise. In this work, we apply BPGD decoding to quantum erasure channels. Using a natural modification, we show that BPGD offers competitive performance on quantum erasure channels for multiple families of quantum LDPC codes. Furthermore, we show that the performance of BPGD decoding on erasure channels can sometimes be improved significantly by either adding damping or adjusting the initial channel log-likelihood ratio for bits that are not erased. More generally, our results demonstrate BPGD is an effective general-purpose solution for erasure decoding across the quantum LDPC landscape.
Due to code degeneracy and the graph structure of quantum low-density parity-check (QLDPC) codes, the performance of conventional belief propagation (BP) decoding can be poor. Recently, belief propagation guided decimation (BPGD) has shown promise to combat these challenges. In this paper, we investigate various decimation approaches to improve the error correcting performance and convergence speed of BPGD. We first consider soft decimation, where the BP equations are modified via several tuneable parameters. This approach exhibits linear complexity relative to the length of the block code and is shown to outperform hard decimation approaches for careful selection of the algorithm parameters. We then combine the approaches in a "soft-hard" BPGD variant, where hard decisions are periodically made and those symbols are permanently fixed throughout the remainder of the decoding process. Simulation results show that further performance improvement can be observed in this case at the cost of increasing the algorithmic complexity.