Fast Decoders for Topological Quantum Codes

We present a family of algorithms, combining real-space renormalization methods and belief propagation, to estimate the free energy of a topologically ordered system in the presence of defects. Such an algorithm is needed to preserve the quantum information stored in the ground space of a topologically ordered system and to decode topological error-correcting codes. For a system of linear size $\ell$, our algorithm runs in time $\log \ell$ compared to ${\ell }^6$ needed for the minimum-weight perfect matching algorithm previously used in this context and achieves a higher depolarizing error threshold.

Figure 1

Simple defect patterns illustrating the importance of the entropic term or error degeneracy (left) and correlations of errors (right).

Figure 2

The 12 qubits that constitute a code block in the concatenation approximation. They form a surface code. Dashed links represent qubits shared between blocks.

Figure 3

Failure probability as a function of bit-flip probability $p$ for a $\ell =8,16,32,\dots ,1024$ toric code decoded using the $2\times 1$ block RG algorithm with 3 belief propagation rounds. Each data point is ${10}^4$ trials.

Figure 4

Failure probability as a function of depolarizing strength $p$ for a $\ell =16$, 32, 64, and 128 toric code decoded using the $2\times 2$ subcode RG algorithm with three rounds of belief propagation with prior physical decoding.