Efficient algorithms for maximum likelihood decoding in the surface code

We describe two implementations of the optimal error correction algorithm known as the maximum likelihood decoder (MLD) for the two-dimensional surface code with a noiseless syndrome extraction. First, we show how to implement MLD exactly in time $O\left(n^2\right)$, where $n$ is the number of code qubits. Our implementation uses a reduction from MLD to simulation of matchgate quantum circuits. This reduction however requires a special noise model with independent bit-flip and phase-flip errors. Secondly, we show how to implement MLD approximately for more general noise models using matrix product states (MPS). Our implementation has running time $O\left(n{\chi }^3\right)$, where $\chi$ is a parameter that controls the approximation precision. The key step of our algorithm, borrowed from the density matrix renormalization-group method, is a subroutine for contracting a tensor network on the two-dimensional grid. The subroutine uses MPS with a bond dimension $\chi$ to approximate the sequence of tensors arising in the course of contraction. We benchmark the MPS-based decoder against the standard minimum weight matching decoder observing a significant reduction of the logical error probability for $\chi \ge 4$.

Figure 1

Distance-3 surface code. Solid dots, stars, and diamonds indicate locations of qubits, site stabilizers, and plaquette stabilizers, respectively. Stabilizers located near the boundary act only on three qubits. The distance-$d$ surface code has $d^2$ qubits on horizontal edges, ${(d-1)}^2$ qubits on vertical edges, and $d(d-1)$ stabilizers of each type.

Figure 2

Logical Pauli operators $\overline{X}$ (left) and $\overline{Z}$ (right).

Figure 3

Partition of edges into “horizontal” columns $H^1,...,H^d$ and vertical columns $V^1,...,V^{d-1}$. Every edge is identified with the respective code qubit (solid dot).

Figure 4

Computing the coset probabilities for the $X$-noise model is equivalent to computing the matrix element $\langle {\psi }_e\left|\widehat{U}\right|{\psi }_e\rangle$, where $\widehat{U}$ is a quantum circuit on $d$ qubits shown above and ${\psi }_e$ is the superposition of all even-weight $d$-bit strings. The above example is for $d=3$. Each gate depends on a parameter $w_e$ defined in Eq. (7).

Figure 5

Restriction of a stabilizer $g(\alpha ;\beta )$ onto the edge $e$ depends only on the variables ${\alpha }_{u\left(e\right)}$, ${\alpha }_{v\left(e\right)}$ and ${\beta }_{p\left(e\right)}$, ${\beta }_{q\left(e\right)}$.

Figure 6

Extended surface code lattice for $d=3$. Locations of stabilizers are represented by $s$ nodes. Code qubits located on horizontal and vertical edges of the original lattice are represented by $h$ nodes and $v$ nodes, respectively. In general, the extended lattice has dimensions $(2d-1)\times (2d-1)$.

Figure 7

Partition of the extended lattice into “horizontal” columns $H^1,...,H^d$ and “vertical” columns $V^1,...,V^{d-1}$ (here $d=3$).

Figure 8

$X$ noise: exact implementation of the ML decoder. The data suggest that the threshold error rate ${\epsilon }_0$ is between $10.9\%$ and $11\%$, which is in a good agreement with the estimate ${\epsilon }_0=10.93\left(2\right)$ of Ref. [24] which calculated the phase-transition point in the respective spin model. Each curve has data points at error rates $\epsilon =10.4,10.5,...,11.3\%$. To compute the logical error probability, at least 5000 failed error correction trials have been accumulated for each data point.

Figure 9

$X$ noise: exact and approximate implementations of the ML decoder. Logical error probability as a function of the error rate $\epsilon$ is shown. The curves representing the exact MLD and MPS decoders with $\chi =6,8$ are too close to be distinguishable on the main plot. The red curve represents the standard minimum weight matching decoder. The inset shows “badness” of various decoders as a function of the error rate. We define the badness as the ratio between logical error probabilities of a given decoder and the optimal decoder (MLD). Each curve has data points at error rates $\epsilon =5,5.5,6,...,11\%$. To compute the logical error probability, at least 1000 failed error correction trials have been accumulated for each data point.

Figure 10

Depolarizing noise: logical error probability of the MPS decoder with $\chi =6$ as a function of the code distance $d$ for a fixed error rate $\epsilon =10,12,14\%$. To compute the logical error probability, at least 1000 failed error correction trials have been accumulated for each data point.

Figure 11

Depolarizing noise: logical error probability of the MPS decoder with $\chi =6$ as a function of the error rate $\epsilon$. Assuming a nonzero error threshold ${\epsilon }_0$, the data suggest that $17\%\le {\epsilon }_0\le 18.5\%$. To compute the logical error probability, at least 5000 failed error correction trials have been accumulated for each data point.

Figure 12

Depolarizing noise: approximate implementations of the ML decoder. Logical error probability as a function of the error rate $\epsilon$ is shown. The red curve represents the minimum weight matching decoder. The inset shows “badness” of various decoders as a function of the error rate. We define the badness as the ratio between logical error probabilities of a given decoder and the best decoder (MPS decoder with $\chi =8$). Each curve has data points at error rates $\epsilon =9,10,...,20\%$. To compute the logical error probability, at least 1000 failed error correction trials have been accumulated for each data point.