Source-linked AI summary
Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel
Nicolas Delfosse, Gilles Zémor
TL;DR
Fast decoding is essential to limit error accumulation during computation. This paper uses spanning forests to construct a linear-time maximum-likelihood decoder for surface-code erasures, with a guarantee for bounded-degree codes with bounded-size faces.
Problem
Fast decoding is essential to avoid error accumulation during computation, and shorter intervals between correction rounds induce fewer errors.
Source: p. 1Method
The decoder finds a most-likely error coset from the erasure pattern and syndrome, using a spanning-forest algorithm on the code graph and its dual.
Source: p. 2Results
For surface codes with bounded degree and bounded face size, applying the algorithm to the graph and its dual produces a linear-time maximum-likelihood decoder.
Source: p. 3Takeaways & Limitations
The decoder applies to surface codes of arbitrary genus and boundary type, including hyperbolic codes.
Source: p. 1
Abstract
from arXiv · showhide
Surface codes are among the best candidates to ensure the fault-tolerance of a quantum computer. In order to avoid the accumulation of errors during a computation, it is crucial to have at our disposal a fast decoding algorithm to quickly identify and correct errors as soon as they occur. We propose a linear-time maximum likelihood decoder for surface codes over the quantum erasure channel. This decoding algorithm for dealing with qubit loss is optimal both in terms of performance and speed.