Local Predecoder to Reduce the Bandwidth and Latency of Quantum Error Correction

A fault-tolerant quantum computer will be supported by a classical decoding system interfacing with quantum hardware to perform quantum error correction. It is important that the decoder can keep pace with the quantum clock speed, within the limitations on communication that are imposed by the physical architecture. To this end, we propose a local “predecoder,” which makes greedy corrections to reduce the amount of syndrome data sent to a standard matching decoder. We study these classical overheads for the surface code under a phenomenological phase-flip noise model with imperfect measurements. We find substantial improvements in the run time of the global decoder and the communication bandwidth by using the predecoder. For instance, to achieve a logical-failure probability of $f={10}^{-15}$ using qubits with physical error rate $p={10}^{-3}$ and a distance $d=22$ code, we find that the bandwidth cost is reduced by a factor of 1000 and that the time taken by a matching decoder is sped up by a factor of 200. To achieve this target failure probability, the predecoding approach requires a 50% increase in the qubit count compared with the optimal decoder.

Figure 1

(a) The distance-4 rotated surface code. Qubits are denoted by dashed or solid white circles. Periodic boundary conditions are enforced by identifying the dashed qubits along the top row with the qubits along the bottom row and identifying the dashed qubits along the right column with the qubits along the left column. Pauli-$X$–type (Pauli-$Z$–type) stabilizers are given by the product of Pauli-$X$–type (Pauli-$Z$–type) operators over white (shaded) squares. One stabilizer of each Pauli type is shown. The surface code encodes two logical qubits into the shared $(+1)$ eigenspace of the stabilizers. Logical operators are given by the product of Pauli operators around a nontrivial cycle and a Pauli-$X$–type logical operator is shown. The logical operators commute with all the stabilizers, implying that they have a nontrivial action that preserves the logical code space. (b) The decoding lattice used for decoding phase-flip noise and faulty $X$-type stabilizer measurements. Only two rounds of stabilizer measurement are shown, although for a distance-4 code, four rounds of stabilizer measurement would be required. The spacelike edges correspond to possible locations of phase-flip errors and the timelike edges correspond to possible locations of measurement errors. When an error occurs on an edge, whether timelike or spacelike, a pair of defects is created on the vertices contained in the boundary of the edge. A single phase-flip error is shown, as well as an extended stringlike error consisting of a phase-flip error and a measurement error. The stringlike error creates defects at its endpoints.

Figure 2

(a) The failure probability as a function of the code distance when the predecoder is used together with MWPM for a range of error rates. We observe that the failure probability decays exponentially in the code distance, indicating the presence of a threshold. (b) The gradients $m$ extracted from a linear fit $\log (f)=md$ of the decay of the failure probability, as a function of the physical error rate $p$. For small error rates ($p\lesssim {10}^{-3}$), we find that $m=k\log (p)$ for $k=0.33(1)$.

Figure 3

The defect density as a function of the error rate. The defect density determines the required bandwidth for transmitting syndrome information per unit area. When syndrome compression is used (green), the defect density scales linearly in the error rate. When the predecoder is also used (blue), the defect density scales quadratically in the error rate. The dotted green line corresponds to Eq. (5) and the dotted blue line corresponds to Eq. (6) with $V_0=57$. The bandwidth usage (red) associated with an uncompressed syndrome history is independent of the error rate. In order to make a fair comparison, we show the density of vertices in the syndrome history divided by 16. The factor of 16 assumes that addresses require 16 bits to transmit, whereas measurement data require only $1$ bit.

Figure 4

Histograms of the number of defects contained in a distance-20 syndrome history with predecoding (blue) and without predecoding (green): (a) $p=1\times {10}^{-5}$; (a) $p=1\times {10}^{-4}$; (c) $p=1\times {10}^{-3}$; (d) $p=5\times {10}^{-3}$. The solid blue and green lines correspond to the random variables described by Eq. (4) for $\overline{\rho }=p^2{V}_0$ and $\overline{\rho }=2p$, respectively. The histograms are normalized to have unit area.

Figure 5

For each error rate, we plot the constant of proportionality extracted from a fit of run time $T=A(p)V^2$, where $V$ is the space-time volume of the syndrome history and the run time is for the global matching part of the decoding scheme and is given in nanoseconds. For the blue trace, predecoding is used: the markers are data points and the dotted line is the fit $A(p)=A(V_{0}p/2{)}^2{p}^2$, for $A=1.4\times {10}^{-4}$. For the green trace, no predecoding is used: the markers are data points and the dotted line is the fit $A(p)=A{p}^2$ for the same $A=1.4\times {10}^{-4}$. In the inset, we demonstrate the goodness of the fit $T=A(p)V^2$ (red) to data (black) for the example case of no predecoding at error rate $p=2\times {10}^{-2}$.

Figure 6

The code distance (left axis) and number of qubits (right axis) required to reach a target logical-failure probability of $f={10}^{-15}$ when predecoding is used (blue) and when predecoding is not used (green). The distances are calculated by inverting Eq. (8) and using the ansätze in Eqs. (9)–(11). The dashed line marks $d=9$, below which predecoding performs comparably to pure MWPM. The inset shows the factor increase in the code distance (left axis) and the number of data qubits (right axis) required with predecoding compared to without predecoding. The dashed-dotted line denotes the expected behavior using Eq. (3) with $k=1/3$.

Figure 7

(a) The weight of the minimum weight failing error, as a function of the code distance. The dotted lines are analytic and are given by Eq. (9) for the case of predecoding (blue) or by $d/2$ for MWPM only (green). The data points are extracted as the gradients of linear fits of the log failure probability to the log error rate [see Eq. (8)]. (b) The multiplicity of least-weight failing errors as a function of the code distance. The data points are extracted as the intercepts of linear fits of the log failure probability to the log error rate [see Eq. (8)]. The dotted green line is a fit for MWPM of the form given in Eq. (11). The dotted blue line is a fit of the form $A(d)\sim 2^{6a-2+\alpha b}$, where $d=6a+b-2$ for non-negative integer $a$, non-negative integer $b<6$, and fitting parameter $\alpha$. When $b=0$, the scaling of $A(d)$ is described by Eq. (10) and this occurs here for distances $d=4,10,16$.

Figure 8

The effective MWPM code distance of the predecoding scheme as a function of error rate, plotted for code distances $d=4,6,8,10,12,14,16,18$. The straight horizontal lines are color coded to correspond to the data lines and provide the low-error-rate asymptotic behavior, as determined by the weight of the least-weight failing error and given by Eq. (9).

Figure 9

The isolation volume of the predecoder for $r=0,1,2$. The black balls correspond to vertices of the syndrome history and the sticks correspond to edges. For the cases $r=1$ and $r=2$, the red vertical stick depicts a measurement error that has occurred. Another error on any yellow stick will produce a defect that is within a distance $r$ from the defects produced by the measurement error and will lead to an error configuration that will not be corrected by the predecoder. Examples of such uncorrectable error configurations are shown in red. In this case, four defects will be left behind in the syndrome history. By counting the yellow sticks, we determine $V_1=57$ and $V_2=163$. The $r=0$ case requires special treatment. We again have a red vertical stick depicting a measurement error and yellow sticks represent sites of possible errors that would result in error configurations that are not fully corrected by the predecoder. However, the mechanism by which this occurs is slightly different and at the bottom left we show an error configuration that cannot be fully cleaned up by the predecoder. The predecoder attempts to place a correction between all neighboring defects, shown in blue at bottom center; however, this introduces a correction at a site at which there was no error initially, shown at bottom right. As such, two defects remain in the syndrome history. In this case, we have $V_0=V_1=57$ but since here most weight-2 errors result in only two defects left in the lattice, we have that Eq. (A5) contains an additional factor of $2$ as compared to Eq. (6).

Figure 10

The defect density associated with predecoders for $r=0,1,2,3,5$. The black dashed line corresponds to MWPM only with syndrome compression. The markers are data points and the dotted lines correspond to Eq. (6) for $r=0$ and to Eq. (A5) for $r>0$, where $V_r$ is determined by Eq. (A4). All predecoders exhibit bandwidth scaling with $p^2$ for sufficiently low-error rates. The vertical lines can be traced to the bottom axis to determine the error rate at which bandwidth savings take effect for a given $r$.

Figure 11

The code distance (left axis) and number of qubits (right axis) required to reach a target logical-failure probability of $f={10}^{-15}$ for predecoders of radius $r=0,1,2,\mathrm{\infty }$, where $r=\mathrm{\infty }$ indicates that no predecoding is performed. The distances are calculated by inverting Eq. (8) and using the ansatz in Eq. (A6) along with an ansatz similar to that described in Fig. 7 for the multiplicities. These ansätze are linear fits to the logical-failure probability at low error rates. The dashed lines are color coded and for each predecoding radius $r$, they mark the maximum distance such that $w_{\mathrm{pre},r}(d)=d/2$. For distances smaller than this, the predecoder of radius $r$ is expected to perform comparably to pure MWPM. The inset shows the factor increase in the code distance (left axis) and the number of data qubits (right axis) required with predecoding compared to without predecoding. The dashed-dotted lines are color coded and mark the expected behavior using Eq. (3) with $k=(\tilde{r}+1)/(\tilde{r}+2)$.