A polynomial-time approximation scheme for minimum-weight decoding of topological codes
Shouzhen Gu, Lily Wang, Aleksander Kubica
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 errors and the toric code with Pauli , and 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 , a recovery operator of weight within a multiplicative factor of 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.
AI Impact Assessments
(1 models)Scientific Impact Assessment
1. Core Contribution
This paper establishes a polynomial-time approximation scheme (PTAS) for minimum-weight decoding of two-dimensional topological translationally invariant (2D TTI) stabilizer codes. Specifically, for any constant ε > 0, the algorithm finds a recovery operator whose weight is within a multiplicative factor (1+ε) of the minimum, with time complexity L²(log L)^{O(1/ε)} on an L×L lattice. This directly addresses the complexity gap created by recent NP-hardness results for exact minimum-weight decoding of the color code with Pauli Z errors and the toric code with Pauli X, Y, Z errors. The approach adapts Arora's celebrated PTAS for Euclidean optimization problems (e.g., traveling salesman) to the quantum error correction setting, exploiting the geometric structure of point-like excitations connected by string-like errors.
2. Methodological Rigor
The paper is technically rigorous and well-structured. The proof proceeds through clearly delineated steps:
1. Dynamic programming over recursive dissection (Section IV): The lattice is hierarchically partitioned into squares with portals on boundaries. The algorithm finds optimal r-light errors (those crossing boundaries only at portals, at most r times per side) via dynamic programming over the dissection tree.
2. Structure Theorem (Section V): The core theoretical result shows that minimum-weight errors can be transformed into r-light ones with only (1+ε) multiplicative cost increase. This is established through two key properties—Patching (reducing crossings of line segments) and Rerouting (shifting crossings to portal locations)—proven first for the toric code with explicit constructions.
3. Extension to general 2D TTI codes (Section VI): A careful treatment handles excitations near square boundaries via Lemma 10, randomizing over shifts (c,d) to ensure excitations can be moved away from boundaries at low cost.
The proofs are complete and self-contained. The randomized algorithm succeeds with probability ≥ 1/4, and a deterministic version is provided with an L⁴(log L)^{O(1/ε)} runtime. The complexity analysis is clean, with explicit tracking of constants depending on ε and code parameters.
3. Potential Impact
Theoretical impact: This is a significant complexity-theoretic result for quantum error correction. It completely resolves the approximability question for minimum-weight decoding of 2D TTI codes: despite NP-hardness of the exact problem, arbitrarily good approximations are achievable in polynomial time. This is the first PTAS for this problem class, improving upon the previous best provable approximation ratio of 2 (from independent X/Z matching).
Practical implications: The paper identifies an explicit decoder for the color code that corrects any error of weight up to (1-ε)d/2, approaching the optimal half-distance bound—an improvement over all previous color-code decoders with provable guarantees. The framework also extends to:
Broader influence: The successful adaptation of Arora's PTAS framework to quantum coding theory opens a methodological bridge between classical combinatorial optimization and quantum error correction. This could inspire further transfers of approximation algorithm techniques to QEC problems.
4. Timeliness & Relevance
This work is exceptionally timely. It arrives immediately after the NP-hardness results for minimum-weight decoding of basic topological codes (published in 2026 by the same group and by Walters & Turner), providing the natural follow-up question's answer. With the quantum computing community actively pursuing fault-tolerant implementations using surface and color codes, understanding the computational complexity of decoding—and what approximations are achievable—is of immediate practical relevance. The extension to circuit-level noise models makes it particularly pertinent to experimental settings.
5. Strengths & Limitations
Key Strengths:
Notable Limitations:
Additional Observations
The concurrent independent work by Walters on PTAS for the color code specifically suggests this result was "in the air," but the present paper's generality (all 2D TTI codes plus higher-dimensional extensions) gives it substantially broader scope. The connection to renormalization-group decoders is noted but underexplored—this could be a fruitful direction for practical improvements.
Generated Jun 17, 2026
Comparison History (17)
Paper 1 resolves a fundamental theoretical question in quantum error correction by proving that minimum-weight decoding of 2D topological stabilizer codes admits a PTAS despite being NP-hard. This has broad implications for fault-tolerant quantum computation, a central challenge in quantum computing. The result bridges computational complexity theory and quantum error correction in a novel way, extending Arora's classical framework to quantum codes. Paper 2 is a valuable engineering advance in quantum magnetometry, but represents incremental improvement in miniaturization and sensitivity rather than a conceptual breakthrough. Paper 1's theoretical contribution has wider and more lasting impact across multiple fields.
Paper 1 offers a concrete, rigorous algorithmic breakthrough: a PTAS for minimum-weight decoding of broad classes of topological stabilizer codes despite NP-hardness, leveraging established PTAS machinery and extending across dimensions/noise models. This directly targets a central bottleneck in fault-tolerant quantum computing with clear integration into decoding pipelines and strong methodological credibility. Paper 2 is potentially exciting and application-relevant, but the abstract is less specific about formal guarantees, assumptions, and generality; its claims may depend on particular noise/intervention models. Overall, Paper 1 has clearer, broadly reusable impact.
Paper 2 likely has higher scientific impact because it demonstrates repeated, scalable toric-code error correction on a leading hardware platform (neutral atoms), including mid-circuit measurement, qubit loss replacement, and reservoir reloading—key practical milestones toward fault-tolerant quantum computing. Its real-world applicability and timeliness are high, and it can influence both experimental architectures and error-correction engineering broadly. Paper 1 is highly novel and rigorous theoretically (a PTAS for decoding), but its impact is more specialized and contingent on practical deployment within decoding stacks.
Paper 2 addresses a fundamental computational complexity question in quantum error correction—proving that minimum-weight decoding of 2D topological stabilizer codes admits a PTAS despite being NP-hard. This resolves an important theoretical gap with broad implications for fault-tolerant quantum computing, the central challenge of the field. The result is mathematically rigorous, generalizable beyond 2D, and connects classical approximation algorithms (Arora's framework) to quantum decoding. Paper 1, while experimentally valuable for quantum networking scalability, represents more of an engineering advancement. Paper 2's theoretical contribution has broader and longer-lasting impact across quantum computing and complexity theory.
Paper 1 likely has higher impact: it proves a PTAS for minimum-weight decoding across the broad class of 2D translationally invariant topological stabilizer codes and extends to certain higher-dimensional codes and realistic noise models (phenomenological/circuit-level), leveraging a general Arora-style framework. This breadth and applicability to fault-tolerant quantum computing and quantum memories increase cross-field relevance. Paper 2 is important but more specialized to the (6.6.6 planar) colour code and focuses on implications for that family, with similarly impractical polynomial factors.
Paper 1 addresses a foundational bottleneck in fault-tolerant quantum computing: decoding topological codes. By providing a polynomial-time approximation scheme for an NP-hard decoding problem and extending it to realistic circuit-level noise, it offers a major theoretical breakthrough with profound practical implications for building scalable quantum computers. While Paper 2 presents significant advancements in quantum metrology and dark matter detection, the widespread and critical need for efficient quantum error correction gives Paper 1 a broader and more transformative potential scientific impact across the entire quantum computing field.
Paper 1 resolves a fundamental complexity-theoretic question about decoding topological codes by establishing a PTAS for a problem recently shown to be NP-hard. This is a significant theoretical breakthrough with broad implications for fault-tolerant quantum computation, connecting classical approximation algorithms (Arora's framework) to quantum error correction. Paper 2 offers a valuable practical insight linking degeneracy to code-shortening and proposes improved decoders, but Paper 1's result is more foundational—it characterizes the computational complexity landscape of a core problem and applies broadly across topological codes and dimensions.
Paper 2 demonstrates the first fully-distributed GHZ state across a three-node quantum network of single atomic qubits, a key experimental milestone for quantum networking. It closes the detection loophole in distributed multipartite entanglement for the first time. This experimental breakthrough has broad impact across quantum computing, sensing, and communication, and represents tangible progress toward scalable quantum networks. While Paper 1 provides an elegant theoretical contribution (PTAS for decoding topological codes), its practical impact is somewhat limited since heuristic decoders already perform well in practice, and the PTAS constants may be impractical for real systems.
Paper 1 likely has higher impact: it provides a PTAS for an NP-hard decoding problem central to fault-tolerant quantum computing, with clear algorithmic/complexity novelty and direct relevance to near-term and long-term quantum hardware. The approach leverages Arora-style techniques and claims applicability beyond 2D to higher-dimensional codes and realistic noise models, broadening cross-field influence (quantum error correction, algorithms, complexity). Paper 2 is rigorous and extends quantum estimation theory, but is more specialized with narrower immediate applications and smaller breadth compared to decoding advances for scalable quantum computation.
Paper 1 presents a significant theoretical breakthrough by providing a polynomial-time approximation scheme (PTAS) for an NP-hard problem fundamental to fault-tolerant quantum computation (decoding topological codes). This methodological innovation, extending Arora's techniques to quantum error correction, offers broad and foundational impact. Paper 2, while providing valuable new quantum LDPC code constructions and empirical performance results, represents a more incremental advancement compared to the foundational algorithmic contribution of Paper 1.