Optimal Decoding with the Worm

• URL: http://arxiv.org/abs/2603.05428v1
• Date: Thu, 05 Mar 2026 17:51:27 GMT
• Title: Optimal Decoding with the Worm
• Authors: Zac Tobias, Nikolas P. Breuckmann, Benedikt Placke,
• Abstract summary: 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.
• Score: 4.970364068620607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new decoder for ``matchable'' qLDPC codes that uses a Markov-Chain Monte-Carlo algorithm -- called the \emph{worm algorithm} -- to approximately compute the probabilities of logical error classes given a syndrome. The algorithm hence performs (approximate) \emph{optimal} decoding, and we expect it to be computationally efficient in certain settings. The algorithm is applicable to decoding random errors for the surface code, the honeycomb Floquet code, and hyperbolic surface codes with constant rate, in all cases with and without measurement errors. The efficiency of the decoder hinges on the mixing time of the underlying Markov chain. We give a rigorous mixing time guarantee in terms of a quantity that we call the \emph{defect susceptibility}. We connect this quantity to the notion of disorder operators in statistical mechanics and use this to argue (non-rigorously) that the algorithm is efficient for \emph{typical} errors in the entire decodable phase. We also demonstrate the effectiveness of the worm decoder numerically by applying it to the surface code with measurement errors as well as a family of hyperbolic surface codes. For most codes, the matchability condition restricts direct application of our decoder to noise models with independent bit-flip, phase-flip, and measurement errors. However, our decoder returns \emph{soft information} which makes it useful also in heuristic ``correlated decoding'' schemes which work beyond this simple setting. We demonstrate this by simulating decoding of the surface code under depolarizing noise, and we find that the threshold for ``correlated worm decoding'' is substantially higher than for both minimum-weight perfect matching and for correlated matching.

Related papers

• Hierarchical quantum decoders [3.312392076411996]
  We propose a family of tunable quantum decoders with a trade-off between speed and accuracy.<n>This work bridges the gap between fast decodings and rigorous optimal decoding.
  arXiv  Detail & Related papers  (2026-01-29T13:42:58Z)
• Improved decoding algorithms for surface codes under independent bit-flip and phase-flip errors [0.0]
  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.
  arXiv  Detail & Related papers  (2026-01-02T19:43:06Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• 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)
• 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)
• Testing the Accuracy of Surface Code Decoders [55.616364225463066]
  Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC) This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
  arXiv  Detail & Related papers  (2023-11-21T10:22:08Z)
• Data-driven decoding of quantum error correcting codes using graph neural networks [0.0]
  We explore a model-free, data-driven, approach to decoding, using a graph neural network (GNN)<n>We show that the GNN-based decoder can outperform a matching decoder for circuit level noise on the surface code given only simulated data.<n>The results show that a purely data-driven approach to decoding may be a viable future option for practical quantum error correction.
  arXiv  Detail & Related papers  (2023-07-03T17:25:45Z)
• The END: An Equivariant Neural Decoder for Quantum Error Correction [73.4384623973809]
  We introduce a data efficient neural decoder that exploits the symmetries of the problem. We propose a novel equivariant architecture that achieves state of the art accuracy compared to previous neural decoders.
  arXiv  Detail & Related papers  (2023-04-14T19:46:39Z)
• 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)
• Improved decoding of circuit noise and fragile boundaries of tailored surface codes [61.411482146110984]
  We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes. Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC. We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
  arXiv  Detail & Related papers  (2022-03-09T18:48:54Z)
• Correcting spanning errors with a fractal code [7.6146285961466]
  We propose an efficient decoder for the Fibonacci code'; a two-dimensional classical code that mimics the fractal nature of the cubic code. We perform numerical experiments that show our decoder is robust to one-dimensional, correlated errors.
  arXiv  Detail & Related papers  (2020-02-26T19:00:06Z)

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.