Interpretation of Union-Find Decoder on Weighted Graphs and Application to XZZX Surface Code

• MWPM decoder: Minimum-Weight Perfect Matching Decoder
• Union-Find decoder: similar threshold on the same weighted decoding graph
  • 2.6% (UF) compared to 2.9% (MWPM) under code capacity noise model in CSS surface code
    Delfosse N, Nickerson N H. Almost-linear time decoding algorithm for topological codes[J]. Quantum, 2021, 5: 595.
  • 0.76% (UF) compared to 0.90% (MWPM) under circuit-level noise model in CSS surface code
    Huang S, Newman M, Brown K R. Fault-tolerant weighted union-find decoding on the toric code[J]. Physical Review A, 2020, 102(1): 012419.

• MWPM decoder: Minimum-Weight Perfect Matching Decoder
• Union-Find decoder: similar threshold on the same weighted decoding graph
  • 2.6% (UF) compared to 2.9% (MWPM) under code capacity noise model in CSS surface code
    Delfosse N, Nickerson N H. Almost-linear time decoding algorithm for topological codes[J]. Quantum, 2021, 5: 595.
  • 0.76% (UF) compared to 0.90% (MWPM) under circuit-level noise model in CSS surface code
    Huang S, Newman M, Brown K R. Fault-tolerant weighted union-find decoding on the toric code[J]. Physical Review A, 2020, 102(1): 012419.
• What's the relationship between them?
• Under what conditions UF decoder has the same accuracy as MWPM decoder?

code distance d = 3

code distance = {{ d }}

i.i.d. errors: the most likely error pattern $\iff$ the lowest amount of errors

A logical X error occurs: an error chain connecting the left and right boundaries

Cluster: a connected region of exploratory region

odd (even) cluster contains odd (even) number of nontrivial measurements

Peeling algorithm: find errors only inside each cluster to cancel out syndrome

these errors correspond to a perfect matching (usually not minimum-weighted)

Dual variables: drawn as the "radius" or "width" of exploratory region

some exploratory region grows while some may shrink (depends on internal structure)

Blossom algorithm: two vertices cannot be matched if they are in different clusters

any minimum-weighted perfect matching corresponds to an error pattern

Both UF and MWPM Decoder: all errors inside clusters

Both UF and MWPM Decoder: all errors inside clusters

In this example, their error patterns only differ by several stabilizer operators

What's the relationship between them?

UF decoder is an approximate MWPM decoder using the same weighted graph

• UF decoder drops internal details of clusters, the blossom algorithm keeps them
• UF decoder: better time complexity, lower accuracy
• MWPM decoder: worse time complexity, higher accuracy
• Combining UF and MWPM decoder could potentially balance between decoding time and accuracy
• e.g. by dropping internal details of clusters only when the cluster is too large

Under what conditions UF decoder has the same accuracy as MWPM decoder?

Under what conditions UF decoder has the same accuracy as MWPM decoder?

Application: XZZX surface code with infinite noise bias under perfect measurements

1. The shape of clusters is the same
2. The second condition stands for any code distance

• Noise model: Pauli errors only on data qubits, single round of perfect measurement
  Bonilla Ataides J P, Tuckett D K, Bartlett S D, et al. The XZZX surface code[J]. Nature communications, 2021, 12(1): 1-12.
• Noise bias: $\eta$, total error rate: $p=7\%$ (fixed) [physical error rate $p_Z = \frac{\eta p}{1+\eta}$, $p_X = p_Y = \frac{p}{2(1+\eta)}$]
• Result: when $\eta \xrightarrow[]{} \infty$, the accuracy loss vanishes

• Noise model: circuit-level noise model, noise bias: $\zeta$
  Darmawan A S, et al. Practical quantum error correction with the XZZX code and Kerr-cat qubits[J]. PRX Quantum, 2021, 2(3): 030345.
• Result: UF decoder close to MWPM decoder at $\zeta = 100$
• threshold = 0.90% (UF decoder) v.s. 0.98% (MWPM decoder)

Analytical and numerical results: UF is equally (closely) accurate as MWPM decoder

Future work: combining UF and MWPM decoder

• Noise model: correlated Pauli errors during two-qubit gates and single-qubit errors
  Darmawan A S, et al. Practical quantum error correction with the XZZX code and Kerr-cat qubits[J]. PRX Quantum, 2021, 2(3): 030345.
• Initialization and measurement: $p_X = p_Y = p_Z / \zeta$
• CPHASE: $p_{Z\otimes I} = p_{I\otimes Z} = p_Z$, $p_{\text{others}} = p_Z / \zeta$
• Standard CNOT: $p_{Z\otimes I} = p_Z$, $p_{I\otimes Z} = p_{Z\otimes Z} = \frac{3 p_Z}{8}$, $p_{I\otimes Y} = p_{Z\otimes Y} = \frac{p_Z}{8}$, $p_{\text{others}} = p_Z / \zeta$
• Bias-preserving CNOT: $p_{Z\otimes I} = p_Z$, $p_{I\otimes Z} = p_{Z\otimes Z} = \frac{p_Z}{2}$, $p_{\text{others}} = p_Z / \zeta$

• Noise model: correlated Pauli errors during two-qubit gates and single-qubit errors
• Result: UF decoder is only close to but not equally accurate as MWPM decdoer
• In circuit-level noise model, the decoding graph is no longer 1-dimensional