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:2504.21845 · IEEE International Symposium on Information Theory (ISIT)

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

Jefrin Sharmitha Prabhu, Abhinav Vaishya, Shobhit Bhatnagar, Aryaman Manish Kolhe, V. Lalitha, P. Vijay Kumar

Published Jun 22, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1109/isit63088.2025.11195550

Related papers

Linear-time erasure recovery for quantum expander codes

Anirudh Krishna, Christopher A. Pattison

Erasures are used to model faults at a subset of known locations in various platforms used to construct fault-tolerant quantum computers. Beyond the utility in erasure recovery, efficient decoders for erasures are useful to both understand error decoders and as a subroutine for error decoding. Classical expander codes, which belong to the family of low-density parity-check (LDPC) codes, can be equipped with the Peeling decoder which works in linear time. Our main result is the algorithm Small-Set-Peeling, a quantum generalization of the classical Peeling decoder for erasures, that applies to quantum expander codes (Tillich, Zémor, IEEE T-IT 2013; Leverrier, Tillich, Zémor, FOCS 2015). This decoder can correct up to $D-1$ erasures, where $D$ is the (design) distance of the code and, importantly, is the first decoder that is guaranteed to do so in linear time. Combining with the erasure-conversion algorithm Small-Set-Find (Krishna, Livni-Navon, Wootters, SODA 2024), our result also implies the existence of a novel graph-local linear-time decoder for Pauli errors.

arXiv:2611.06818•Nov 4, 2026•0 citations

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

Decoding Quasi-Cyclic Quantum LDPC Codes

Louis Golowich, Venkatesan Guruswami

Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.

arXiv:2411.04464•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•3 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•9 citations

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•109 citations

Almost-linear time decoding algorithm for topological codes

Nicolas Delfosse, Naomi Nickerson

In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O ( n α ( n ) ) , where n is the number of physical qubits and α is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α ( n ) ≤ 3 . We prove that our algorithm performs optimally for errors of weight up to ( d − 1 ) / 2 and for loss of up to d − 1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9 % for the 2d-toric code with perfect syndrome measurements and 2.6 % with faulty measurements.

arXiv:1709.06218•Quantum•Dec 2, 2021•337 citations
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.
Erasures are used to model faults at a subset of known locations in various platforms used to construct fault-tolerant quantum computers. Beyond the utility in erasure recovery, efficient decoders for erasures are useful to both understand error decoders and as a subroutine for error decoding. Classical expander codes, which belong to the family of low-density parity-check (LDPC) codes, can be equipped with the Peeling decoder which works in linear time. Our main result is the algorithm Small-Set-Peeling, a quantum generalization of the classical Peeling decoder for erasures, that applies to quantum expander codes (Tillich, Zémor, IEEE T-IT 2013; Leverrier, Tillich, Zémor, FOCS 2015). This decoder can correct up to D−1D-1D−1 erasures, where DDD is the (design) distance of the code and, importantly, is the first decoder that is guaranteed to do so in linear time. Combining with the erasure-conversion algorithm Small-Set-Find (Krishna, Livni-Navon, Wootters, SODA 2024), our result also implies the existence of a novel graph-local linear-time decoder for Pauli errors.
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.
Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.
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.
In order to build a large scale quantum computer, one must be able to correct errors extremely fast. We design a fast decoding algorithm for topological codes to correct for Pauli errors and erasure and combination of both errors and erasure. Our algorithm has a worst case complexity of O ( n α ( n ) ) , where n is the number of physical qubits and α is the inverse of Ackermann's function, which is very slowly growing. For all practical purposes, α ( n ) ≤ 3 . We prove that our algorithm performs optimally for errors of weight up to ( d − 1 ) / 2 and for loss of up to d − 1 qubits, where d is the minimum distance of the code. Numerically, we obtain a threshold of 9.9 % for the 2d-toric code with perfect syndrome measurements and 2.6 % with faulty measurements.