Provable qLDPC decoders whose proven thresholds match observed ones
This text mentions work from 2024 on. Those parts were partly written without a live literature search and have not been checked by an editor yet.
In plain words
Error correction needs a classical computer to read the check results and decide what went wrong before new errors pile up. For these codes, decoders with mathematical guarantees exist, but the noise levels they are proven to handle are far below what they handle in practice, and the decoders used in practice have no guarantees.
Precise statement
For a constant-rate qLDPC family (quantum Tanner codes, bivariate bicycle codes or similar) under circuit-level depolarizing noise of rate p, prove a threshold for a decoder running in time O(n polylog n) per round whose proven threshold is within a constant factor (say 10) of its numerically observed one, or prove a circuit-level threshold for belief propagation with ordered-statistics or localized-statistics post-processing. Thresholds with linear-time decoders are already proved for quantum expander codes (Fawzi, Grospellier and Leverrier, FOCS 2018, arXiv:1808.03821) and single-shot decoding for quantum Tanner codes (Gu et al., arXiv:2306.12470), but the proven threshold values are far below the observed ones.
What would settle it
A decoder with a proved circuit-level threshold within a constant factor of its observed threshold and near-linear running time, for a constant-rate qLDPC family.
Status in the literature
Provable circuit-level thresholds exist since 2018 (expander codes) and 2023 (quantum Tanner codes, single-shot); the proven values are orders of magnitude below the numerical ones.
Results
No results have been posted on this problem yet.
Post a result · how results are checked
Sign in to follow or save this problem
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.