Pith. sign in

REVIEW 2 minor 16 references

For any ε>0, a polynomial-time algorithm finds a colour-code error set of weight at most (1+ε) times the minimum.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-27 00:15 UTC pith:ETNO7UJF

load-bearing objection The paper shows a PTAS exists for min-weight decoding on the planar colour code, answering the open question left by the author's prior NP-hardness result.

arxiv 2606.18035 v1 pith:ETNO7UJF submitted 2026-06-16 quant-ph

Approximately Decoding the Colour Code

Mark Walters This is my paper
classification quant-ph
keywords colour codeminimum weight decodingapproximation algorithmquantum error correctionNP-hardpolynomial time approximation schemesyndrome decodingplanar lattice
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves that minimum-weight decoding of the (6.6.6 planar) colour code, though NP-hard in the exact case, admits a polynomial-time approximation scheme. For every fixed ε>0 an algorithm returns, from any syndrome, an error set whose weight lies within a (1+ε) factor of the true minimum-weight solution. This immediately yields an efficient decoder that corrects every error pattern of weight up to (1−ε)d/2 in a distance-d code. A reader cares because the result separates the intractability of exact decoding from the feasibility of near-optimal correction in a concrete quantum code.

Core claim

For any ε>0 there is a polynomial time algorithm that, given a syndrome, can find an error-set generating that syndrome whose weight is at most 1+ε times the weight of the minimum weight decoding. As a consequence, for any ε>0 there is a polynomial time algorithm that can correct all errors of weight up to (1−ε)d/2 in the distance d colour code.

What carries the argument

Polynomial-time approximation scheme for minimum-weight syndrome decoding on the (6.6.6) colour-code lattice.

Load-bearing premise

The geometric structure of the (6.6.6 planar) colour code permits a PTAS for its minimum-weight decoding problem.

What would settle it

An explicit family of syndromes on the (6.6.6) lattice for which every polynomial-time algorithm returns an error set whose weight exceeds (1+ε) times the minimum for some fixed ε>0.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Approximate minimum-weight decoding is not NP-hard.
  • Errors of weight up to almost d/2 can be corrected in polynomial time.
  • The NP-hardness of exact decoding does not block practical near-optimal decoders for this code.
  • The existence of a PTAS opens the possibility of designing faster, still-approximate decoders with smaller polynomials.

Where Pith is reading between the lines

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

  • Similar lattice-based quantum codes may also admit PTAS decoding once their exact hardness is established.
  • The large degree of the polynomial suggests that concrete implementations will require further algorithmic refinement.
  • The result links the planarity and colourability properties of the lattice directly to approximability thresholds in coding problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The paper proves that minimum-weight decoding of the (6.6.6 planar) colour code admits a PTAS: for every ε > 0 there exists a polynomial-time algorithm that, given a syndrome, returns an error set generating the syndrome whose weight is at most (1 + ε) times the minimum weight. As an immediate corollary, the same algorithm corrects every error of weight ≤ (1 − ε)d/2 in a distance-d code.

Significance. If the claimed PTAS holds, the result is significant. It resolves the open question left by the authors’ prior NP-hardness proof for the exact problem, shows that approximate decoding is not NP-hard, and supplies an explicit (albeit impractically large) polynomial-time procedure that achieves correction arbitrarily close to the d/2 information-theoretic limit. The existence proof itself constitutes a parameter-free derivation of approximability.

minor comments (2)
  1. [Abstract] Abstract, final paragraph: the remark that “the polynomial we give is impractically large” is useful but should be expanded in §6 or the conclusion with at least one sentence explaining the source of the large degree (e.g., the size of the dynamic-programming table or the number of colours used in the PTAS construction).
  2. [Abstract] The consequence for error correction (errors up to (1−ε)d/2) follows immediately from the (1+ε)-approximation guarantee, but a one-line derivation of the inequality (1+ε)·((1−ε)d/2) < d/2 would improve readability for readers outside coding theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. Their summary correctly captures the main contribution: a PTAS for minimum-weight decoding of the (6.6.6) planar colour code, with the stated corollary on near-optimal error correction.

Circularity Check

0 steps flagged

No significant circularity; PTAS claim is independent of self-cited hardness result

full rationale

The paper's central claim is the existence of a PTAS for minimum-weight decoding on the (6.6.6) planar colour code, proved in this work. The self-citation to prior NP-hardness of the exact problem is background only and does not load-bear the approximability result; the two statements are mathematically independent (NP-hardness of exact optimization does not preclude PTAS). The error-correction consequence follows immediately from the (1+ε) guarantee via the algebraic identity (1+ε)·((1-ε)d/2) < d/2, with no reduction to fitted parameters, self-definitions, or ansatzes. No quoted step equates a prediction to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard complexity-theoretic assumptions and the validity of the prior NP-hardness proof for exact decoding; no free parameters or invented entities appear in the abstract.

axioms (2)
  • domain assumption The prior result that exact minimum-weight decoding of the (6.6.6 planar) colour code is NP-hard holds.
    Invoked to frame the new approximability result as resolving the remaining open question.
  • standard math Standard assumptions of polynomial-time computability and approximation algorithms in theoretical computer science.
    Background for the existence of a PTAS.

pith-pipeline@v0.9.1-grok · 5689 in / 1265 out tokens · 32590 ms · 2026-06-27T00:15:21.350626+00:00 · methodology

0 comments
read the original abstract

Recently we showed that minimum weight decoding in the (6.6.6 planar) colour code is NP-hard. However, it remained an open question as to whether it was possible to approximate the minimum weight decoding arbitrarily closely in polynomial time. In this paper we prove that it is possible: for any $\varepsilon>0$ there is an polynomial time algorithm that, given a syndrome, can find an error-set generating that syndrome whose weight is at most $1+\varepsilon$ times the weight of the minimum weight decoding. As a consequence we see that, for any $\varepsilon>0$, there is a polynomial time algorithm that can correct all errors of weight up to $(1-\varepsilon)d/2$ in the distance $d$ colour code (so almost up to the theoretical $d/2$ limit). The polynomial we give is impractically large, but it does open the door for sensible polynomial time algorithms that approximate minimum weight decoding and, in particular, shows that approximate decoding is not NP-hard.

Figures

Figures reproduced from arXiv: 2606.18035 by Mark Walters.

Figure 1
Figure 1. Figure 1: The colour code and its error model. (a) The 6.6.6 colour code (with boundary). There are data qubits on the vertices of a hexagonal lattice and the checks are the coloured faces. An X-error on a bulk data qubit (the yellow star in the middle of the picture) triggers the three Z-checks shown ringed in black. However, an X-error on a qubit lying on a boundary, only triggers the two checks (faces) containing… view at source ↗
Figure 2
Figure 2. Figure 2: (a) A rhombus consisting of sixteen tiles. (b) Two adjacent tiles with six errors joining them: one of each colour-orientation. Once we have proved Proposition 2 it is relatively easy to deduce Theorem 1 which we do in Section 6. There are two key ideas for the proof of Proposition 2 (both inspired by Arora’s proof). • We set up a constrained problem – roughly we forbid the error-set from containing certai… view at source ↗
Figure 3
Figure 3. Figure 3: (a) Given an error f (the red triangle) look in the nearest portal tile (the rhombus shown) and pick the error p with the same colour-orientation (the green triangle) in the nearest portal tile (the tile shown). (b) We can join the red error to the green error by two ‘paths’ as shown: the set of all the shown errors has no syndrome, so the syndrome of the combined yellow and green errors (together these fo… view at source ↗
Figure 4
Figure 4. Figure 4: The distance 11 reduced colour code – the triangular region [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The four steps in the post-processing described in Lemma [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The syndrome box (the rhombus) with the hexagon [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗

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

16 extracted references · 5 canonical work pages

  1. [1]

    Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.Journal of the ACM, 45(5):753–782, September 1998

    Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.Journal of the ACM, 45(5):753–782, September 1998

    1998

  2. [2]

    Proof verification and the hardness of approximation problems.Journal of the ACM, 45(3):501–555, 1998

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems.Journal of the ACM, 45(3):501–555, 1998. Preliminary version in IEEE FOCS 1992

    1998

  3. [3]

    Probabilistic checking of proofs: A new characterization of NP

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70–122, January 1998

    1998

  4. [4]

    Tradeoffs for reliable quantum information storage in 2d systems.Physical Review Letters, 104:050503, Feb 2010

    Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeoffs for reliable quantum information storage in 2d systems.Physical Review Letters, 104:050503, Feb 2010

    2010

  5. [5]

    Decoding color codes by projection onto surface codes.Physical Review A, 89(1):012317, January 2014

    Nicolas Delfosse. Decoding color codes by projection onto surface codes.Physical Review A, 89(1):012317, January 2014

    2014

  6. [6]

    New circuits and an open source decoder for the color code, December

    Craig Gidney and Cody Jones. New circuits and an open source decoder for the color code, December

  7. [7]

    arXiv:2312.08813 [quant-ph]

    work page Pith review arXiv

  8. [8]

    The color code, the surface code, and the transver- sal CNOT: NP-hardness of minimum-weight decoding, March 2026

    Shouzhen Gu, Lily Wang, and Aleksander Kubica. The color code, the surface code, and the transver- sal CNOT: NP-hardness of minimum-weight decoding, March 2026. arXiv:2603.22064

    work page arXiv 2026

  9. [9]

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

    Shouzhen Gu, Lily Wang, and Aleksander Kubica. A polynomial-time approximation scheme for minimum-weight decoding of topological codes, June 2026

    2026

  10. [10]

    Some optimal inapproximability results.Journal of the ACM, 48(4):798–859, July 2001

    Johan H˚ astad. Some optimal inapproximability results.Journal of the ACM, 48(4):798–859, July 2001

    2001

  11. [11]

    Koutsioumpas, T

    Stergios Koutsioumpas, Tamas Noszko, Hasan Sayginel, Mark Webster, and Joschka Roffe. Colour Codes Reach Surface Code Performance using Vibe Decoding, August 2025. arXiv:2508.15743 [quant- ph]. 14

    work page arXiv 2025

  12. [12]

    Efficient color code decoders ind≥2 dimensions from toric code decoders.Quantum, 7:929, February 2023

    Aleksander Kubica and Nicolas Delfosse. Efficient color code decoders ind≥2 dimensions from toric code decoders.Quantum, 7:929, February 2023

    2023

  13. [13]

    Kaavya Sahay and Benjamin J. Brown. Decoder for the triangular color code by matching on a M¨ obius strip.PRX Quantum, 3(1):010310, January 2022

    2022

  14. [14]

    Senior, Thomas Edlich, Francisco J

    Andrew W. Senior, Thomas Edlich, Francisco J. H. Heras, Lei M. Zhang, Oscar Higgott, James S. Spencer, Taylor Applebaum, Sam Blackwell, Justin Ledford, Akvil˙ e ˇZemgulyt˙ e, Augustin ˇZ´ ıdek, Noah Shutty, Andrew Cowie, Yin Li, George Holland, Peter Brooks, Charlie Beattie, Michael New- man, Alex Davies, Cody Jones, Sergio Boixo, Hartmut Neven, Pushmeet ...

    work page arXiv 2025

  15. [15]

    Mark Walters and Mark L. Turner. Minimum Weight Decoding in the Colour Code is NP-hard,

  16. [16]

    Walters and M

    arXiv:2603.04234. Appendix Lemma 14.Suppose thatSis a syndrome of diameterdlying inside theL×Lsyndrome box and including the point(d, d). Then there is a minimum weight error-setEgeneratingSwhere all the errors ofElie inside the syndrome box. Proof.LetHbe the regular hexagon of ‘radius’dcentred at the point (d, d) – see Figure 6. We see that His contained...

    work page arXiv