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• 6 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•2 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•15 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•22 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

Trimming Decoding of Color Codes over the Quantum Erasure Channel

Sangjun Lee, Mehdi Mhalla, Valentin Savin

We propose a decoding algorithm for color codes over the quantum erasure channel, which is linear-time maximum likelihood (ML) when the set of erased qubits satisfies a certain condition called trimmability. Two methods are proposed for general erasure sets, either by extending the erasure set to make it trimmable, or by inactivating some vertices. The former is linear time but not ML, while the latter is ML but not linear time. Numerical results are provided to assess the error correction performance and the complexity of both methods.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•8 citations

Efficient post-selection for general quantum LDPC Codes

Seok-Hyung Lee, Lucas English, Stephen D. Bartlett

Abstract Post-selection strategies that discard low-confidence results can significantly improve the effective fidelity of quantum computing at the cost of reduced acceptance rates, particularly useful for offline resource state generation and moderate-depth fault-tolerant circuits. Prior work has primarily relied on the “logical gap” metric, which faces fundamental limitations including computational overhead that scales exponentially with the number of logical qubits and poor generalizability beyond surface codes. We develop post-selection strategies based on computationally efficient heuristic metrics that leverage error cluster statistics from clustering-based decoders, which are applicable to arbitrary quantum low-density parity check (QLDPC) codes. We validate our method through extensive numerical simulations on surface codes, bivariate bicycle codes, and hypergraph product codes, demonstrating orders of magnitude reductions in logical error rates with moderate abort rates. For instance, applying our strategy to the [[144, 12, 12]] bivariate bicycle code achieves ~ 1000 × reduction in the logical error rate with an abort rate of only 1% at a physical error rate of 0.1%. Additionally, we integrate our approach with the sliding-window framework for real-time decoding, featuring mid-circuit abort decisions that eliminate unnecessary overheads. Notably, its performance matches or even surpasses the original strategy, while exhibiting favorable scaling in the number of rounds.

arXiv:2510.05795•npj Quantum Information•Apr 24, 2026•3 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.
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.
We propose a decoding algorithm for color codes over the quantum erasure channel, which is linear-time maximum likelihood (ML) when the set of erased qubits satisfies a certain condition called trimmability. Two methods are proposed for general erasure sets, either by extending the erasure set to make it trimmable, or by inactivating some vertices. The former is linear time but not ML, while the latter is ML but not linear time. Numerical results are provided to assess the error correction performance and the complexity of both methods.
Abstract Post-selection strategies that discard low-confidence results can significantly improve the effective fidelity of quantum computing at the cost of reduced acceptance rates, particularly useful for offline resource state generation and moderate-depth fault-tolerant circuits. Prior work has primarily relied on the “logical gap” metric, which faces fundamental limitations including computational overhead that scales exponentially with the number of logical qubits and poor generalizability beyond surface codes. We develop post-selection strategies based on computationally efficient heuristic metrics that leverage error cluster statistics from clustering-based decoders, which are applicable to arbitrary quantum low-density parity check (QLDPC) codes. We validate our method through extensive numerical simulations on surface codes, bivariate bicycle codes, and hypergraph product codes, demonstrating orders of magnitude reductions in logical error rates with moderate abort rates. For instance, applying our strategy to the [[144, 12, 12]] bivariate bicycle code achieves ~ 1000 × reduction in the logical error rate with an abort rate of only 1% at a physical error rate of 0.1%. Additionally, we integrate our approach with the sliding-window framework for real-time decoding, featuring mid-circuit abort decisions that eliminate unnecessary overheads. Notably, its performance matches or even surpasses the original strategy, while exhibiting favorable scaling in the number of rounds.