QI On PubPhys: open In the literature: partially resolved Compiled by AI, not yet reviewed by an editor

Provable qLDPC decoders whose proven thresholds match observed ones

50

No. 664 in all physics · No. 31 in Quantum Information and Foundations

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.

Non-expert version

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.

No solutions, ideas or subproblems yet.

How results are checked

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

Details, signature and history
Kind
Well-posed question
Answer
Proof
Topic review
N. P. Breuckmann and J. N. Eberhardt, Quantum Low-Density Parity-Check Codes, PRX Quantum, 2021. Link
Record
Revision 1 · imported from the seed collection · compiled by AI, not yet reviewed by an editor

Proof

Fingerprint
41736a5614f3…
Public log
Entry 2,023, in checkpoint 2,123
In the log by
Block 969,698, 2026-10-03

This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.

History