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

IEEE International Symposium on Information Theory (ISIT)

Trimming Decoding of Color Codes over the Quantum Erasure Channel

Sangjun Lee, Mehdi Mhalla, Valentin Savin

Published Jun 1, 2020• 8 citations
Publisher

Abstract

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.

DOI
10.1109/isit44484.2020.9174084

Related papers

Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel

Nicolas Delfosse, Gilles Zémor

This paper presents a decoding algorithm for the correction of erasure or qubit loss using surface codes. The peeling decoder identifies an optimal correction and it can be implemented in linear time. It corrects up to 50% of qubit loss.

arXiv:1703.01517•Physical Review Research•Jul 9, 2020•89 citations

Quantum Maxwell Erasure Decoder for qLDPC codes

Bruno Costa Alves Freire, François-Marie Le Régent, Anthony Leverrier

We introduce a quantum Maxwell erasure decoder for CSS quantum low-density parity-check (qLDPC) codes that extends peeling with bounded guessing. Guesses are tracked symbolically and can be eliminated by restrictive checks, giving a tunable tradeoff between complexity and performance via a guessing budget: an unconstrained budget recovers Maximum-Likelihood (ML) performance, while a constant budget yields linear-time decoding and approximates ML. We provide theoretical guarantees on asymptotic performance and demonstrate strong performance on bivariate bicycle and quantum Tanner codes.

quant-pharXiv:2601.10713•IEEE International Symposium on Information Theory (ISIT)•Jan 16, 2026•2 citations

Erasure decoding of two-dimensional color codes

Arun B. Aloshious, Pradeep Kiran Sarvepalli

The quantum erasure channel models phenomena such as loss or leakage of qubits. Using quantum codes, we can recover from such errors. In this paper, we are interested in studying the performance of two-dimensional color codes over the quantum erasure channel. Our approach makes use of the local equivalence between color codes and surface codes. We propose a variety of decoding algorithms for color codes over the erasure channel. First, we propose algorithms that decode by projecting the erasures on the color to surface codes. Then, instead of directly decoding on the color code or on the equivalent copies of surface codes, we decode jointly on the color code and the equivalent surface codes. We observe a threshold of 44.3% for the color code on the square octagonal lattice.

Physical Review A•Oct 14, 2019•6 citations

Stabilizer-Assisted Inactivation Decoding of Quantum Error-Correcting Codes with Erasures

Giulio Pech, Mert Gökduman, Hanwen Yao +1 more

In this work, we develop a reduced complexity maximum likelihood (ML) decoder for quantum low-density parity-check (QLDPC) codes over erasures. Our decoder combines classical inactivation decoding, which integrates peeling with symbolic guessing, with a new dual peeling procedure. In the dual peeling stage, we perform row operations on the stabilizer matrix to efficiently reveal stabilizer generators and their linear combinations whose support lies entirely on the erased set. Each such stabilizer identified allows us to freely fix a bit in its support without affecting the logical state of the decoded result. This removes one degree of freedom that would otherwise require a symbolic guess, reducing the number of inactivated variables and decreasing the size of the final linear system that must be solved. We further show that dual peeling combined with standard peeling alone, without inactivation, is sufficient to achieve ML for erasure decoding of surface codes. Simulations across several QLDPC code families confirm that our decoder matches ML logical failure performance while significantly reducing the complexity of inactivation decoding, including more than a 20% reduction in symbolic guesses for the B1 lifted product code at high erasure rates.

arXiv:2601.14236•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2026•1 citation

An Efficient Maximum-Likelihood Decoding of LDPC Codes Over the Binary Erasure Channel

David Burshtein, G. Miller

We propose an efficient maximum-likelihood (ML) decoding algorithm for decoding low-density parity-check (LDPC) codes over the binary-erasure channel (BEC). We also analyze the computational complexity of the proposed algorithm.

IEEE Transactions on Information Theory•Oct 26, 2004•97 citations

Cluster Decomposition for Improved Erasure Decoding of Quantum LDPC Codes

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

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.

arXiv:2412.08817•IEEE Journal on Selected Areas in Information Theory•Jan 1, 2025•6 citations
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.
We introduce a quantum Maxwell erasure decoder for CSS quantum low-density parity-check (qLDPC) codes that extends peeling with bounded guessing. Guesses are tracked symbolically and can be eliminated by restrictive checks, giving a tunable tradeoff between complexity and performance via a guessing budget: an unconstrained budget recovers Maximum-Likelihood (ML) performance, while a constant budget yields linear-time decoding and approximates ML. We provide theoretical guarantees on asymptotic performance and demonstrate strong performance on bivariate bicycle and quantum Tanner codes.
The quantum erasure channel models phenomena such as loss or leakage of qubits. Using quantum codes, we can recover from such errors. In this paper, we are interested in studying the performance of two-dimensional color codes over the quantum erasure channel. Our approach makes use of the local equivalence between color codes and surface codes. We propose a variety of decoding algorithms for color codes over the erasure channel. First, we propose algorithms that decode by projecting the erasures on the color to surface codes. Then, instead of directly decoding on the color code or on the equivalent copies of surface codes, we decode jointly on the color code and the equivalent surface codes. We observe a threshold of 44.3% for the color code on the square octagonal lattice.
In this work, we develop a reduced complexity maximum likelihood (ML) decoder for quantum low-density parity-check (QLDPC) codes over erasures. Our decoder combines classical inactivation decoding, which integrates peeling with symbolic guessing, with a new dual peeling procedure. In the dual peeling stage, we perform row operations on the stabilizer matrix to efficiently reveal stabilizer generators and their linear combinations whose support lies entirely on the erased set. Each such stabilizer identified allows us to freely fix a bit in its support without affecting the logical state of the decoded result. This removes one degree of freedom that would otherwise require a symbolic guess, reducing the number of inactivated variables and decreasing the size of the final linear system that must be solved. We further show that dual peeling combined with standard peeling alone, without inactivation, is sufficient to achieve ML for erasure decoding of surface codes. Simulations across several QLDPC code families confirm that our decoder matches ML logical failure performance while significantly reducing the complexity of inactivation decoding, including more than a 20% reduction in symbolic guesses for the B1 lifted product code at high erasure rates.
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.