Cellular-Automaton Decoders with Provable Thresholds for Topological Codes

We propose a new cellular automaton (CA), the sweep rule, which generalizes Toom’s rule to any locally Euclidean lattice. We use the sweep rule to design a local decoder for the toric code in $d\ge 3$ dimensions, the sweep decoder, and rigorously establish a lower bound on its performance. We also numerically estimate the sweep decoder threshold for the three-dimensional toric code on the cubic and body-centered cubic lattices for phenomenological phase-flip noise. Our results lead to new CA decoders with provable error-correction thresholds for other topological quantum codes including the color code.

Figure 1

(Inset) The failure probability $p_{\mathrm{fail}}(p,L)$ of the sweep decoder for the 3D toric code on the bcc lattice $\mathcal{L}$ after $N_{\mathrm{cyc}}=2^8$ correction cycles, where $p$ is the phase-flip error rate and $L$ is the linear size of $\mathcal{L}$. We estimate the threshold $p_{\mathrm{th}}(N_{\mathrm{cyc}})\approx 1.055\%$ from the crossing point of different curves. (Main) We find the sustainable threshold $p_{\mathrm{sus}}^{\mathrm{bcc}}=0.99\pm 0.02\%$ by fitting the numerical ansatz from Eq. (10) to the data.

Figure 2

(a) At time $T$, the spin $s_C^{(T)}=-1$ (green face) differs from its neighbors to the east $s_E^{(T)}=1$ and north $s_N^{(T)}=1$ (red faces). According to Eq. (1), Toom’s rule sets $s_C^{(T+1)}=1$. (b) A 2D lattice built of three types of parallelograms. A domain wall (red) cannot be removed by repeated application of a naive generalization of Toom’s rule. (c) The 3D toric code on the bcc lattice [39] has qubits on faces and $X$ stabilizers associated with edges. Any configuration of $Z$ errors (green) results in a 1D looplike $X$ syndrome (red).

Figure 3

(a) Vertices $u$ and $v$ are connected by a path ($u$: $v$) (red), but there is no causal path between them; $v$ and $w$ are connected by a causal path ($v\updownarrow w$ (blue). We shaded in green and blue the future $\uparrow (v)$ and past $\downarrow (v)$ of $v$. (b) The causal diamond $\diamond (V)$ (blue) of a subset of vertices $V=\{v_1,v_2,v_3,v_4\}$ is defined as the intersection of the future of the infimum of $V$ with the past of the supremum of $V$. (c) The sweep rule is defined for every vertex and locally updates $\pm 1$ spins on neighboring faces. Since the vertex $v$ is trailing (see below), spins on two green faces will be flipped.

Figure 4

For each trailing vertex $v$ (black) at time $T=1$, 2, 3, the sweep rule finds a subset $\phi (v)$ of neighboring faces (green) in the future $\uparrow (v)$, whose boundary ${\partial }_2\phi (v)$ locally matches the domain wall ${\sigma }^{(T)}$ (red), i.e., $[{\partial }_2\phi (v)]{|}_v={\sigma }^{(T)}{|}_v$. Flipping spins in $\phi (v)$ pushes ${\sigma }^{(T)}$ away from $v$ in the sweep direction $\overrightarrow{t}$. Note that $\phi (v)$ and ${\sigma }^{(T)}$ are always in the causal diamond $\diamond ({\sigma }^{(1)})$ (blue) of the initial domain wall ${\sigma }^{(1)}$.