Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

• URL: http://arxiv.org/abs/2608.17109v3
• Date: Tue, 25 Aug 2026 08:28:35 GMT
• Title: Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the $4.8.8$ color code on the torus, there exists a constant $c>0$ such that no polynomial-time algorithm can always produce a solution whose weight is within $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $Ω(N^{1/18})$ gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT. Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.

Related papers

• Entropic Rigidity in Quantum Memories: How Geometry and Algebra Control the Onset of Degeneracy Corrections [4.226475360842309]
  We determine the first physical error weight $m$ at which their logical winner sets become disjoint.<n>The onset fixes the leading operational failure gap, proportional to the $m$th power of the physical noise strength.
  arXiv  Detail & Related papers  (2026-08-19T01:17:59Z)
• Quantum error correction at ultra-low overhead [0.0]
  Suppressing errors is the central challenge for useful large-scale quantum computing.<n>We introduce Cornucopia codes, a family of practical, hardware-efficient quantum low-density parity-check codes.<n>Results bring demonstrations of ultra-low overhead quantum error correction within the reach of near-term quantum processors.
  arXiv  Detail & Related papers  (2026-08-03T18:13:57Z)
• A polynomial-time approximation scheme for minimum-weight decoding of topological codes [42.44256445495892]
  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.
  arXiv  Detail & Related papers  (2026-06-16T16:44:08Z)
• 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)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks [18.20811830109862]
  We construct the first known quantum codes with linear dimension and distance supporting non-Clifford gates.<n>We design an efficient decoding algorithm for these codes.<n>Our results can be viewed as a new generalization of Prony's method for reconstructing a function from partial access to its transform.
  arXiv  Detail & Related papers  (2025-10-08T09:27:41Z)
• Demonstrating dynamic surface codes [118.67046728951689]
  We experimentally demonstrate three time-dynamic implementations of the surface code.<n>First, we embed the surface code on a hexagonal lattice, reducing the necessary couplings per qubit from four to three.<n>Second, we walk a surface code, swapping the role of data and measure qubits each round, achieving error correction with built-in removal of accumulated non-computational errors.<n>Third, we realize the surface code using iSWAP gates instead of the traditional CNOT, extending the set of viable gates for error correction without additional overhead.
  arXiv  Detail & Related papers  (2024-12-18T21:56:50Z)
• 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)
• The closed-branch decoder for quantum LDPC codes [0.0]
  Real-time decoding is a necessity for implementing arbitrary quantum computations on the logical level. We present a new decoder for Quantum Low Density Parity Check (QLDPC) codes, named the closed-branch decoder.
  arXiv  Detail & Related papers  (2024-02-02T16:22:32Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
  We show that for $q = pm$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time. On the other hand, classical algorithms can efficiently solve the problem only for much smaller inverse factors.
  arXiv  Detail & Related papers  (2022-10-20T19:35:50Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)

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.