pith. sign in

arxiv: 2606.18145 · v1 · pith:XR6C7DXEnew · submitted 2026-06-16 · 🪐 quant-ph · cs.DS

A polynomial-time approximation scheme for minimum-weight decoding of topological codes

Shouzhen Gu , Lily Wang , Aleksander Kubica This is my paper

Pith reviewed 2026-06-27 00:01 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords topological codesminimum-weight decodingPTASstabilizer codesquantum error correctionapproximation algorithmstoric codecolor code
0
0 comments X

The pith

Minimum-weight decoding of 2D topological codes admits a polynomial-time approximation scheme.

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

The paper shows that exact minimum-weight decoding for two-dimensional topological translationally invariant stabilizer codes is NP-hard, yet a recovery operator whose weight is at most 1+ε times the minimum can still be found in polynomial time for any fixed ε>0. The argument adapts Arora's geometric approximation techniques to the case where errors appear as strings linking point-like excitations. A reader would care because these codes are central to fault-tolerant quantum computation, and the result supplies a practical decoding route even when optimal solutions remain intractable. The same approach covers certain higher-dimensional codes and noise models such as phenomenological or circuit-level noise on the toric code.

Core claim

We prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant ε>0, a recovery operator of weight within a multiplicative factor of 1+ε of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.

What carries the argument

Adaptation of Arora's PTAS for Euclidean geometric problems to the geometry of string-like errors that connect point-like excitations.

If this is right

  • Practical decoders for large 2D color codes and toric codes can return recovery operators guaranteed to be within any constant factor of optimal.
  • The same PTAS covers the toric code under phenomenological and circuit-level noise models.
  • Exact minimum-weight decoding stays NP-hard while approximation becomes efficient.
  • The technique reaches certain higher-dimensional topological codes whose error strings satisfy the same geometric structure.

Where Pith is reading between the lines

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

  • Similar geometric reductions may yield PTAS results for other quantum decoding problems that reduce to connecting point defects with paths.
  • Runtime benchmarks on concrete lattices such as the toric code would reveal whether the PTAS is already useful at moderate code sizes.
  • The result raises the question of whether PTASs exist for decoding on lattices with defects or boundaries that still admit a string-excitation description.

Load-bearing premise

The decoding task can be cast as finding short connecting strings between point-like excitations so that Euclidean-style approximation methods apply.

What would settle it

An explicit 2D TTI code family and a fixed ε>0 for which every polynomial-time algorithm produces a recovery operator heavier than (1+ε) times the true minimum on some syndrome would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.18145 by Aleksander Kubica, Lily Wang, Shouzhen Gu.

Figure 1
Figure 1. Figure 1: FIG. 1. (a) A 2D TTI code on a square lattice has a constant number of qubits at each vertex; its stabilizers are [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Finding the minimum-weight [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. (a) To view the toric code in the framework of 2D TTI codes, we move qubits (black dots) from the edges [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (c). The set Jk consisting of the plaquettes with a nonzero proper subset of its vertices in T + k contains the possible excitations. The error e ′ k is defined by moving all excitations through J to a single location, which has support contained in BT . For Tk on the ends of the T, this uses the fact that we placed an extra portal distance two away from each endpoint of T. Note that the support of e ′ k o… view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. (a) The Patching Property for higher-dimensional decoding problems. An error [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
read the original abstract

Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli $Z$ errors and the toric code with Pauli $X$, $Y$ and $Z$ errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant $\varepsilon>0$, a recovery operator of weight within a multiplicative factor of $1+\varepsilon$ of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.

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 / 2 minor

Summary. The manuscript proves that minimum-weight decoding of 2D topological translationally invariant (TTI) stabilizer codes admits a polynomial-time approximation scheme (PTAS). For any fixed ε > 0, a recovery operator whose weight is at most (1 + ε) times the minimum weight can be found in polynomial time. The proof reduces the decoding task to a geometric optimization problem on point-like excitations connected by string-like errors, to which Arora's PTAS for Euclidean problems (such as TSP) is applied. The result is stated to extend to selected higher-dimensional topological codes and to the toric code under phenomenological or circuit-level noise.

Significance. If the reduction is correctly established, the result is significant: exact minimum-weight decoding is NP-hard for the codes considered, yet a PTAS supplies a tunable approximation guarantee that becomes arbitrarily close to optimal while remaining polynomial-time. The approach re-uses a classical geometric PTAS rather than inventing a new one, and the extension beyond 2D broadens its relevance to quantum memories. No machine-checked proofs or reproducible code are mentioned, but the explicit link to an established classical result is a strength.

minor comments (2)
  1. The abstract states that the method 'applies when decoding can be cast in terms of point-like excitations connected by string-like errors,' but the manuscript should include a dedicated subsection that explicitly verifies the metric and embedding conditions required by Arora's PTAS (e.g., Euclidean distances versus lattice path lengths).
  2. A brief complexity table or statement of the running-time dependence on ε and code size would improve clarity, even if the polynomial bound is already implied by the cited classical result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its significance, and recommendation of minor revision. The report contains no specific major comments requiring point-by-point response.

Circularity Check

0 steps flagged

No significant circularity; derivation applies external PTAS to standard anyon model

full rationale

The paper's central result is a PTAS obtained by casting minimum-weight decoding of 2D TTI codes as a geometric optimization problem (point-like excitations connected by string-like errors) and invoking Arora's existing PTAS for Euclidean TSP-like problems. This reduction uses the standard anyon/string model of topological stabilizer codes, which is independent of the present work and externally verifiable. No equations, fitted parameters, or self-citations appear in the load-bearing steps; the NP-hardness of exact decoding is compatible with an approximation scheme. The derivation chain is self-contained against external benchmarks and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Ledger extracted from abstract only; full paper not available so exhaustive list of parameters or axioms cannot be confirmed.

axioms (1)
  • domain assumption Arora's PTAS for Euclidean geometric problems applies once decoding is expressed as point-like excitations connected by string-like errors
    Explicitly invoked in the abstract as the foundation of the approach.

pith-pipeline@v0.9.1-grok · 5716 in / 1315 out tokens · 36829 ms · 2026-06-27T00:01:11.349707+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

48 extracted references · 2 canonical work pages

  1. [1]

    using exhaustive search, which is constant. Decoding subproblems at leveli < i 0 are solved by iterating through r-light lifts, finding the corresponding solutions to subdecoding problems at leveli+ 1, and piecing them together. Because there are four line segments that are shared between two of the four level-(i+ 1) squares as well as one corner shared b...

  2. [2]

    IfT ′ is a different line segment of level at leasti, then(B T ′ \T ′)∩T=∅. 2. S T ′:level(T ′)<i(BT ′ \T ′) ∩T ≤A. Proof.IfT ′ has level at leasti, then either it is entirely contained inT, it is disjoint fromT, or it intersects Tat the endpoint ofT ′. In all cases, (B T ′ \T ′)∩T=∅. IfT ′ has level less thani, i.e., level(T ′)< i, then an endpoint ofTma...

  3. [3]

    squares” to be slightly rectangular by rounding lines to the nearest integer coordinate. That is, for a shift (c, d), we can define the level-i“squares

    for any other line segmentT ′ of level lower than or equal to the level ofT,suppe ′ ∩T ′ =∅. Proof (toric code).The syndrome ofeconsists of excitations whose total charge is neutral and which are located on plaquettes adjacent toT. The errore ′ will be obtained from string operators that annihilate all excitations by moving allXexcitations to one place an...

    2024

  4. [4]

    P. W. Shor, Scheme for reducing decoherence in quantum computer memory, Physical Review A52, R2493–R2496 (1995)

    1995

  5. [5]

    A. M. Steane, Error correcting codes in quantum theory, Physical Review Letters77, 793–797 (1996)

    1996

  6. [6]

    Gottesman, Class of quantum error-correcting codes saturating the quantum hamming bound, Physical Review A54, 1862–1868 (1996)

    D. Gottesman, Class of quantum error-correcting codes saturating the quantum hamming bound, Physical Review A54, 1862–1868 (1996)

    1996

  7. [7]

    P. W. Shor, Fault-tolerant quantum computation, inProceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS ’96 (IEEE Computer Society, USA, 1996) p. 56

    1996

  8. [8]

    Preskill, Reliable quantum computers, Proceedings of the Royal Society of London

    J. Preskill, Reliable quantum computers, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences454, 385–410 (1998)

    1998

  9. [9]

    Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics303, 2–30 (2003)

    A. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics303, 2–30 (2003)

    2003

  10. [10]

    Bombin, An introduction to topological quantum codes (2013), arXiv:1311.0277 [quant-ph]

    H. Bombin, An introduction to topological quantum codes (2013), arXiv:1311.0277 [quant-ph]

    Pith/arXiv arXiv 2013

  11. [11]

    A. M. Kubica,The ABCs of the Color Code: A Study of Topological Quantum Codes as Toy Models for Fault- Tolerant Quantum Computation and Quantum Phases Of Matter, Ph.D. thesis (2018)

    2018

  12. [12]

    S. B. Bravyi and A. Y. Kitaev, Quantum codes on a lattice with boundary (1998), arXiv:quant-ph/9811052 [quant-ph]

    Pith/arXiv arXiv 1998

  13. [13]

    Haah, Commuting pauli hamiltonians as maps between free modules, Communications in Mathematical Physics 324, 351–399 (2013)

    J. Haah, Commuting pauli hamiltonians as maps between free modules, Communications in Mathematical Physics 324, 351–399 (2013)

    2013

  14. [14]

    A. A. Kovalev and L. P. Pryadko, Quantum kronecker sum-product low-density parity-check codes with finite rate, Physical Review A88, 10.1103/physreva.88.012311 (2013)

    work page doi:10.1103/physreva.88.012311 2013

  15. [15]

    Bravyi, A

    S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, High-threshold and low-overhead fault-tolerant quantum memory, Nature627, 778 (2024)

    2024

  16. [16]

    Steffan, S

    V. Steffan, S. H. Choe, N. P. Breuckmann, F. R. F. Pereira, and J. N. Eberhardt, Tile codes: High-efficiency quantum codes on a lattice with boundary, Physical Review Letters135, 170601 (2025)

    2025

  17. [17]

    B. M. Terhal, Quantum error correction for quantum memories, Reviews of Modern Physics87, 307–346 (2015)

    2015

  18. [18]

    Dennis, A

    E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, Topological quantum memory, Journal of Mathematical Physics43, 4452–4505 (2002)

    2002

  19. [19]

    Delfosse, Decoding color codes by projection onto surface codes, Physical Review A89, 012317 (2014)

    N. Delfosse, Decoding color codes by projection onto surface codes, Physical Review A89, 012317 (2014)

    2014

  20. [20]

    Kubica and N

    A. Kubica and N. Delfosse, Efficient color code decoders ind≥2 dimensions from toric code decoders, Quantum 7, 929 (2023). 18

    2023

  21. [21]

    S. J. S. Tan, I. Gill, E. Huang, P. Liu, C. Zhao, H. Dehghani, A. Kubica, H. Zhou, and A. Dua, Generalized matching decoders for 2d topological translationally-invariant codes (2026), arXiv:2603.05402 [quant-ph]

    arXiv 2026

  22. [22]

    Sahay, D

    K. Sahay, D. J. Williamson, and B. J. Brown, A matching decoder for bivariate bicycle codes (2026), arXiv:2602.22770 [quant-ph]

    Pith/arXiv arXiv 2026

  23. [23]

    Walters and M

    M. Walters and M. L. Turner, Minimum weight decoding in the colour code is np-hard (2026), arXiv:2603.04234 [quant-ph]

    arXiv 2026

  24. [24]

    S. Gu, L. Wang, and A. Kubica, The color code, the surface code, and the transversal cnot: Np-hardness of minimum-weight decoding (2026), arXiv:2603.22064 [quant-ph]

    arXiv 2026

  25. [25]

    Delfosse and J.-P

    N. Delfosse and J.-P. Tillich, A decoding algorithm for css codes using the x/z correlations, in2014 IEEE International Symposium on Information Theory(IEEE, 2014) p. 1071–1075

    2014

  26. [26]

    Higgott, T

    O. Higgott, T. C. Bohdanowicz, A. Kubica, S. T. Flammia, and E. T. Campbell, Improved decoding of circuit noise and fragile boundaries of tailored surface codes, Physical Review X13, 031007 (2023)

    2023

  27. [27]

    A. d. iOlius, J. E. Martinez, P. Fuentes, and P. M. Crespo, Performance enhancement of surface codes via recursive minimum-weight perfect-match decoding, Physical Review A108, 022401 (2023)

    2023

  28. [28]

    Arora, Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems, J

    S. Arora, Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems, J. ACM45, 753–782 (1998)

    1998

  29. [29]

    Hsieh and F

    M.-H. Hsieh and F. Le Gall, Np-hardness of decoding quantum error-correction codes, Physical Review A83, 052331 (2011)

    2011

  30. [30]

    Kuo and C.-C

    K.-Y. Kuo and C.-C. Lu, On the hardnesses of several quantum decoding problems, Quantum Information Processing19, 123 (2020)

    2020

  31. [31]

    Yoshida, Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes, Annals of Physics326, 15–95 (2011)

    B. Yoshida, Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes, Annals of Physics326, 15–95 (2011)

    2011

  32. [32]

    Bomb´ ın, Structure of 2d topological stabilizer codes, Communications in Mathematical Physics327, 387 (2014)

    H. Bomb´ ın, Structure of 2d topological stabilizer codes, Communications in Mathematical Physics327, 387 (2014)

    2014

  33. [33]

    J. W. Harrington,Analysis of Quantum Error-Correcting Codes: Symplectic Lattice Codes and Toric Codes, phd, California Institute of Technology (2004)

    2004

  34. [34]

    Duclos-Cianci and D

    G. Duclos-Cianci and D. Poulin, Fast decoders for topological quantum codes, Physical Review Letters104, 050504 (2010)

    2010

  35. [35]

    Bravyi and J

    S. Bravyi and J. Haah, Quantum self-correction in the 3d cubic code model, Phys. Rev. Lett.111, 200501 (2013)

    2013

  36. [36]

    Kubica and M

    A. Kubica and M. Vasmer, Single-shot quantum error correction with the three-dimensional subsystem toric code, Nature Communications13, 6272 (2022)

    2022

  37. [37]

    J. C. Bridgeman, A. Kubica, and M. Vasmer, Lifting topological codes: Three-dimensional subsystem codes from two-dimensional anyon models, PRX Quantum5, 020310 (2024)

    2024

  38. [38]

    Bombin, Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes, New Journal of Physics17, 083002 (2015)

    H. Bombin, Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes, New Journal of Physics17, 083002 (2015)

    2015

  39. [39]

    Kubica and M

    A. Kubica and M. E. Beverland, Universal transversal gates with color codes: A simplified approach, Physical Review A91, 032330 (2015)

    2015

  40. [40]

    Bombin and M

    H. Bombin and M. A. Martin-Delgado, Exact topological quantum order ind= 3 and beyond: Branyons and brane-net condensates, Physical Review B75, 075103 (2007)

    2007

  41. [41]

    R. M. Karp, Reducibility among combinatorial problems, inComplexity of Computer Computations(Springer US, 1972) p. 85–103

    1972

  42. [42]

    M. R. Garey and D. S. Johnson,Computers and Intractability; A Guide to the Theory of NP-Completeness(W. H. Freeman & Co., USA, 1990)

    1990

  43. [43]

    J. M. Steele and T. L. Snyder, Worst-case growth rates of some classical problems of combinatorial optimization, SIAM Journal on Computing18, 278 (1989), https://doi.org/10.1137/0218019

    work page doi:10.1137/0218019 1989

  44. [44]

    Chamberland, A

    C. Chamberland, A. Kubica, T. J. Yoder, and G. Zhu, Triangular color codes on trivalent graphs with flag qubits, New Journal of Physics22, 023019 (2020)

    2020

  45. [45]

    Sahay and B

    K. Sahay and B. J. Brown, Decoder for the triangular color code by matching on a m¨ obius strip, PRX Quantum 3, 010310 (2022)

    2022

  46. [46]

    S.-H. Lee, A. Li, and S. D. Bartlett, Color code decoder with improved scaling for correcting circuit-level noise, Quantum9, 1609 (2025)

    2025

  47. [47]

    A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, Surface codes: Towards practical large-scale quantum computation, Physical Review A86, 032324 (2012)

    2012

  48. [48]

    Walters, Approximately decoding the colour code (2026), arXiv:2606.XXXXX

    M. Walters, Approximately decoding the colour code (2026), arXiv:2606.XXXXX

    2026