arXiv preprint ·
Linear-time erasure recovery for quantum expander codes
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Hotplug Coded Caching: Embedding the YMA and Interference Elimination Schemes via Reed--Muller Codes
Graph Neural Networks for Resource Allocation in Integrated Sensing and Communication
Functional inequalities from the fundamental limits of Bayesian estimation
Functional Converses for Private Matrix-Product Retrieval under Library-Wide Decoder-Side Correlation
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.