# is the minimum weight perfect matching decoder optimal

The toric code and other popular codes can be decoded using minimum weight perfect matching. Is this an optimal decoder? Here by optimal, I mean it gives the best logical error rate vs physical error rate performance in depolarizing channel. "Threshold" is often used to characterize toric codes, does that assume optimal decoding or a particular type?

Is [minimum weight perfect matching] an optimal decoder?

No, it's not optimal. For example, it uses the weight of the shortest path between two detection events as an approximation for the contributions of all topologically equivalent paths. An optimal decoder would exactly compute the contributions of all possible errors consistent with the symptoms, instead of focusing on the most likely one.

"Threshold" is often used to characterize toric codes, does that assume optimal decoding or a particular type?

Thresholds are always relative to a decoder. And ideally that decoder is something that runs in polynomial time, instead of a hypothetical optimal decoder which likely takes exponential time.

• It makes perfect sense that performance and threshold are decoder dependent. Unfortunately I see a lot of papers refer to "the threshold of the code" without reference to the decoding algorithm. Oct 18, 2021 at 18:30
• @unknown Oh it's even worse than that. They all refer to different error models too. Sometimes it's just single qubit depolarizing noise between rounds, sometimes there's no measurement errors sometimes there isn't, sometimes it's full circuit noise, sometimes a single qubit depolarization error that triggers picks randomly between {I,X,Y,Z} and sometimes it picks between {X,Y,Z}. You can find papers saying the surface code threshold is ~1% and other papers saying it's ~10% and neither is "wrong". Oct 18, 2021 at 18:42
• @CraigGidney could you please explain - if the optimal decoder would compute all errors consistent with the symptoms, how would it know when one to choose?
– Lior
Feb 8, 2022 at 19:21
• @Lior An optimal decoder would perform exact Bayesian inference of the equivalence class of errors given the observed detection events. It's not necessary to know specifically which errors occurred, only which equivalence class they are from. The equivalence classes are defined by which logical observables are flipped, so you only have two bits to predict per logical qubit (X obs flipped and Z obs flipped). Feb 8, 2022 at 19:52
• I think your answer BTW is strongly related to this question, not sure if you saw it - if you could take a look, it would be greatly appreciated!
– Lior
Feb 8, 2022 at 21:13

In light of the comments above, I'm going to try to answer this question, with the caveat that I am taking my first steps in this field so I might have errors here.

TLDR - it seems to me that in an independent errors model, the MWPM decoder is an optimal decoder for the Pauli frame, rather than for the logical outcome. Thus, it is the optimal encoder if we only use the syndrome record. However, if we have additional information about the structure of the logical state $$|\psi_L\rangle$$ and the data outcomes, we can do better.

Why did I reach this conclusion?

### Optimal decoder

The error correction procedure uses a an ancilla measurement record $$s$$ and a data qubit measurement record $$d$$ to infer a logical observable outcome $$L$$ (which can be 0 or 1, depending on if the measured state is an eigenvalue of the measured logical operator with eigenvalues +1, -1, respectively).

We want to maximize the probability $$p(L'=L)$$, where $$L'$$ is the inferred logical state.

What we need to is to do Bayesian inference, as was commented above, i.e we need to calculate:

$$L' = \arg\max_L{p(L|s,d)} = \arg\max_L{p(s,d|L)p(L)}.$$

Now, the data qubits are determined by the Pauli frame and the encoded logical state in the following way:

$$d = (d_L + F)$$,

where $$d_L$$ is one of the outcome bits of the state $$|\psi_L\rangle$$ and $$F$$ is the Pauli frame, and we add mod 2. The syndromes $$s$$ are determined in a specific way by the set of Pauli errors that occured, and the frame $$F$$ is determined by the overall Pauli errors that occured on the data qubits. At this point the situation is quite complicated, and it's not clear how to find the $$L$$ that maximizes this probability.

### Optimal estimation of the Pauli frame $$F$$

Now what it seems to me is that MWPM decoding says the following: Let's estimate $$L$$ using the following rule:

$$L' = v_L^T(d_L + F) = L + v_L^TF$$

where $$v_L^T$$ is a string which is 1 only on the logical qubits of the logical operator. This estimator is probably sub-optimal, though I can't think of a specific way to show it.

In this case however, our task is to estimate $$F$$. This is more straightforward, since $$p(F|s,d)$$ is the the probability that we got a set of Pauli errors $$P_e$$ and measurement errors $$M_e$$ that are consistent with $$F$$:

$$F' = \arg\max_F p(F|s,d) = \arg\max_F p(\{P_e, M_e | F = f(P_e, M_e)\} | s,d)$$

so out of all the possible Pauli and measurement errors that could result in $$F$$, we need to search for the highest probability set, which in the case of independent errors is the minimal weight set.

Again, any comments/corrections to this argument would be most welcome.

• upvote for trying to derive things from first principles; but some things don't seem right. For QECC the syndrome is all you're allowed to use; this is different from classical but it turns out not to be an issue : you can (soft decision) decode with "syndrome based" decoders and get the same performance as "codeword based" decoders. That being said, there are optimal syndrome based decoders but MWPM isn't one of them Feb 9, 2022 at 17:24
• thanks @unknown. I think perhaps the mistake is that the given a syndrome record, the most probable set of pauli errors consistent with them, and therefore the most probable frame, is not the same as the minimal length set, because there are many more longer chains than shorter ones? If this is the intuition, it makes sense to me and I understand where the error is
– Lior
Feb 11, 2022 at 11:32