Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errors

• URL: http://arxiv.org/abs/2601.00972v1
• Date: Fri, 02 Jan 2026 19:43:06 GMT
• Title: Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errors
• Authors: Louay Bazzi,
• Abstract summary: We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent (X/Z) noise model.<n>We show that an (O(n3/2log n))-time decoder is achievable for surface and toric codes, improving over the (O(n2)) worst-case time of the standard approach.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study exact decoding for the toric code and for planar and rotated surface codes under the standard independent \(X/Z\) noise model, focusing on Separate Minimum Weight (SMW) decoding and Separate Most Likely Coset (SMLC) decoding. For the SMW decoding problem, we show that an \(O(n^{3/2}\log n)\)-time decoder is achievable for surface and toric codes, improving over the \(O(n^{3}\log n)\) worst-case time of the standard approach based on complete decoding graphs. Our approach is based on a local reduction of SMW decoding to the minimum weight perfect matching problem using Fisher gadgets, which preserves planarity for planar and rotated surface codes and genus~\(1\) for the toric code. This reduction enables the use of Lipton--Tarjan planar separator methods and implies that SMW decoding lies in \(\mathrm{NC}\). For SMLC decoding, we show that the planar surface code admits an exact decoder with \(O(n^{3/2})\) algebraic complexity and that the problem lies in \(\mathrm{NC}\), improving over the \(O(n^{2})\) algebraic complexity of Bravyi \emph{et al.} Our approach proceeds via a dual-cycle formulation of coset probabilities and an explicit reduction to planar Pfaffian evaluation using Fisher--Kasteleyn--Temperley constructions. The same complexity measures apply to SMLC decoding of the rotated surface code. For the toric code, we obtain an exact polynomial-time SMLC decoder with \(O(n^{3})\) algebraic complexity. In addition, while the SMLC formulation is motivated by connections to statistical mechanics, we provide a purely algebraic derivation of the underlying duality based on MacWilliams duality and Fourier analysis. Finally, we discuss extensions of the framework to the depolarizing noise model and identify resulting open problems.

Related papers

• Optimal Decoding with the Worm [4.970364068620607]
  We propose a new decoder for matchable'' qLDPC codes that uses a MarkovChain MonteCarlo algorithm.<n>The algorithm is applicable to decoding random errors for the surface code, the honeycomb Floquet code, and hyperbolic surface codes with constant rate.
  arXiv  Detail & Related papers  (2026-03-05T17:51:27Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Progressive-Proximity Bit-Flipping for Decoding Surface Codes [8.971989179518214]
  Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation. Existing decoders often fall short of meeting requirements such as having low computational complexity. We propose a novel bit-flipping (BF) decoder tailored for toric and surface codes.
  arXiv  Detail & Related papers  (2024-02-24T22:38:05Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• Comparative study of decoding the surface code using simulated annealing under depolarizing noise [0.6449786007855248]
  We find that the proposed Ising-based decoding approaches provide higher accuracy compared to the minimum-weight perfect matching (MWPM) algorithm for depolarizing noise. Our results are important for devising efficient and fast decoders feasible with quantum computer control devices.
  arXiv  Detail & Related papers  (2023-11-14T08:00:23Z)
• Deep Learning Assisted Multiuser MIMO Load Modulated Systems for Enhanced Downlink mmWave Communications [68.96633803796003]
  This paper is focused on multiuser load modulation arrays (MU-LMAs) which are attractive due to their low system complexity and reduced cost for millimeter wave (mmWave) multi-input multi-output (MIMO) systems. The existing precoding algorithm for downlink MU-LMA relies on a sub-array structured (SAS) transmitter which may suffer from decreased degrees of freedom and complex system configuration. In this paper, we conceive an MU-LMA system employing a full-array structured (FAS) transmitter and propose two algorithms accordingly.
  arXiv  Detail & Related papers  (2023-11-08T08:54:56Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  Communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. We propose Common Om REOm, which can be used to compress information transmitted between machines.
  arXiv  Detail & Related papers  (2023-09-23T08:45:27Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  We tackle a novel federated learning (FL) problem for optimizing a family of X-risks, to which no existing algorithms are applicable. The challenges for designing an FL algorithm for X-risks lie in the non-decomability of the objective over multiple machines and the interdependency between different machines.
  arXiv  Detail & Related papers  (2022-10-26T00:23:36Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• A Learning-Based Approach to Address Complexity-Reliability Tradeoff in OS Decoders [32.35297363281744]
  We show that using artificial neural networks to predict the required order of an ordered statistics based decoder helps in reducing the average complexity and hence the latency of the decoder.
  arXiv  Detail & Related papers  (2021-03-05T18:22:20Z)

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.