# How is the match graph extracted from a stim.circuit.detector_error_model?

Let's say we have an error mechanism error(0.1) D7 D8 ^ D9 D10 ^ D13 D15. I understand that Stim is trying to decompose the complex errors into graphlike errors. It is saying: ok, we have one error mechanism, when it happens, we have three edges D7--D8, D9--D10, and D13--D15.

My understanding is that: we are adding these 3 weighted edges to the matching graph. And these 3 edges are dependent on each other. Namely, if D7--D8 is triggered, then we also know that D9--D10, and D13--D15 is triggered.

However, it is not right. Because the MWPM decoder assumes independent probability of each qubit suffering an error (if I understand it in the right way), which means the weights of the matching graph should also be independent of each other so that we can add weights of edges that connect two defects.

My questions are the followings:

1. How does Stim convert a DEM to a matching graph with independent edges?
2. Let's say we have a DEM with two error mechanisms: error(0.1) D1 D2 ^ D2 D3 ^ D7 D8 and error(0.2) D2 D3 ^ D4 D7 ^ D7 . How does Stim deal with the weight of edge D2--D3?
3. Can we get the matching graph with weights in some way?

Thanks!

How does Stim covert a DEM to a matching graph with independent edges?

Stim doesn't do this. It's the decoder's job to turn the DEM into a matching graph. Stim tries to help make this easier by giving the suggested decomposition.

The key property that Stim uses when suggesting these decompositions is to notice pieces of the error occurring elsewhere. The idea is that if D1 D3 can occur on its own from one single error, and D2 D4 can occur on its own from one single error, then it must be safe to think of D1 D2 D3 D4 as being built out of those two errors: D1 D3 ^ D2 D4. You need to be able to correct them individually, so you should also be able to correct them occurring together.

For example, suppose D1 D3 is an X error in the bulk of the CSS surface code and D2 D4 is a Z error on the same data qubit. The key thing to realize is that D1 D2 and D1 D4 and D2 D3 and D3 D4 won't appear from single physical errors in this context, because they require long strings of physical errors reaching from the bulk to boundaries, as opposed to single physical errors. So D1 D2 D3 D4 will be decomposed into D1 D3 ^ D2 D4 (decomposing Y into X*Z) instead of into anything else.

Let's say we have a DEM with two error mechanisms: error(0.1) D1 D2 ^ D2 D3 ^ D7 D8 and error(0.2) D2 D3 ^ D4 D7 ^ D7 . How does Stim deal with the weight of edge D2--D3?

What pymatching does is to decompose error(0.1) D1 D2 ^ D2 D3 ^ D7 D8 as if it were error(0.1) D1 D2 then error(0.1) D2 D3 then error(0.1) D7 D8. In other words, the big correlated error is seen as raising the probability of its component edges, and all correlations are ignored.

Pymatching combines edge probabilities p1, p2 for the same edge into a combined probability p1 * (1 - p2) + p2 * (1 - p1). Ultimately the combined edge error probability $$p$$ becomes a weight $$w = \lg(p / (1 - p))$$. Internally, weights are rescaled so that the biggest weight is $$2^{24}-2$$, then weights are discretized into even integers, so faster integer math can be used while matching.

Of course, simply ignoring the correlations is not required. Decoders that perform correlated decoding will take note of these correlations between edges instead of simply splitting them into independent pieces. There's a huge variety of ways this can be done. For example, after a simple pre-matching pass that can only match adjacent detection events, the decoder can use the pre-matched edges as triggers for downweighting associated edges.

Can we get the matching graph with weights in some way?

Use pymatching.Matching.from_detector_error_model to ask pymatching to convert a DEM into a match graph, and then pymatching.Matching.to_networkx to get that graph as a networkx.Graph.

• Thanks very much! That's very helpful! Feb 6, 2023 at 17:52