4
$\begingroup$

I am starting to learn how decoders work for surface code and I need to understand some of the basics. For this reason, I ask the questions $Q1$ to $Q4$ written below (they are all strongly related).

My main reference to learn is this paper. I assume that the noise model is such that errors occur independently on the data qubits only. Each data qubit has a probability $p$ to have an $X$-error and a probability $p$ to have a $Z$ error.

In all that follows, I assume that we correct $X$ and $Z$ errors independently (I first correct $X$ errors, then $Z$ errors). In the explanations, I will focus on correcting a single type of errors ($X$ errors for instance).

Common to all decoders

The job of a decoder is, given a syndrome $S$ caused by an error $E$, to apply a correction $C(S)$ that will fix the error $E$. The difference between decoders is solely contained in the function $C(S)$ (which correction should I apply given the syndrome). Q1: Would you agree?

Minimum Weight Perfect Matching (MWPM)

For MWPM, $C(S)$ will correspond to apply one chain of bit-flips (I focus on correcting $X$ errors here) that (i.1) will fix the syndrome, (ii.1) has the minimum weight possible. Q2: Would you agree? In the case different solutions having the same (minimum) weight are possible, do we choose randomly one of them?

Maximum likelihood

The Maximum likelihood is more efficient than MWPM in the sense that it will apply a chain of bit-flips that (i.2) will fix the syndrome, (ii.2) will have the highest probability to fix the logical error.

What I would like to understand is why (ii.1) and (ii.2) are different: for this purpose I drawed some examples below.

The image below represents a distance 3 surface code. The black circles are the syndrome ancilla qubits, the white circles are the data qubits. The red circles are syndrome qubits that detected an error.

enter image description here

In the following two images, I show the two possible minimum weight that might have caused this error. The MWPM will assume either one of them occured and fix it by applying an $X$ operator on the associated data qubit. In practice, in this case, it doesn't matter which error actually occurred as the post-recovery state will be the same up to a stabilizer operation.

enter image description here

enter image description here

In the following three images, I show other possible events of higher weight that might have caused the same syndrome (more events than the one I show could occur but let's keep the example simple). The first image occur with a probability of order $p^4$ and the two lasts with a probability of order $p^5$.

enter image description here enter image description here enter image description here

In the case I assume the first of these three images is the error that occured while it was actually the second or third, the "mistake" I would do would only introduce a net stabilizer operation on the surface (so I don't care).

My question:

With this simple example, we see that the MWPM would fix an error occuring with a probability $2p^2$ while the maximum likelihood would fix an error occuring with a probability $p^4+2p^5$. A "naïve" asymptotic estimate would tell me that MWPM is the best, but actually in some cases $p^4+2p^5>2p^2$ (it depends on the actual value of $p$).

Q3: Is the discussion provided in this last paragraph the correct intution to understand why MWPM and maximum likelihood are different?

Q4: How is the syndrome to apply precisely defined for maximum likelihood? Should I solve the following problem?

I call $S$ a syndrome. I call $\mathcal{E}(S)$ the set of errors compatible with this syndrome. In some cases, being wrong about the error that actually occured is not an issue. For instance if an error $E_1$ occured while I believe that the error was actually $E'_1=g E_1$, where $g$ is a stabilizer, applying $E'_1$ as a recovery will still provide a correct correction.

I should acknowledge that fact when applying a recovery. For this purpose, I must split $\mathcal{E}(S)$ in a family of sets $\{\mathcal{E}_i(S)\}_i$ such that two different errors in any $\{\mathcal{E}_i(S)\}_i$ only differ by a stabilizer operation.

The maximum likelihood computes the probability to have an error in $\mathcal{E}_i(S)$. I call this probability $p(\mathcal{E}_i(S))$. Then, it looks at which $\mathcal{E}_i(S)$ is associated to the largest $p(\mathcal{E}_i(S))$ and it applies any element in $\mathcal{E}_i(S)$ in order to fix the error.

Note: the definition is provided in this reference but I was struggling to understand it. This is why I tried to provide my own definition (and I would like to see if you agree with me?... or not!)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
+100
$\begingroup$

The job of a decoder is, given a syndrome 𝑆 caused by an error 𝐸 , to apply a correction 𝐶(𝑆) that will fix the error 𝐸 . The difference between decoders is solely contained in the function 𝐶(𝑆) (which correction should I apply given the syndrome). Q1: Would you agree?

A1: Nearly. When you say "fix the error $E$", really what the decoder needs to do is to apply a correction $C(S)$ so that $E * C(S)$ is itself a stabilizer. This is in contrast to the more demanding condition that $E * C(S)$ is the identity operator.

For MWPM, 𝐶(𝑆) will correspond to apply one chain of bit-flips (I focus on correcting 𝑋 errors here) that (i.1) will fix the syndrome, (ii.1) has the minimum weight possible. Q2: Would you agree? In the case different solutions having the same (minimum) weight are possible, do we choose randomly one of them?

A2: Again, if by "fix the syndrome" you mean apply a correction $C(S)$ so that $E * C(S)$ is itself a stabilizer, then yes I agree. To your second question, typically when people refer to a minimum-weight solution, it is allowed to be any of the possibly many minimum weight solutions. Which you choose will likely depend on the implementation of your decoder. However, there have been decoder proposals that take the multiplicity of particular minimum-weight solutions into account (see e.g. Section III here).

Q3: Is the discussion provided in this last paragraph the correct intuition to understand why MWPM and maximum likelihood are different?

A3: No. First of all, every configuration from picture 2 through 6 is an equivalent correction. They are all the same correction up to a stabilizer operation.

The maximum-likelihood decoder is defined to be the decoder that returns the most likely class of corrections. This is frequently also the class containing the minimum-weight correction, but not always.

Q4: How is the syndrome to apply precisely defined for maximum likelihood? Should I solve the following problem?

A4: Yes I think so, but I'm going to just say it in words because the subscript notation confuses me a bit. Fix any logical-Z operator $Z_L$. For bit-flip errors, determine the set of all errors that could have produced the syndrome you see. Then, you divide that set into two subsets - those that commute $Z_L$ and those that don't. Add up all the probabilities of the errors of each subset, and choose any correction from the subset with the higher probability. By contrast, MWPM chooses the subset with the maximum probability element, rather than the subset with the overall maximum probability. Although, these frequently end up being the same, especially in the limit of low $p$.

In the pictures you've drawn, I'd be adding up all the contributions of each of those errors and grouping them into one error class... but there are many more to count. An example of an error from the opposite class would be an error that matches the red circles to opposite boundaries.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the answer. Points A1 & A2: Yes I agree, thanks! Point A3: Right, I missed the equivalence between some of the picture. I am still confused by A3 though: let's assume that MWPM tries to fix an error by applying a correction of minimal weight. I assume this correction belongs to an equivalent class of corrections $S_1$. In some case, it might be that a correction of larger weight, belonging to another class $S_2 \neq S_1$ will be more likely to be successfull because of combinatorial factors. $\endgroup$
    – Marco Fellous-Asiani
    Mar 13 at 22:54
  • $\begingroup$ An analogy: if I have two errors among $N$ possibilities, the probability will be $p_2=\binom{N}{2} p^2(1-p)^{N-2}$, but three errors among $N$ possibilities reads $p_3=\binom{N}{3} p^3(1-p)^{N-3}$. For "low enough" $p$, two errors is more likely, but in general one should really compare $p_3$ and $p_2$. For instance, the class $S_2$ in my example would only be composed of higher weight event, but there are much more of them because of combinatorial factors, meaning that an event in $S_2$ is in the end more likely? Does this explanation convey the good physics? $\endgroup$
    – Marco Fellous-Asiani
    Mar 13 at 22:54
  • $\begingroup$ To clarify for what I call class of correction $S_1$ and $S_2$. Any two corrections in $S_1$ will only differ by a stabilizer operation (same for $S_2$). But a correction in $S_1$ and a correction in $S_2$ will differ by an element that is not a stabilizer. $\endgroup$
    – Marco Fellous-Asiani
    Mar 13 at 23:04
  • 1
    $\begingroup$ If I understand you correctly, then yes. In this toy example, the minimum-weight decoder will always choose $S_1$, but the maximum-likelihood decoder will only choose $S_1$ if $p_2 > p_3$, otherwise it will choose $S_2$. $\endgroup$
    – squiggles
    Mar 14 at 6:02
  • $\begingroup$ Thanks! I guess you meant that maximum likelihood will only choose S1 if $p_2<p_3$ (which might often be the case, but not always) $\endgroup$
    – Marco Fellous-Asiani
    Mar 15 at 12:59

Your Answer

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

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