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

• URL: http://arxiv.org/abs/2606.18145v1
• Date: Tue, 16 Jun 2026 16:44:08 GMT
• Title: A polynomial-time approximation scheme for minimum-weight decoding of topological codes
• Abstract summary: Two-dimensional topological translationally in (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation.<n>Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings.
• Score: 42.44256445495892
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes [0.0]
  We study the computational complexity of minimum-weight decoding for topological quantum codes.<n>For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding.
  arXiv  Detail & Related papers  (2026-08-17T20:37:08Z)
• High-threshold decoding of non-Pauli codes for 2D universality [0.15999407512883507]
  Topological codes have many desirable properties that allow fault-tolerant quantum computation with relatively low overhead.<n>A core challenge for these codes is to achieve a low-overhead universal gate set with limited connectivity.<n>We explore a non-Pauli stabilizer code that can be used to complete a universal gate set on topological toric and surface codes in strictly two dimensions.
  arXiv  Detail & Related papers  (2026-04-02T13:39:46Z)
• The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding [42.44256445495892]
  We show that minimum-weight decoding is NP-hard in three quintessential settings.<n>Our results highlight a sharp computational complexity separation between minimum-weight decoding and its approximate realizations.
  arXiv  Detail & Related papers  (2026-03-23T14:57:38Z)
• Optimal Quantum $(r,δ)$-Locally Repairable Codes From Matrix-Product Codes [52.3857155901121]
  We study optimal quantum $(r,delta)$-LRCs from matrix-product (MP) codes.<n>We present five infinite families of optimal quantum $(r,delta)$-LRCs with flexible parameters.
  arXiv  Detail & Related papers  (2025-08-05T16:05:14Z)
• Parallel Logical Measurements via Quantum Code Surgery [42.95092131256421]
  Quantum code surgery is a flexible and low overhead technique for performing logical measurements on quantum error-correcting codes.<n>We present a code surgery scheme, applicable to any qubit stabiliser low-density parity check (LDPC) code, that fault-tolerantly measures many logical Pauli operators in parallel.
  arXiv  Detail & Related papers  (2025-03-06T22:05:52Z)
• Decoding Quasi-Cyclic Quantum LDPC Codes [23.22566380210149]
  Quantum low-density parity-check (qLDPC) codes are an important component in the quest for fault tolerance. Recent progress on qLDPC codes has led to constructions which are quantumally good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice.
  arXiv  Detail & Related papers  (2024-11-07T06:25:27Z)
• SSIP: automated surgery with quantum LDPC codes [55.2480439325792]
  We present Safe Surgery by Identifying Pushouts (SSIP), an open-source lightweight Python package for automating surgery between qubit CSS codes. Under the hood, it performs linear algebra over $mathbbF$ governed by universal constructions in the category of chain complexes. We show that various logical measurements can be performed cheaply by surgery without sacrificing the high code distance.
  arXiv  Detail & Related papers  (2024-07-12T16:50:01Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Extracting topological orders of generalized Pauli stabilizer codes in two dimensions [5.593891873998947]
  We introduce an algorithm for extracting topological data from translation invariant generalized Pauli stabilizer codes in two-dimensional systems.<n>The algorithm applies to $mathbbZ_d$ qudits, including instances where $d$ is a nonprime number.
  arXiv  Detail & Related papers  (2023-12-18T13:18:19Z)
• Error-correcting codes for fermionic quantum simulation [4.199246521960609]
  We present methodologies for fermions via qubit systems on a two-dimensional lattice algorithm. We identify a family of stabilizer codes suitable for fermion simulation. Our method can increase the code distances without decreasing the (fermionic) code rate.
  arXiv  Detail & Related papers  (2022-10-16T01:43:07Z)
• Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders [77.34726150561087]
  We prove that the Restriction Decoder successfully corrects errors in the color code if and only if the corresponding toric code decoding succeeds. We numerically estimate the Restriction Decoder threshold for the color code in two and three dimensions against the bit-flip and phase-flip noise.
  arXiv  Detail & Related papers  (2019-05-17T17:41:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.