Decision-tree decoders for general quantum LDPC codes
Open accessAbstract
We introduce Decision Tree Decoders (DTDs), which rely only on the sparsity of the binary check matrix, making them broadly applicable for decoding any quantum low-density parity-check (qLDPC) code and fault-tolerant quantum circuits. DTDs construct corrections incrementally by adding faults one-by-one, forming a path through a Decision Tree (DT). Each DTD algorithm is defined by its strategy for exploring the tree, with well-designed algorithms typically needing to explore only a small portion before finding a correction. We propose two explicit DTD algorithms that can be applied to any qLDPC code: (1) A provable decoder: Guaranteed to find a minimum-weight correction. While it can be slow in the worst case, numerical results show surprisingly fast median-case runtime, exploring only $w$ DT nodes to find a correction for weight-$w$ errors in notable qLDPC codes, such as bivariate bicycle and color codes. This decoder may be useful for ensemble decoding and determining provable code distances, and can be adapted to compute all minimum-weight logical operators of a code. (2) A heuristic decoder: Achieves higher accuracy and faster performance than BP-OSD on the gross code with circuit noise in realistic parameter regimes.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For more general detector-model decoding beyond graph-like settings, recent works have proposed the decision-tree decoder and the closely related Tesseract decoder for QEC codes.
“For more general detector-model decoding beyond graph-like settings, recent works have proposed the decision-tree decoder [207] and the closely related Tesseract decoder for QEC codes [208].”
From Quantum error correction and fault tolerance: A comprehensive tutorial (2026) · cites this paper as [207]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 12
- [BCG + 23] Sergey Bravyi, Andrew W. Cross, Jay M. Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J. Yoder. High-threshold and low-overhead fault-tolerant quantum memory. arXiv version , 2023.
- [BCG + 24] Sergey Bravyi, Andrew W Cross, Jay M Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature , 627(8005):778-782, 2024.
- [BE21] Nikolas P Breuckmann and Jens Niklas Eberhardt. Quantum low-density parity-check codes. PRX Quantum , 2(4):040101, 2021.
- [BFHS17] Dave Bacon, Steven T Flammia, Aram W Harrow, and Jonathan Shi. Sparse quantum codes from quantum circuits. IEEE Transactions on Information Theory , 63(4):24642479, 2017.
- [BHK24] Michael E Beverland, Shilin Huang, and Vadym Kliuchnikov. Fault tolerance of stabilizer channels. arXiv preprint arXiv:2401.12017 , 2024. · arXiv
- [BMD06] Hector Bombin and Miguel Angel Martin-Delgado. Topological quantum distillation. Physical Review Letters , 97(18):180501, 2006.
- [BMT + 22] Michael E Beverland, Prakash Murali, Matthias Troyer, Krysta M Svore, Torsten Hoefler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo. Assessing requirements to scale to practical quantum advantage. arXiv preprint arXiv:2211.07629 , 2022. · arXiv
- [BSH + 23] Johannes Bausch, Andrew W Senior, Francisco JH Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin Satzinger, Murphy Yuezhen Niu, Sam Blackwell, et al. Learning to decode the surface code with a recurrent, transformer-based neural network. arXiv preprint arXiv:2310.05900 , 2023. · arXiv
- [Del14] Nicolas Delfosse. Decoding color codes by projection onto surface codes. Physical Review A-Atomic, Molecular, and Optical Physics , 89(1):012317, 2014.
- [Ste96] Andrew Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society A , 452(1954):2551-2577, 1996.
- [TV15] Ido Tal and Alexander Vardy. List decoding of polar codes. IEEE transactions on information theory , 61(5):2213-2226, 2015.
- [WB24] Stasiu Wolanski and Ben Barber. Introducing ambiguity clustering: an accurate and efficient decoder for qldpc codes. In 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) , volume 2, pages 402-403. IEEE, 2024.
Cited by
Sorted by citations
Quantum error correction and fault tolerance: A comprehensive tutorial
Spencer, D. J., Jain, S. P., Tanggara, A., Sun, Z., Haug, T., Khu, D., & Bharti, K. (2026) · arXiv
- Authors
- Ott, K. R., Hetényi, B., & Beverland, M. E.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2025
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2502.16408
- OpenAlex
- W4414841076
- Cited by
- 0
- References
- 0
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Keywords
- quantum LDPC codes, quantum error correction, fault-tolerant quantum circuits, bivariate bicycle codes, color codes, ensemble decoding, code distance, logical connectives
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
