Struggle to understand the derivation of the probability of logical error per surface code cycle

Question

I am following this introduction paper for the surface code theory.

The question:

I am struggling to understand the derivation of the equation (12) of this paper. This equation gives the probability of having an $X_L$ (logical $X$) error for a protected logical qubit after one surface code cycle.

The result is:

$$P_L^s=d \frac{d!}{(d_e-1)!d_e!}p_e^{d_e}.\tag{12}$$

Where $d$ is the array distance, and $d_e=(d+1)/2$.

What I understand:

Let me start by what I understand. In the paper they provide an example of what can cause a logical error. Below is the image the discussion is based on.

As illustrated in (a), the first and third $Z$ measurement qubits are detecting an error. It could be due to an $X$ error on the second and third data qubits (on (b), I call this error $X_2 X_3$), or to an $X$ error to the first and two last data qubits as represented on (c) (I call this error $X_1 X_4 X_5$). Conceptually we cannot know.

However, the situation in (b) is more likely to occur and hence we will assume it is the case. In this case we can apply the $X$ operator on the second and third data qubit and it will fix the error. Now, if actually the situation in (c) occured, such correction would induce a logical $X$ error. Indeed we would apply $X_2 X_3$ (to correct what we believed occured) where an error $X_1 X_4 X_5$ is the one that actually occured. In the end it means that the "net" effect is $X_1 X_2 X_3 X_4 X_5$ which is a logical $X$ operator: hence it introduces a logical error.

I am fine with this example.

Where I struggle to understand:

My struggle start on the precise counting, and generalization of this example on a full surface. The probability to have a logical error is the probability to face an uncorrectable event (such as the example (c) before). Then we have to answer two questions:

1. What characterizes an uncorrectable event?
2. How much of those events can occur?

I am struggling to understand the answer to those two questions. In the paper they answer the following (I reformulate what I believe they say in my own words).

1. For arrays with distance $d$, an uncorrectable event will occur when $(d+1)/2$ qubits errors are mis-identified as $(d-1)/2$ qubits error. Actually there might have more possibilities than that, but such possibilities are the one giving the highest probability of error (we neglect the rest).
2. The precise counting of these possibilities gives for a 2D array: $d \frac{d!}{(d_e-1)!d_e!}$.

In the particular example of the 1D array here, I agree that $(d+1)/2$ qubits errors were misidentified as $(d-1)/2$ qubits error. But why would it be a general result? How can I be sure of that?

Assuming the point 1. is correct, I don't understand how we end up with the factor $d \frac{d!}{(d_e-1)!d_e!}$

Answer 1

Lowest order approximation of logical error

We can generalize equation $(12)$ as follows

$$ P_L=\sum_{k=1}^\infty N(k)p_e^k\tag{a} $$

where $P_L$ is the probability of a logical error, $N(k)$ is the number of error chains of weight $k$ which are misidentified by the decoder and $p_e$ is the probability of an error on a physical data qubit$^1$. All error chains shorter than $d_e=(d+1)/2$ are correctly identified by the decoder, so $N(k)=0$ for $k<d_e$. Also, there are only $D=d^2+(d-1)^2$ data qubits so $N(k)=0$ for $k>D$. Therefore, we can rewrite $(a)$ as

$$ P_L=\sum_{k=d_e}^{D} N(k)p_e^k\tag{b}. $$

For $p_e$ sufficiently small, we may neglect all terms in $(b)$ except the one with the smallest power of $p_e$, obtainig the estimate

$$ P_L\approx P_L^s=N(d_e)p_e^{d_e}\tag{c}. $$

Error misidentification

We will now compute $N(d_e)$. Let $E$ denote an error chain of length $d_e$ which is misidentified by the decoder. The input for the decoder is the syndrome $S=\partial E$ where $\partial E$ denotes the boundary, i.e. the set of endpoints, of the chain $E$. Misidentification occurs when the decoder outputs a chain $F$ which is complementary to $E$, i.e. such that $\partial F=S$ and the chain $E+F$ connects opposite boundaries of the lattice. Assuming that the decoder always returns the lowest weight chain - as is for example the case for minimum-weight perfect matching decoders - we have that $|F|\le |E|=d_e$. Moreover, by complementarity $|E|+|F|\ge d=2d_e-1$. Therefore, $d_e-1\le|F|\le d_e$.

Consider first the case $|F|=d_e-1$. Since $|E|+|F|=d_e+d_e-1=d$ we see that in this case $E+F$ is a straight path along one of the lattice rows. There are $d$ rows and for each row there are ${d\choose d_e}$ ways of choosing data qubits in $E$. Therefore, this case includes

$$ N_1(d_e)=d{d \choose d_e}=d\frac{d!}{(d_e-1)!d_e!}\tag{d} $$

error chains.

Consider next the case $|F|=d_e$. Since this time $|E|+|F|=d+1$ the path consists of two straight segments connected by a single vertical step to an adjacent row. The shape of each such path is uniquely determined by one of the data qubits comprising the "internal" $(d-1)\times(d-1)$ sublattice and a boolean value indicating whether the left end of the path is above or below the right end. In figure $3$ on page $9$ in the paper

the internal sublattice consists of data qubits corresponding to the white circles at the ends of horizontal arms of the yellow ($X$) operators. Thus, there are $2(d-1)^2$ ways to place $E+F$ on the lattice. Since $|E|=|F|=d_e$, we assume that the decoder misidentifies the error chain half$^2$ the time. Therefore, this case includes

$$ N_2(d_e)=(d-1)^2{d+1 \choose d_e}=(d-1)^2\frac{(d+1)!}{d_e!d_e!}=2(d-1)^2\frac{d!}{(d_e-1)!d_e!}\tag{e} $$

error chains. Combining the two cases, we get

$$ N(d_e)=N_1(d_e)+N_2(d_e)=(2d^2-3d+2)\frac{d!}{(d_e-1)!d_e!}.\tag{f} $$

Dependence on decoding algorithm

Note that the analysis depends on our assumptions about the decoder. In particular, we assumed above that confronted with a syndrome $S$ that could be explained by either of two complementary paths of the same length $d_e$, our decoder makes a misidentification half the time. Had we assumed that the decoder always handles this case correctly we would have obtained

$$ N(d_e)=N_1(d_e)=d\frac{d!}{(d_e-1)!d_e!}\tag{g} $$

in agreement with equation $(12)$ in the paper. Both analyses agree on the scaling behavior of $P_L$ with respect to $p_e$. Since the express goal of section VII A is the statistical explanation of the scaling behavior in equation $(11)$, the more detailed analysis here confirms that the simplifying assumption about the decoder in the paper does not affect the conclusion.

---

$^1$ As stated on page $12$ in the paper, the analysis considers only data qubit errors and neglects other errors such as those arising in syndrome measurement circuits.

$^2$ This is probably a pessimistic assumption.