2023/11/01 by Lev Stambler, Stambler, Lev, Anirudh Krishna +3 · 1 citation
Computer Science · Mathematics · #Algorithm #Code (set theory) #Computer science #Decoding methods #Discrete mathematics #Error Correcting Code Techniques #Error detection and correction #FOS: Physical sciences #Hypergraph #Low-density parity-check code #Mathematics #Order (exchange) #Product (mathematics) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #Set (abstract data type)
paper · pdf · doi:10.48550/arxiv.2311.00877
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/11/01 · openalex created_date 2023/11/04 · openalex updated_date 2026/08/06
For a quantum error correcting code to be used in practice, it needs to be equipped with an efficient decoding algorithm, which identifies corrections given the observed syndrome of errors.Hypergraph product codes are a promising family of constant-rate quantum LDPC codes that have a linear-time decoding algorithm called Small-Set-Flip (SSF) (Leverrier, Tillich, Zémor FOCS 2015). The algorithm proceeds by iteratively applying small corrections which reduce the syndrome weight. Together, these small corrections can provably correct large errors for sufficiently large codes with sufficiently large (but constant) stabilizer weight. However, this guarantee does not hold for small codes with low stabilizer weight. In this case, SSF can terminate with stopping failures, meaning it encounters an error for which it is unable to identify a small correction. We find that the structure of errors that cause stopping failures have a simple form for sufficiently small qubit failure rates. We propose a new decoding algorithm called the Projection-Along-a-Line (PAL) decoder to supplement SSF after stopping failures. Using SSF+PAL as a combined decoder, we find an order-of-magnitude improvement in the logical error rate.