Tropical TN MAP decoder has higher LER than BP+OSD due to MAP vs marginal inference

[ChanceSiyuan]

Summary

The tropical tensor network decoder in scripts/analyze_tropical_threshold.py performs exact MAP (Maximum A Posteriori) inference to find the most likely error pattern. However, for quantum error correction, this approach yields higher logical error rates compared to BP+OSD.

Benchmark Results (d=3, 500 samples)

Error Rate	BP+OSD LER	Tropical MAP LER
0.001	0.00%	1.40%
0.003	0.60%	2.20%
0.005	1.00%	3.40%
0.007	5.40%	11.00%
0.010	6.00%	9.20%
0.015	12.00%	17.80%

Root Cause

The fundamental issue is that MAP decoding finds the most likely error pattern, but QEC requires the most likely observable value.

When multiple error patterns satisfy the syndrome:

• Some patterns predict observable = 0
• Others predict observable = 1
• The MAP pattern (highest individual probability) may predict the wrong observable
• Even when the total probability mass favors the correct observable

Example

For a syndrome with two valid solutions:

• Solution A: P=0.4, predicts obs=0
• Solution B: P=0.3, predicts obs=1
• Solution C: P=0.3, predicts obs=1

MAP picks Solution A (obs=0), but the correct answer is obs=1 (total probability 0.6 vs 0.4).

Why BP+OSD Works Better

BP computes marginal probabilities that account for ALL possible error patterns weighted by their probabilities. The soft XOR computation in observable prediction naturally handles this probabilistic weighting. OSD then finds a valid solution guided by these marginals.

Potential Improvements

1. Marginal MAP for Observable: Modify the factor graph to marginalize over error variables and compute P(obs=0|syndrome) vs P(obs=1|syndrome) directly. This requires sum-product (not max-product) for the observable variable.

2. Observable-Constrained MAP Comparison: Run MAP twice with hard constraints (obs=0 and obs=1), compare partition functions. Initial attempts had issues with assignment recovery in the tropical TN code.

3. Multiple Solution Enumeration: Find top-k most likely solutions and vote on the observable. Computationally expensive.

4. Hybrid Approach: Use tropical TN for the MAP solution, but use BP marginals for observable prediction.

Related Files

• scripts/analyze_tropical_threshold.py - Current implementation
• tropical_in_new/src/mpe.py - Tropical MPE inference
• scripts/analyze_threshold.py - BP+OSD threshold analysis for comparison

References

• Branch: fix/tropical
• Related to tropical tensor network integration from PR Add standalone tropical tensor network package #51

[ChanceSiyuan]

Fix Implemented

The root cause has been identified and fixed in commit 72383eb.

Problem Identified

The issue was not primarily about MAP vs marginal inference, but rather a bug in the contraction tree generation:

1. omeco.optimize_code only processes one connected component of the factor graph
2. When prior factors (single-variable) were disconnected from constraint factors, they were being dropped from the contraction tree
3. In a 78-variable, 102-factor problem, only 31 factors were being included in the contraction
4. This meant most syndrome parity constraints were not being enforced!

Evidence

Contraction tree has 31 leaf nodes (expected: 102)
WARNING: Tree doesn't include all nodes!

The Tropical TN was returning solutions that didn't even satisfy the syndrome constraints, which explained the higher LER.

Fix Applied

1. Added _find_connected_components() using union-find algorithm to detect all connected components in the factor graph
2. Modified get_omeco_tree() to:
   • Contract each connected component separately using omeco
   • Combine all component trees into a single contraction tree
3. Updated analyze_tropical_threshold.py to use pymatching's graph structure for consistency with MWPM

Verification Results

After the fix, on 100 samples with d=3 surface code:

• Tropical TN correct: 99/100 (99.0%)
• MWPM correct: 99/100 (99.0%)
• Agreement: 100/100 (100.0%)

The Tropical TN now produces results identical to MWPM on all test samples. Both decoders make the same decisions, and any remaining errors are due to the inherent limitations of MAP decoding (which is what MWPM also does).

New Tests Added

• tropical_in_new/tests/test_connected_components.py - Tests for connected component handling
• tropical_in_new/tests/test_tropical_mwpm_match.py - Tests verifying Tropical TN matches MWPM

All 16 new tests pass.