René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Tropical TN decoder scalability: d\u003e=5 infeasible due to high tree width - investigate approximate contraction methods","articleBody":"## Problem Summary\n\nThe current tropical tensor network MAP decoder implementation works perfectly for d=3 but **fails for d\u003e=5** due to prohibitively high tree width (space complexity).\n\n### Current Results\n\n| Distance | Variables | Factors | Tree Width (sc) | Memory Required |\n|----------|-----------|---------|-----------------|-----------------|\n| d=3 | 78 | 102 | 9 | **~4 KB** ✓ |\n| d=5 | 502 | 622 | 36 | **~550 GB** ✗ |\n| d=7 | 1558 | 1894 | 80 | **~10¹⁵ GB** ✗ |\n\nFor d=3, the tropical TN decoder achieves **exact agreement with MWPM** (differs=0 across all error rates), validating the implementation correctness.\n\n### Root Cause\n\nThe factor graph for circuit-level noise rotated surface codes has tree width that grows exponentially with distance. This is a **fundamental limitation of exact MAP inference**, not an implementation issue.\n\nKey observations:\n1. The time dimension (d rounds) creates high connectivity in the factor graph\n2. Standard variable elimination/contraction ordering cannot reduce tree width below ~36 for d=5\n3. Slicing only splits the network into disconnected components without reducing per-component tree width\n\n---\n\n## Potential Solutions: Approximate Tensor Network Contraction\n\nBased on literature survey, several approximate methods could enable d\u003e=5 decoding:\n\n### 1. **Bond Dimension Truncation (MPS/MPO)**\n- **Reference**: Bravyi et al., \"Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code\" [arXiv:1405.4883]\n- **Method**: Use Matrix Product States to approximate intermediate tensors during contraction\n- **Complexity**: O(n χ³) where χ is bond dimension (approximation parameter)\n- **Results**: Significant improvement over MWPM with χ≥4 for code capacity noise\n- **Key insight**: Uses DMRG-style boundary contraction\n\n### 2. **Sweep Line Contraction**\n- **Reference**: Chubb, \"General tensor network decoding of 2D Pauli codes\" [arXiv:2101.04125]\n- **Implementation**: [SweepContractor.jl](https://github.com/chubbc/SweepContractor.jl)\n- **Method**: Sweep a line across the 2D tensor network, maintaining bounded bond dimension\n- **Complexity**: O(n log n + n χ³)\n- **Results**: State-of-the-art thresholds, numerically consistent with optimal\n\n### 3. **Belief Propagation on Tensor Networks**\n- Combine BP messages with tensor structure\n- May inherit BP's limitations on loopy graphs\n\n### 4. **Variational Methods**\n- Optimize tensor network structure variationally\n- Potentially slower but more general\n\n---\n\n## Proposed Implementation Plan\n\n### Phase 1: MPS-based Approximate Contraction\nImplement MPS boundary contraction following Bravyi et al.:\n1. Arrange factor graph on a cylinder/strip\n2. Contract row-by-row using MPO-MPS multiplication\n3. Truncate to bond dimension χ after each step\n4. Recover approximate MPE assignment via backtracking\n\n### Phase 2: Sweep Contraction\nPort/adapt SweepContractor.jl approach:\n1. Planarize the tensor network\n2. Use sweep line algorithm with truncation\n3. Works for general 2D tensor networks\n\n### Phase 3: Benchmarking\nCompare approximate TN decoder against:\n- MWPM baseline\n- BP-OSD decoder\n- Measure threshold degradation vs χ\n\n---\n\n## Technical Considerations\n\n### For Circuit-Level Noise\nThe factor graph is **3D** (space × time), not 2D. This complicates:\n1. Boundary contraction ordering\n2. Sweep line direction selection\n3. Bond dimension requirements may be higher\n\n### Tropical Semiring Adaptation\nStandard MPS truncation uses SVD on probability semiring. For tropical (max-plus) semiring:\n- Need tropical SVD analog or\n- Convert to log-probabilities and use standard SVD approximation\n- May lose exactness of tropical operations\n\n---\n\n## Related Issues\n- This explains why slicing alone doesn't help: sliced components maintain same tree width\n- Connected component handling was fixed in recent commits but doesn't address core scalability\n\n## References\n1. Bravyi et al., [arXiv:1405.4883](https://arxiv.org/abs/1405.4883) - MPS decoder\n2. Chubb, [arXiv:2101.04125](https://arxiv.org/abs/2101.04125) - Sweep contraction\n3. Schotte et al., [arXiv:2012.04610](https://arxiv.org/abs/2012.04610) - TN for Fibonacci code\n\n/cc @maintainers","author":{"url":"https://github.com/ChanceSiyuan","@type":"Person","name":"ChanceSiyuan"},"datePublished":"2026-01-25T16:34:36.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":7},"url":"https://github.com/71/BPDecoderPlus/issues/71"}