pith. sign in

arxiv: 2606.10399 · v1 · pith:KPBRMRK2new · submitted 2026-06-09 · 💻 cs.DS

Average-Case and Smoothed Near-Optimality for Color-Code Decoding

Daniel Gibney , Jackson Huffstutler This is my paper

Pith reviewed 2026-06-27 11:40 UTC · model grok-4.3

classification 💻 cs.DS
keywords color code decodingaverage-case analysissmoothed analysisapproximation algorithmsblock decoderminimum weight decodingtriangular latticeadditive guarantee
0
0 comments X

The pith

A block-based decoder converts its additive error bound into a (1+ε) multiplicative approximation for color codes under i.i.d. or smoothed noise.

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

The paper shows that a block decoder on triangular color-code lattices, which always satisfies an additive guarantee of OPT plus O(n/τ) where τ is the wall spacing, turns this into a multiplicative (1+ε) guarantee when noise is constant-rate i.i.d. face errors or a constant-rate perturbation of any pattern. Setting τ to Θ(1/ε) makes the decoder succeed with probability 1 minus exp(-Ω(n)) and run in time n 2^{O(1/ε)}. The same conversion works for smoothed adversarial errors. In the sparse regime where error probability is o(1/log² n), the syndrome breaks into small independent pieces and the decoder finds an exact minimum-weight correction in time n 2^{O((log n)^{3/2})}.

Core claim

The decoder satisfies the deterministic additive guarantee |E_alg| ≤ OPT(S) + O(n/τ). For constant-rate i.i.d. face noise and constant local degree, choosing τ = Θ(ε^{-1}) gives a (1+ε)-approximation with probability 1−exp(−Ω(n)), in time n 2^{O(ε^{-1})}. The same near-optimality holds when an arbitrary adversarial error pattern is perturbed by independent constant-rate noise. In the low-probability regime p = o(1/log² n), the syndrome decomposes into small active regions with high probability, allowing independent component-wise decoding and yielding an exact minimum-weight correction in time n 2^{O((log n)^{3/2})}.

What carries the argument

The block-based decoder that partitions the lattice into blocks separated by walls of spacing τ and solves each block separately.

If this is right

  • Choosing τ proportional to 1/ε produces a (1+ε) approximation with exponentially high probability under constant-rate i.i.d. noise.
  • The same (1+ε) guarantee and runtime hold for smoothed adversarial error patterns.
  • When error probability drops to o(1/log² n), the decoder finds an exact minimum-weight solution by handling independent small regions separately.
  • The additive-to-multiplicative conversion relies on the noise model concentrating the total error weight around its mean.

Where Pith is reading between the lines

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

  • Block isolation may let similar additive-to-multiplicative arguments apply to other 2D topological codes that are hard in the worst case.
  • Exponential concentration around the mean error weight suggests the decoder remains reliable even as lattice size grows.
  • One could check the transition by measuring how often the output ratio exceeds 1+ε exactly at the boundary noise rates assumed in the model.

Load-bearing premise

The noise must be either independent constant-rate face errors or a constant-rate random perturbation of any fixed pattern on a lattice with constant local degree.

What would settle it

An i.i.d. noise pattern at constant rate where the decoder output weight exceeds (1+ε) times OPT with probability larger than exp(−Ω(n)).

read the original abstract

Minimum-weight decoding for two-dimensional color codes is NP-hard (Walters and Turner 2026), motivating the search for approximation guarantees beyond worst-case exact decoding. We study a block-based decoder for triangular color-code lattices. The decoder satisfies the deterministic additive guarantee \(\lvert E_{\mathrm{alg}}\rvert \leq \operatorname{OPT}(S)+O(n/\tau)\), where \(n\) is the number of vertices and \(\tau\) is the wall spacing. We show that this additive guarantee becomes a near-optimal multiplicative guarantee under natural noise models. For constant-rate i.i.d. face noise and constant local degree, choosing \(\tau=\Theta(\epsilon^{-1})\) gives a \((1+\epsilon)\)-approximation with probability \(1-\exp(-\Omega(n))\), in time \(n2^{O(\epsilon^{-1})}\). We also prove a smoothed analogue: the same near-optimality guarantee holds when an arbitrary adversarial error pattern is perturbed by independent constant-rate noise. Finally, in the low-probability regime \(p=o(1/\log^2 n)\), the syndrome decomposes into small active regions with high probability, allowing independent component-wise decoding and yielding an exact minimum-weight correction in time \(n2^{O((\log n)^{3/2})}\). These results show that, despite worst-case hardness, color-code decoding admits strong average-case, smoothed, and sparse-regime guarantees.

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

0 major / 3 minor

Summary. The paper studies a block-based decoder for minimum-weight decoding of 2D color codes on triangular lattices. It proves a deterministic additive guarantee |E_alg| ≤ OPT(S) + O(n/τ) for wall spacing τ. Under constant-rate i.i.d. face noise (or its smoothed analogue) with constant local degree, setting τ = Θ(ε^{-1}) converts this to a (1+ε)-multiplicative approximation with probability 1−exp(−Ω(n)) in time n 2^{O(ε^{-1})}. In the sparse regime p = o(1/log² n), the syndrome decomposes into small clusters, enabling exact minimum-weight decoding in time n 2^{O((log n)^{3/2})}.

Significance. If the probabilistic arguments hold, the results establish the first strong average-case and smoothed near-optimality guarantees for color-code decoding despite its worst-case NP-hardness. The conversion from additive to multiplicative approximation via standard concentration bounds under natural noise models, together with the exact sparse-regime algorithm, is a meaningful contribution to quantum error-correction algorithms. The parameter-free nature of the additive guarantee and the explicit time bounds are strengths.

minor comments (3)
  1. The abstract states the time bound n2^{O(ε^{-1})} but does not clarify whether the hidden constant in the exponent depends on the fixed local degree or lattice parameters; adding a sentence on this dependence would improve precision.
  2. The low-probability regime result invokes a cluster decomposition yielding the specific exponent O((log n)^{3/2}); a brief high-level outline of how the active-region size distribution produces this exponent (even if details are in a later section) would aid readers.
  3. The phrase 'constant local degree' is used without an explicit numerical bound or reference to the triangular lattice degree; stating the maximum degree (e.g., 6) or citing the relevant lattice definition would remove ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper states a deterministic additive guarantee |E_alg| ≤ OPT(S) + O(n/τ) that is converted to a (1+ε) multiplicative guarantee via standard concentration bounds once τ = Θ(ε^{-1}) and OPT(S) = Ω(n) holds w.h.p. under the stated i.i.d. or smoothed noise model. This conversion uses ordinary probabilistic arguments rather than any fitted parameter renamed as a prediction, self-citation chain, or ansatz smuggled from prior work. The NP-hardness citation is external, the time bound follows directly from the exponential dependence on τ, and the low-probability regime analysis is likewise independent. No load-bearing step reduces by construction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on the cited NP-hardness result, standard probabilistic concentration inequalities, and the modeling assumption of constant-rate i.i.d. face noise on a constant-degree triangular lattice. No free parameters are fitted to data; τ is chosen explicitly as Θ(ε^{-1}). No new entities are postulated.

axioms (2)
  • domain assumption Minimum-weight decoding for two-dimensional color codes is NP-hard (Walters and Turner 2026)
    Invoked in the first sentence to motivate the search for approximation guarantees.
  • standard math Standard Chernoff/Hoeffding-type concentration bounds apply to the number of errors inside blocks
    Implicit in the high-probability statements 1−exp(−Ω(n)).

pith-pipeline@v0.9.1-grok · 5792 in / 1551 out tokens · 22696 ms · 2026-06-27T11:40:49.355504+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

12 extracted references · 6 linked inside Pith

  1. [1]

    Kitaev, A. Yu. , title =. Annals of Physics , volume =. 2003 , doi =. quant-ph/9707021 , archivePrefix =

    Pith/arXiv arXiv 2003

  2. [2]

    Journal of Mathematical Physics , volume =

    Dennis, Eric and Kitaev, Alexei and Landahl, Andrew and Preskill, John , title =. Journal of Mathematical Physics , volume =. 2002 , doi =. quant-ph/0110143 , archivePrefix =

    Pith/arXiv arXiv 2002

  3. [3]

    and Martin-Delgado, M

    Bombin, H. and Martin-Delgado, M. A. , title =. Physical Review Letters , volume =. 2006 , doi =. quant-ph/0605138 , archivePrefix =

    Pith/arXiv arXiv 2006

  4. [4]

    Katzgraber, H. G. and Bombin, H. and Martin-Delgado, M. A. , title =. Physical Review Letters , volume =. 2009 , doi =. 0902.4845 , archivePrefix =

    Pith/arXiv arXiv 2009

  5. [5]

    Physical Review A , volume =

    Delfosse, Nicolas , title =. Physical Review A , volume =. 2014 , doi =. 1308.6207 , archivePrefix =

    Pith/arXiv arXiv 2014

  6. [6]

    Quantum , volume =

    Kubica, Aleksander and Delfosse, Nicolas , title =. Quantum , volume =. 2023 , doi =. 1905.07393 , archivePrefix =

    arXiv 2023

  7. [7]

    , title =

    Delfosse, Nicolas and Nickerson, Naomi H. , title =. Quantum , volume =. 2021 , doi =. 1709.06218 , archivePrefix =

    arXiv 2021

  8. [8]

    Canadian Journal of Mathematics , volume =

    Edmonds, Jack , title =. Canadian Journal of Mathematics , volume =. 1965 , doi =

    1965

  9. [9]

    Surveys in Combinatorics, 1989 , series =

    McDiarmid, Colin , title =. Surveys in Combinatorics, 1989 , series =. 1989 , doi =

    1989

  10. [10]

    IEEE Transactions on Information Theory , volume =

    Iyer, Pavithran and Poulin, David , title =. IEEE Transactions on Information Theory , volume =. 2015 , doi =. 1310.3235 , archivePrefix =

    Pith/arXiv arXiv 2015

  11. [11]

    , title =

    Walters, Mark and Turner, Mark L. , title =. 2026 , eprint =

    2026

  12. [12]

    2026 , eprint =

    Gu, Shouzhen and Wang, Lily and Kubica, Aleksander , title =. 2026 , eprint =

    2026