pith. sign in

arxiv: 2606.20513 · v1 · pith:SBIQ3SF4new · submitted 2026-06-18 · 🪐 quant-ph · cs.IT· math.IT

Approximating optimal decoding of quantum LDPC codes with narrow frontiers

Anthony Leverrier , R\"udiger Urbanke This is my paper

Pith reviewed 2026-06-26 16:39 UTC · model grok-4.3

classification 🪐 quant-ph cs.ITmath.IT
keywords Frontier decoderquantum LDPC codesdynamic programming decodingapproximate decodingsurface codecolor codecircuit-level noise
0
0 comments X

The pith

A pruned dynamic-programming decoder approximates optimal decoding of quantum LDPC codes by retaining a narrow scored frontier of prefixes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Frontier decoder, which processes error variables sequentially, merges prefixes that share the same residual syndrome and logical label, and approximates logical-coset posterior masses by keeping only a narrow set of top-scored prefixes. Without pruning the recursion is exact but exponential; with pruning the method runs in linear time for constant frontier size. In the code-capacity setting the resulting decoder reaches thresholds close to optimal for the surface code and the color code. Under circuit-level noise it matches state-of-the-art performance on the gross code while retaining an average frontier of fewer than 100 entries at physical error rate 0.001.

Core claim

The Frontier decoder approximates the exact ordered inference recursion for logical-coset posteriors by keeping only a narrow scored frontier of merged prefixes, achieving near-optimal decoding performance on quantum LDPC codes with substantially reduced complexity.

What carries the argument

The Frontier decoder: a dynamic-programming procedure that merges prefixes sharing residual syndrome and logical label, scores the merged states, and retains only a narrow frontier to approximate posterior masses.

If this is right

  • In the code-capacity setting the decoder reaches thresholds close to optimal for the surface code and the color code.
  • In the circuit-level noise model it achieves state-of-the-art performance with an average retained list size less than 100 for the gross code [[144,12,12]] at physical error rate 0.001.
  • When the list size is held constant the decoder has linear complexity.
  • The approach suggests the possibility of low-latency implementations for sparse quantum codes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same pruning idea could be tested on classical LDPC decoding problems where exact inference is also intractable.
  • Constant-size frontiers may enable memory-constrained hardware realizations of near-ML decoders.
  • Performance on additional families of quantum LDPC codes would clarify how broadly the narrow-frontier approximation holds.

Load-bearing premise

Retaining only a narrow scored frontier of prefixes is sufficient to approximate the logical-coset posterior masses without materially degrading decoding accuracy.

What would settle it

Run both the Frontier decoder and an exact maximum-likelihood decoder on a small quantum code where exact computation is feasible and check whether their logical error rates agree within statistical uncertainty.

Figures

Figures reproduced from arXiv: 2606.20513 by Anthony Leverrier, R\"udiger Urbanke.

Figure 1
Figure 1. Figure 1: Standard surface-code factor model and its ordered-matrix representation. Left: one CSS side of a small [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: One transition of the pruned ordered-frontier recursion on a BB code [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Rotated-surface code-capacity depolarizing-noise behavior for correlated Pauli [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Hexagonal color-code code-capacity bit-flip benchmark for [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Rotated-surface memory-Z memory experiment with d syndrome extraction rounds and p = 0.002: logical FER per round versus code distance for Frontier and correlated minimum-weight perfect matching [6, 7, 41]. The decoder settings are ∆ = 10, K = 1024 for d = 5, 7, 9 and ∆ = 12, K = 2048 for d = 11. Blue point labels report the estimated average retained frontier size R¯ = 1 n Pn−1 t=0 |Ft|, averaged over sam… view at source ↗
Figure 6
Figure 6. Figure 6: BB circuit-level benchmarks. Top: BB code [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Comparison between the peak frontier size and [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: Failure decomposition of Frontier for the gross code, under depolarizing circuit-level noise with p = 0.002. The cap is fixed to K = 214 for ∆ ≤ 12 and K = 214 for ∆ = 15. Failures are classified into “no path” corresponding to shots where the terminal frontier is empty (no error with the correct syndrome was found); “truth missing” when the terminal list does not contain the true error; and “bad ranking” … view at source ↗
read the original abstract

We introduce the Frontier decoder, a pruned dynamic-programming decoder for sparse quantum decoding problems. Frontier processes error variables in a chosen order, merges prefixes with the same residual syndrome and logical label, and approximates logical-coset posterior masses by retaining only a narrow scored frontier. Without pruning, the recursion is exact ordered inference with exponential complexity. In the code-capacity setting, the decoder reaches thresholds close to optimal for the surface code and the color code. In the circuit-level noise model, it achieves state-of-the-art performance with a very small average retained list size: less than 100 for the gross code $[[144,12,12]]$ at a physical error rate of $0.001$. When the list size is constant, the decoder has linear complexity, suggesting the possibility of low-latency implementations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript introduces the Frontier decoder, a pruned dynamic-programming decoder for sparse quantum decoding problems. It processes error variables in a chosen order, merges prefixes with the same residual syndrome and logical label, and approximates logical-coset posterior masses by retaining only a narrow scored frontier. Without pruning, the recursion is exact ordered inference with exponential complexity. In the code-capacity setting, the decoder reaches thresholds close to optimal for the surface code and the color code. In the circuit-level noise model, it achieves state-of-the-art performance with a very small average retained list size: less than 100 for the gross code [[144,12,12]] at a physical error rate of 0.001. When the list size is constant, the decoder has linear complexity, suggesting the possibility of low-latency implementations.

Significance. If the empirical results hold, this provides a practical approximation to optimal decoding for quantum LDPC codes that could support low-latency implementations in fault-tolerant quantum computing. The work is credited for its direct empirical validation on standard codes (surface code, color code, gross code) together with explicit measurements of average retained list sizes that address the pruning-sufficiency assumption.

major comments (2)
  1. [Abstract] Abstract: The performance numbers (near-optimal thresholds, SOTA circuit-level results, list size <100 at p=0.001) are reported without any details on measurement methodology, baseline comparisons, error-bar handling, or data-selection rules. This information is required to substantiate the central empirical claims.
  2. [Decoder construction and complexity claims (likely §2–3)] Decoder construction and complexity claims (likely §2–3): The statement that constant list size yields linear complexity is load-bearing for the low-latency suggestion, but the precise dependence of runtime on frontier size and the merging step should be derived explicitly to confirm the scaling.
minor comments (1)
  1. [Abstract] The abstract would be clearer if it briefly named the baselines used for the 'state-of-the-art' claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's thorough review and constructive feedback on our manuscript. Below we provide point-by-point responses to the major comments, outlining the revisions we intend to implement.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The performance numbers (near-optimal thresholds, SOTA circuit-level results, list size <100 at p=0.001) are reported without any details on measurement methodology, baseline comparisons, error-bar handling, or data-selection rules. This information is required to substantiate the central empirical claims.

    Authors: We agree with the referee that the abstract would be strengthened by including references to the methodology. In the revised version, we will modify the abstract to briefly mention that the reported thresholds and performance metrics are obtained via Monte Carlo simulations with details provided in Section 4, including comparisons to belief propagation and minimum-weight perfect matching decoders, as well as the use of 10^6 samples per data point for error bar estimation. This will substantiate the claims without significantly lengthening the abstract. revision: yes

  2. Referee: [Decoder construction and complexity claims (likely §2–3)] Decoder construction and complexity claims (likely §2–3): The statement that constant list size yields linear complexity is load-bearing for the low-latency suggestion, but the precise dependence of runtime on frontier size and the merging step should be derived explicitly to confirm the scaling.

    Authors: We concur that an explicit derivation is necessary. We will add a new subsection in Section 3 deriving the time complexity as O(N * K * C), where N is the number of error variables, K is the maximum frontier size, and C is the cost of the merging operation per prefix. When K is held constant, this reduces to linear scaling in N, supporting the low-latency claim. We will also discuss the practical merging implementation using hash maps for the syndrome and logical labels. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript introduces the Frontier decoder as an explicit algorithmic construction (ordered inference with pruning of a scored frontier) whose correctness and performance are assessed via direct simulation on fixed, externally defined codes (surface, color, gross [[144,12,12]]). Reported thresholds and list sizes are measured outcomes of that algorithm under standard noise models; they are not obtained by fitting parameters inside the paper and then relabeling the fit as a prediction, nor do any equations reduce the claimed approximation quality to a self-referential definition. No load-bearing self-citation, uniqueness theorem, or ansatz smuggling appears in the derivation chain. The central empirical claim therefore remains independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities are stated in the provided text.

pith-pipeline@v0.9.1-grok · 5667 in / 1111 out tokens · 47765 ms · 2026-06-26T16:39:31.537675+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 11 linked inside Pith

  1. [1]

    Topological quan- tum memory

    Eric Dennis, Alexei Kitaev, Andrew Lan- dahl, and John Preskill. “Topological quan- tum memory”. Journal of Mathematical Physics 43, 4452–4505 (2002). arXiv:quant- ph/0110143

    arXiv 2002

  2. [2]

    Paths, trees, and flowers

    Jack Edmonds. “Paths, trees, and flowers”. Canadian Journal of Mathematics17, 449– 467 (1965)

    1965

  3. [3]

    Surface codes: Towards practical large-scale quantum computation

    Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. “Surface codes: Towards practical large-scale quantum computation”. Physical Review A 86, 032324 (2012). arXiv:1208.0928

    Pith/arXiv arXiv 2012

  4. [4]

    Almost-linear time decoding algorithm for topological codes

    Nicolas Delfosse and Naomi H. Nickerson. “Almost-linear time decoding algorithm for topological codes”. Quantum5, 595 (2021). arXiv:1709.06218

    arXiv 2021

  5. [5]

    Efficient algorithms for max- imum likelihood decoding in the surface code

    Sergey Bravyi, Martin Suchara, and Alexan- der Vargo. “Efficient algorithms for max- imum likelihood decoding in the surface code”. Physical Review A90, 032326 (2014). arXiv:1405.4883

    Pith/arXiv arXiv 2014

  6. [6]

    PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching

    Oscar Higgott. “PyMatching: A Python package for decoding quantum codes with minimum-weight perfect matching”. ACM Transactions on Quantum Computing 3, 16:1–16:16 (2022). arXiv:2105.13082

    arXiv 2022

  7. [7]

    Sparse Blossom: correcting a million errors per core second with minimum-weight matching

    Oscar Higgott and Craig Gidney. “Sparse Blossom: correcting a million errors per core second with minimum-weight matching”. Quantum9, 1600 (2025). arXiv:2303.15933

    arXiv 2025

  8. [8]

    Sparse-graph codes for quantum error correction

    DavidJ.C.MacKay, GraemeMitchison, and Paul L. McFadden. “Sparse-graph codes for quantum error correction”. IEEE Trans- actions on Information Theory 50, 2315– 2330 (2004). arXiv:quant-ph/0304161

    Pith/arXiv arXiv 2004

  9. [9]

    Quan- tum LDPC codes with positive rate and min- imum distance proportional to the square root of the blocklength

    Jean-Pierre Tillich and Gilles Zémor. “Quan- tum LDPC codes with positive rate and min- imum distance proportional to the square root of the blocklength”. IEEE Trans- actions on Information Theory 60, 1193– 1202 (2014). arXiv:0903.0566

    Pith/arXiv arXiv 2014

  10. [10]

    Quantum low-density parity-check codes

    Nikolas P. Breuckmann and Jens N. Eber- hardt. “Quantum low-density parity-check codes”. PRX Quantum 2, 040101 (2021). arXiv:2103.06309

    arXiv 2021

  11. [11]

    Asymp- totically good quantum and locally testable classical LDPC codes

    PavelPanteleevandGlebKalachev. “Asymp- totically good quantum and locally testable classical LDPC codes”. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 375–388. (2022). arXiv:2111.03654

    arXiv 2022

  12. [12]

    Quan- tum Tanner codes

    Anthony Leverrier and Gilles Zémor. “Quan- tum Tanner codes”. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science. Pages 872–883. (2022). arXiv:2202.13641

    arXiv 2022

  13. [13]

    High-threshold and low-overhead fault-tolerant quantum memory

    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, 778–782 (2024). arXiv:2308.07915

    arXiv 2024

  14. [14]

    Decoding across the quantum low-density parity-check code landscape

    Joschka Roffe, David R. White, Simon Bur- ton, and Earl T. Campbell. “Decoding across the quantum low-density parity-check code landscape”. Physical Review Research 2, 043423 (2020). arXiv:2005.07016

    arXiv 2020

  15. [15]

    Localized statistics decoding 13 for quantum low-density parity-check codes

    Timo Hillmann, Lucas Berent, Armanda O. Quintavalle, Jens Eisert, Robert Wille, and Joschka Roffe. “Localized statistics decoding 13 for quantum low-density parity-check codes”. Nature Communications 16, 8214 (2025). arXiv:2406.18655

    arXiv 2025

  16. [16]

    An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

    Antonio deMarti iOlius, Imanol Etx- ezarreta Martinez, Joschka Roffe, and Josu Etxezarreta Martinez. “An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise”. npj Quan- tum Information (2026). arXiv:2409.01440

    arXiv 2026

  17. [17]

    Belief propagation decod- ing of quantum ldpc codes with guided deci- mation

    Hanwen Yao, Waleed Abu Laban, Chris- tian Häger, Alexandre Graell i Amat, and Henry D. Pfister. “Belief propagation decod- ing of quantum ldpc codes with guided deci- mation”. In 2024 IEEE International Sympo- sium on Information Theory (ISIT). Pages 2478–2483. (2024)

    2024

  18. [18]

    Toward low-latency itera- tive decoding of QLDPC codes under circuit- level noise

    Anqi Gong, Sebastian Cammerer, and Joseph M. Renes. “Toward low-latency itera- tive decoding of QLDPC codes under circuit- level noise” (2024). arXiv:2403.18901

    arXiv 2024

  19. [19]

    The closed-branch de- coder for quantum LDPC codes

    Antonio deMarti iOlius and Josu Etx- ezarreta Martinez. “The closed-branch de- coder for quantum LDPC codes” (2024). arXiv:2402.01532

    arXiv 2024

  20. [20]

    Beam search decoder for quantum LDPC codes

    Min Ye, Dave Wecker, and Nicolas Delfosse. “Beam search decoder for quantum LDPC codes” (2025). arXiv:2512.07057. code: ionq- publications/BeamSearchDecoder com- mit:084a475

    arXiv 2025

  21. [21]

    Improved belief propagation is sufficient for real-time decoding of quantum memory

    Tristan Müller, Thomas Alexander, Michael E. Beverland, Markus Bühler, Blake R. Johnson, Thilo Maurer, and Drew Vandeth. “Improved belief propagation is sufficient for real-time decoding of quantum memory” (2025). arXiv:2506.01779

    arXiv 2025

  22. [22]

    Au- tomorphism ensemble decoding of quantum LDPC codes

    Stergios Koutsioumpas, Hasan Sayginel, Mark Webster, and Dan E. Browne. “Au- tomorphism ensemble decoding of quantum LDPC codes” (2025). arXiv:2503.01738

    arXiv 2025

  23. [23]

    Decoding correlated errors in quantum LDPC codes

    Arshpreet Singh Maan, Francisco Miguel Garcia Herrero, Alexandru Paler, and Valentin Savin. “Decoding correlated errors in quantum LDPC codes”. Nature Commu- nications 17, 3965 (2026). arXiv:2510.14060

    arXiv 2026

  24. [24]

    Tesseract: a search-based decoder for quantum error correction

    Laleh Aghababaie Beni, Oscar Hig- gott, and Noah Shutty. “Tesseract: a search-based decoder for quantum error correction” (2025). arXiv:2503.10988. code: quantumlib/tesseract-decoder v0.1.1.dev20260508215356 commit:06a20c3

    arXiv 2025

  25. [25]

    Decision-tree decoders for general quantum LDPC codes

    Kai R. Ott, Bence Hetényi, and Michael E. Beverland. “Decision-tree decoders for general quantum LDPC codes” (2025). arXiv:2502.16408

    arXiv 2025

  26. [26]

    Learning high-accuracy er- ror decoding for quantum processors

    Johannes Bausch, Andrew W. Senior, Fran- cisco J. H. Heras, Thomas Edlich, Alex Davies, Michael Newman, Cody Jones, Kevin J. Satzinger, Murphy Yuezhen Niu, Sam Blackwell, George Holland, Dvir Kafri, Juan Atalaya, Craig Gidney, Demis Has- sabis, Sergio Boixo, Hartmut Neven, and Pushmeet Kohli. “Learning high-accuracy er- ror decoding for quantum processors...

    2024

  27. [27]

    Machine learn- ing decoding of circuit-level noise for bivari- ate bicycle codes

    John Blue, Harshil Avlani, Zhiyang He, Liu Ziyin, and Isaac L. Chuang. “Machine learn- ing decoding of circuit-level noise for bivari- ate bicycle codes” (2025). arXiv:2504.13043

    Pith/arXiv arXiv 2025

  28. [28]

    Scalable neural decoders for practical fault- tolerant quantum computation

    Andi Gu, J. Pablo Bonilla Ataides, Mikhail D. Lukin, and Susanne F. Yelin. “Scalable neural decoders for practical fault- tolerant quantum computation” (2026). arXiv:2604.08358

    Pith/arXiv arXiv 2026

  29. [29]

    The Viterbi algorithm

    G. David Forney. “The Viterbi algorithm”. Proceedings of the IEEE61, 268–278 (1973)

    1973

  30. [30]

    Optimal decoding of lin- ear codes for minimizing symbol error rate

    Lalit R. Bahl, John Cocke, Frederick Jelinek, and Josef Raviv. “Optimal decoding of lin- ear codes for minimizing symbol error rate”. IEEE Transactions on Information Theory 20, 284–287 (1974)

    1974

  31. [31]

    Factor graphs and the sum-product algorithm

    Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. “Factor graphs and the sum-product algorithm”. IEEE Trans- actions on Information Theory 47, 498– 519 (2001)

    2001

  32. [32]

    Bucket elimination: A unify- ing framework for reasoning

    Rina Dechter. “Bucket elimination: A unify- ing framework for reasoning”. Artificial In- telligence113, 41–85 (1999)

    1999

  33. [33]

    Trellises for stabilizer codes: Definition and uses

    Harold Ollivier and Jean-Pierre Tillich. “Trellises for stabilizer codes: Definition and uses”. Physical Review A74, 032304 (2006). arXiv:quant-ph/0512041

    Pith/arXiv arXiv 2006

  34. [34]

    Degener- ate Viterbi decoding

    Emilie Pelchat and David Poulin. “Degener- ate Viterbi decoding”. IEEE Transactions on Information Theory 59, 3915–3921 (2013). arXiv:1204.2439. 14

    Pith/arXiv arXiv 2013

  35. [35]

    Trellis decoding for qu- dit stabilizer codes and its application to qubit topological codes

    Eric Sabo, Arun B. Aloshious, and Ken- neth R. Brown. “Trellis decoding for qu- dit stabilizer codes and its application to qubit topological codes”. IEEE Transactions on Quantum Engineering 5, 1–30 (2024). arXiv:2106.08251

    arXiv 2024

  36. [36]

    Ten- sor networks and quantum error correction

    Andrew J. Ferris and David Poulin. “Ten- sor networks and quantum error correction”. Physical Review Letters113, 030501 (2014). arXiv:1312.4578

    Pith/arXiv arXiv 2014

  37. [37]

    General tensor net- work decoding of 2D Pauli codes

    Christopher T. Chubb. “General tensor net- work decoding of 2D Pauli codes” (2021). arXiv:2101.04125

    arXiv 2021

  38. [38]

    Tensor-network decoding beyond 2D

    Christophe Piveteau, Christopher T. Chubb, and Joseph M. Renes. “Tensor-network decoding beyond 2D”. PRX Quantum 5, 040303 (2024). arXiv:2310.10722

    arXiv 2024

  39. [39]

    Strong resilience of topo- logical codes to depolarization

    H. Bombin, Ruben S. Andrist, Masayuki Ohzeki, Helmut G. Katzgraber, and M. A. Martin-Delgado. “Strong resilience of topo- logical codes to depolarization”. Physical Re- view X2, 021004 (2012). arXiv:1202.1852

    Pith/arXiv arXiv 2012

  40. [40]

    Error threshold for color codes and random three-body Ising models

    Helmut G. Katzgraber, H. Bombin, and M. A. Martin-Delgado. “Error threshold for color codes and random three-body Ising models”. Physical Review Letters 103, 090501 (2009). arXiv:0902.4845

    Pith/arXiv arXiv 2009

  41. [41]

    PyMatching: minimum-weight perfect matching decoder implemen- tation

    Oscar Higgott, Craig Gidney, and con- tributors. “PyMatching: minimum-weight perfect matching decoder implemen- tation” (2026). Python/C++ soft- ware implementation; repositoryhttps: //github.com/oscarhiggott/PyMatching; version 2.3.1, Git tag v2.3.1, com- mite27b8c6a5f5ba10fb74d4ebb 29822f2df5e12bcd; accessed 2026-06-18. 15

    2026