understanding the accuracy implication of `max_tree_size`

[yuewuo]

As explain in [1,2], the only difference between the MWPM decoder and the Union-Find decoder is whether they maintain detailed structures within each cluster. Recently, I added a parameter called max_tree_size which allows one to control how much detail they want to preserve inside each cluster. When max_tree_size = 0, it's equivalent to UF decoder; when max_tree_size = infinity, it's equivalent to MWPM decoder. This parameter actually generates a full spectrum of decoders between MWPM and UF decoder.

Now, the question is, what parameter should I choose to reach the same decoding accuracy of MWPM? For example, if the logical error rate of MWPM decoder is $p_M$ and the logical error rate of UF decoder is $p_U$, generally $p_U > p_M$. By tuning this parameters, we can create a decoder with logical error rate of $p_L$ which has $P_U \ge p_L \ge p_M$. Say, if we want to reach at most 20% more logical error rates in exchange for faster decoding, what max_tree_size should I choose? That is, what is the minimum max_tree_size value that satisfies $p_L \le p_M \times 1.2$?

Furthermore, does this parameter changes with the size of the code? For example, do we need to increase the minimum max_tree_size with code distance $d$?

It is your choice to start with any code, and it's quite easy to benchmark fusion blossom logical error rate using QEC-Playground. For example, you can run this command in QEC-Playground to obtain the logical error rate:

# for parameters:
cargo run --release -- tool benchmark --help
# code capacity noise model: 2D graph
cargo run --release -- tool benchmark '[5]' '[0]' '[0.05]' --decoder fusion -p10
cargo run --release -- tool benchmark '[5]' '[0]' '[0.05]' --decoder fusion --decoder-config '{"max_tree_size":0}' -p10
cargo run --release -- tool benchmark '[5]' '[0]' '[0.05]' --decoder fusion --decoder-config '{"max_tree_size":3}' -p10
# circuit-level noise model (the same with `stim`)
cargo run --release -- tool benchmark '[5]' '[5]' '[0.005]' --noise-model stim-noise-model --decoder fusion -p10
cargo run --release -- tool benchmark '[5]' '[5]' '[0.005]' --noise-model stim-noise-model --decoder fusion --decoder-config '{"max_tree_size":0}' -p10

[1] Wu, Yue, and Lin Zhong. "Fusion blossom: Fast mwpm decoders for qec." 2023 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 1. IEEE, 2023. [2] Wu, Yue, Namitha Liyanage, and Lin Zhong. "An interpretation of union-find decoder on weighted graphs." arXiv preprint arXiv:2211.03288 (2022).

[DotandLog]

Hi Yue,

Could I help on this issue?

[golanor]

Hi, I also started collecting data for this issue. So far, for code distances 3,5,7 there is no dependence on the tree size. Does that make sense?

[yuewuo]

Hi, I also started collecting data for this issue. So far, for code distances 3,5,7 there is no dependence on the tree size. Does that make sense?

According to our previous numerical analysis, there should be noticable difference between MWPM (max_tree_size=infinity) and UF (max_tree_size=0) decoder. This is the result for xzzx code with some noise bias. It's simulated with qecp as well, so it should be fairly easy to reproduce this figure using the command line tool of qecp. https://us.wuyue98.cn/aps2022/#/4/1/0 . The difference should be at the order of 1.3x or something. The difference will increase as the code distance increases. There might be other factors, like the noise model and the code type.

[golanor]

It seems to be the case for d>7, but I'm still collecting the data for larger distances

[golanor]

I thought I had a result but it didn't make sense, so I'm rerunning it. I'm running on distance 9 with p=0.005. How do you want the results to be displayed? A plot with all values? Should I calculate other distances as well?

[yuewuo]

I thought I had a result but it didn't make sense, so I'm rerunning it. I'm running on distance 9 with p=0.005. How do you want the results to be displayed? A plot with all values? Should I calculate other distances as well?

A plot would be fine. How about adding a tutorial page in the tutorial/ folder, including the plot of differences? Thanks.

[YangLiuWillow]

Hi, I just submitted a PR.