Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel

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.

Figure 1

(a) A square lattice of the torus. Red thick edges mark the set $\mathcal{E}$ of erased qubits which support some $Z$ error. Its syndrome is indicated by large red nodes. (b) A spanning forest $F_{\mathcal{E}}$ [thick red lines in (b)] is constructed. Then, starting from the leaves, an error included in the $F_{\mathcal{E}}$ is constructed using the syndrome. This provides a correct estimation of the error up to a stabilizer.

Figure 2

(a) Surface code with boundaries. White nodes and dashed lines represent open vertices and open edges. (b) Red thick lines indicate an erasure $\mathcal{E}$ with a $Z$ error and its syndrome given by the large red vertices. (c) A spanning forest $F_{\mathcal{E}}$, with open vertices as a seed. Arrows show the way the forest is grown. (d) The error is estimated by reversing the arrows.

Figure 3

Monte Carlo simulation of the peeling decoder for (a) the 2D toric code and (b) the 3D toric code. Each data point is obtained from ${10}^5$ decoding trials.