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.
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.
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$.
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!)