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.

enter image description here

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!}$


1 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

enter image description here

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.

  • $\begingroup$ Thank you for your answer. I am back on surface code learning and I give you a feedback in a few days. $\endgroup$ Commented Jan 19, 2022 at 17:03
  • 1
    $\begingroup$ Cool! I appreciate feedback and am happy to clarify things further :-) $\endgroup$ Commented Jan 19, 2022 at 17:10
  • $\begingroup$ Thanks for the answer. I am having trouble to understand "All error chains shorter than $d_e=(d+1)/2$ are correctly identified by the decoder" in the most general case. To understand my confusion: I assume a chain of $X$-error necessarily being horizontal (to simplify). I consider in my explanation the illustration of your answer. If the chain happens on an odd horizontal line, then the syndrome will be detected on the boundary of this chain. A given syndrome can be due to either a chain or its complementary. Hence, if the chain is smaller than $(d+1)/2$ I can correct it for sure. $\endgroup$ Commented Jan 20, 2022 at 18:16
  • $\begingroup$ However, if it happens to an even horizontal line, the error will not provide syndrome on its edge only but on "many" $Z$ stabilizers. And when considering those cases I don't follow anymore the proof (and it gets even more spicy if the chain goes in two directions (it starts horizontally then goes vertically). Could you elaborate on those cases? If they are not considered as being chain of errors, why would that be the case? Actually that was my main confusion I think. Then I guess I could start to understand the detailed derivation. $\endgroup$ Commented Jan 20, 2022 at 18:18
  • 1
    $\begingroup$ (i) It's double because for each of the $(d-1)^2$ internal qubits there are two possible paths, one making a step "up" and the other making a step "down". (ii) The decoder could apply random guessing to choose between $E$ and $F$. Since there are two possibilities it then succeeds half the time. $\endgroup$ Commented Jan 25, 2022 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.