Efficient decoding of random errors for quantum expander codes

DOI10.1145/3188745.3188886MaRDI QIDQ5230316zbMATH OpenOpenAlexWikidataFDO

Authors Omar Fawzi, Antoine Grospellier, Anthony Leverrier

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.08351

zbMATH Keywords

percolationquantum error correctiondecoding algorithmexpander codes

Mathematics Subject Classification ID

Quantum coding (general) (81P70) Decoding (94B35)

Abstract: We show that quantum expander codes, a constant-rate family of quantum LDPC codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Z'emor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman's construction of fault tolerant schemes with constant space overhead. In order to obtain this result, we study a notion of $alpha$-percolation: for a random subset $W$ of vertices of a given graph, we consider the size of the largest connected $alpha$-subset of $W$, where $X$ is an $alpha$-subset of $W$ if $|XcapW|geqalpha|X|$.

Recommendations

• Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders
• On expander codes
• Linear-time decoding of regular expander codes
• Expander codes
• Local correctability of expander codes

Cited in

(11)

• Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders
• Fault-tolerant conversion between adjacent Reed–Muller quantum codes based on gauge fixing
• Towards local testability for quantum coding
• Bitwise Quantum Min-Entropy Sampling and New Lower Bounds for Random Access Codes
• Fast decoders for qudit topological codes
• Improved quantum information set decoding
• Robust quantum entanglement at (nearly) room temperature
• Approximate Bacon-Shor code and holography
• [[:Publication:1955881|Efficient quantum circuit for encoding and decoding of the 8,3,5 stabilizer code]]
• Expanding the sharpness parameter area based on sequential \(3 \rightarrow 1\) parity-oblivious quantum random access code
• Single-shot decoding of good quantum LDPC codes

This page was built for publication: Efficient decoding of random errors for quantum expander codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230316)