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:2412.08817 · IEEE Journal on Selected Areas in Information Theory

Cluster Decomposition for Improved Erasure Decoding of Quantum LDPC Codes

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

Published Jan 1, 2025• 9 citations
arXivHTMLPDF

Abstract

We introduce a new erasure decoder that applies to arbitrary quantum LDPC codes. Dubbed the cluster decoder, it generalizes the decomposition idea of Vertical-Horizontal (VH) decoding introduced by Connolly et al. in 2022. Like the VH decoder, the idea is to first run the peeling decoder and then post-process the resulting stopping set. The cluster decoder breaks the stopping set into a tree of clusters, which can be solved sequentially via Gaussian Elimination. By allowing clusters of unconstrained size, this decoder achieves maximum-likelihood (ML) performance with reduced complexity compared with full Gaussian Elimination. When Gaussian Elimination is applied only to clusters whose sizes are less than a constant, the performance is degraded, but the complexity becomes linear in the block length. Our simulation results show that, for hypergraph product codes, the cluster decoder with constant cluster size achieves near-ML performance similar to VH decoding in the low-erasure-rate regime. For the general quantum LDPC codes we studied, the cluster decoder can be used to estimate the ML performance curve with reduced complexity over a wide range of erasure rates.

DOI
10.1109/jsait.2025.3578597

Related papers

On the Efficacy of the Peeling Decoder for the Quantum Expander Code

Jefrin Sharmitha Prabhu, Abhinav Vaishya, Shobhit Bhatnagar +3 more

The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their errorcorrecting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.

arXiv:2504.21845•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation

On the Analysis of Stopping Sets Associated with the Quantum Hypergraph Product Code

Jefrin Sharmitha Prabhu, R. Gayathri, P. Vijay Kumar

The design of efficient quantum error-correcting codes that address qubit erasures is relevant, as these erasures occur in physical systems such as photonic, trapped-ion, and superconducting qubit systems. The focus here is on the performance of the Quantum Hypergraph Product (HGP) code when decoded with a low-complexity peeling decoder. As with classical LDPC codes, the performance of the peeling decoder is limited by the presence of stopping sets, so minimizing their number is important. The parity-check matrix of the HGP code is parameterized by the parity-check matrix H of a classical error-correcting code. Geometrically, the stopping sets of the HGP code can be classified as vertical, horizontal, or mixed, with the mixed type including stabilizer stopping sets. We derive tight upper and lower bounds on the probability of stabilizer stopping sets that are linked to the stabilizer generators, and establish a simple relationship with the variable and check node distributions in the Tanner graph associated with H. Additionally, we show how an earlier bound by Shokrollahi implies an upper bound on the probability of both horizontal and vertical stopping sets. Taken together, the bounds presented offer useful insights for selecting H to enhance peeling performance, and we present an illustrative example of such an application.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•0 citations

Fast erasure decoder for hypergraph product codes

Nicholas Connolly, Vivien Londe, Anthony Leverrier +1 more

We propose a decoder for the correction of erasures with hypergraph product codes, which form one of the most popular families of quantum LDPC codes. Our numerical simulations show that this decoder provides a close approximation of the maximum likelihood decoder that can be implemented in O ( N 2 ) bit operations where N is the length of the quantum code. A probabilistic version of this decoder can be implemented in O ( N 1.5 ) bit operations.

arXiv:2208.01002•Quantum•Aug 27, 2024•23 citations

Pivoting Algorithms for Maximum Likelihood Decoding of LDPC Codes over Erasure Channels

Gianluigi Liva, Balázs Matuz, Enrico Paolini +1 more

This paper investigates efficient maximum-likelihood (ML) decoding algorithms for low-density parity-check (LDPC) codes over erasure channels. In particular, enhancements to a previously proposed structured Gaussian elimination approach are presented. The improvements are achieved by developing a set of algorithms, here referred to as pivoting algorithms, aiming to limit the average number of reference variables (or pivots) from which the erased symbols can be recovered. Four pivoting algorithms are compared, which exhibit different trade-offs between the complexity of the pivoting phase and the average number of pivots. Numerical results on the performance of LDPC codes under ML erasure decoding complete the analysis, confirming that a near-optimum performance can be obtained with an affordable decoding complexity, up to very high data rates. For example, for one of the presented algorithms, a software implementation has been developed, which is capable to provide data rates above 1.5 Gbps on a commercial computing platform.

Globecom•Nov 1, 2009•21 citations

An Improved Decimation Technique for Erasure Decoding of Quantum LDPC Codes

R. Gayathri, Shobhit Bhatnagar, Abhinav Vaishya +1 more

Quantum low density parity-check (QLDPC) codes represent an attractive candidate for achieving fault-tolerant quantum computation. Erasure decoding of QLDPC codes has gained traction recently as many physical systems such as neutral-atom systems, photonic systems, trapped-ion systems etc. suffer from qubit erasures. Techniques for erasure decoding of QLDPC codes via belief propagation (BP) have been proposed in the literature, such as BP with guided decimation (BP-GD), where decimation refers to sequentially fixing hard values for the variable nodes. We provide an alternative decimation-based BP algorithm, which we term the BP with degree-based decimation (BP-DD) algorithm, that intelligently chooses a check node based on its degree and subsequently decimates a variable node in its neighborhood. We apply the BP-DD algorithm to two families of QLDPC codes, namely hypergraph product codes and lifted product codes, and show improved logical error performance over the BP-GD algorithm, without incurring additional complexity. Our simulations show that the BP-DD algorithm provides a versatile solution for erasure decoding of QLDPC codes, in contrast to some techniques in the literature that are applicable to only specific classes of QLDPC codes.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•2 citations

Improved Stopping Set Elimination by Parity-Check Matrix Extension of LDPC Codes

Saejoon Kim, Jun Heo, Hyuncheol Park

Stopping sets associated with a parity-check matrix of low-density parity-check codes limit the performance of iterative decoding over the binary erasure channel. In this letter, we propose a parity-check matrix extension scheme that eliminates stopping sets of small sizes. The results show that our proposed scheme provides significant performance improvement compared to previously known parity-check matrix extension schemes.

IEEE Communications Letters•Apr 6, 2011•6 citations
We introduce a new erasure decoder that applies to arbitrary quantum LDPC codes. Dubbed the cluster decoder, it generalizes the decomposition idea of Vertical-Horizontal (VH) decoding introduced by Connolly et al. in 2022. Like the VH decoder, the idea is to first run the peeling decoder and then post-process the resulting stopping set. The cluster decoder breaks the stopping set into a tree of clusters, which can be solved sequentially via Gaussian Elimination. By allowing clusters of unconstrained size, this decoder achieves maximum-likelihood (ML) performance with reduced complexity compared with full Gaussian Elimination. When Gaussian Elimination is applied only to clusters whose sizes are less than a constant, the performance is degraded, but the complexity becomes linear in the block length. Our simulation results show that, for hypergraph product codes, the cluster decoder with constant cluster size achieves near-ML performance similar to VH decoding in the low-erasure-rate regime. For the general quantum LDPC codes we studied, the cluster decoder can be used to estimate the ML performance curve with reduced complexity over a wide range of erasure rates.
The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their errorcorrecting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.
The design of efficient quantum error-correcting codes that address qubit erasures is relevant, as these erasures occur in physical systems such as photonic, trapped-ion, and superconducting qubit systems. The focus here is on the performance of the Quantum Hypergraph Product (HGP) code when decoded with a low-complexity peeling decoder. As with classical LDPC codes, the performance of the peeling decoder is limited by the presence of stopping sets, so minimizing their number is important. The parity-check matrix of the HGP code is parameterized by the parity-check matrix H of a classical error-correcting code. Geometrically, the stopping sets of the HGP code can be classified as vertical, horizontal, or mixed, with the mixed type including stabilizer stopping sets. We derive tight upper and lower bounds on the probability of stabilizer stopping sets that are linked to the stabilizer generators, and establish a simple relationship with the variable and check node distributions in the Tanner graph associated with H. Additionally, we show how an earlier bound by Shokrollahi implies an upper bound on the probability of both horizontal and vertical stopping sets. Taken together, the bounds presented offer useful insights for selecting H to enhance peeling performance, and we present an illustrative example of such an application.
This paper investigates efficient maximum-likelihood (ML) decoding algorithms for low-density parity-check (LDPC) codes over erasure channels. In particular, enhancements to a previously proposed structured Gaussian elimination approach are presented. The improvements are achieved by developing a set of algorithms, here referred to as pivoting algorithms, aiming to limit the average number of reference variables (or pivots) from which the erased symbols can be recovered. Four pivoting algorithms are compared, which exhibit different trade-offs between the complexity of the pivoting phase and the average number of pivots. Numerical results on the performance of LDPC codes under ML erasure decoding complete the analysis, confirming that a near-optimum performance can be obtained with an affordable decoding complexity, up to very high data rates. For example, for one of the presented algorithms, a software implementation has been developed, which is capable to provide data rates above 1.5 Gbps on a commercial computing platform.
Quantum low density parity-check (QLDPC) codes represent an attractive candidate for achieving fault-tolerant quantum computation. Erasure decoding of QLDPC codes has gained traction recently as many physical systems such as neutral-atom systems, photonic systems, trapped-ion systems etc. suffer from qubit erasures. Techniques for erasure decoding of QLDPC codes via belief propagation (BP) have been proposed in the literature, such as BP with guided decimation (BP-GD), where decimation refers to sequentially fixing hard values for the variable nodes. We provide an alternative decimation-based BP algorithm, which we term the BP with degree-based decimation (BP-DD) algorithm, that intelligently chooses a check node based on its degree and subsequently decimates a variable node in its neighborhood. We apply the BP-DD algorithm to two families of QLDPC codes, namely hypergraph product codes and lifted product codes, and show improved logical error performance over the BP-GD algorithm, without incurring additional complexity. Our simulations show that the BP-DD algorithm provides a versatile solution for erasure decoding of QLDPC codes, in contrast to some techniques in the literature that are applicable to only specific classes of QLDPC codes.