Obtain the error threshold of BP + OSD decoder

[GiggleLiu]

[ChanceSiyuan]

OSD Decoder Implementation and Investigation Results

Implementation Status

I've implemented an OSD (Ordered Statistics Decoding) post-processor in src/bpdecoderplus/osd.py on branch fix/osd-decoder-improvements. The implementation includes:

• OSD-0: Basic RREF-based solution (no search)
• OSD-E: Exhaustive search over most probable free variables
• Optional random_seed parameter for deterministic testing

Bug Fixes Applied

1. Fixed free variable selection: Now correctly selects free variables with highest probability (most likely to be errors) rather than just the first N free columns in sorted space.

2. Simplified solution computation: Cleaned up the convoluted logic for computing candidate solutions using vectorized operations.

Test Results (1000 samples, d=3, p=0.01)

Decoder	Logical Error Rate
BP only	0.193
BP + OSD-0	0.375
BP + OSD-5	0.332
BP + OSD-10	0.314

Key Finding

OSD is performing worse than BP alone, not better. This is unexpected since OSD should improve upon BP by finding minimum-weight solutions that satisfy the syndrome constraint.

The syndrome constraints ARE being satisfied (verified), so the OSD implementation is mathematically correct. However, the minimum-weight solution found by OSD is often not the correct error pattern.

Root Cause Analysis

This issue is likely related to the fundamental architecture problems described in Issue #38. Specifically:

1. The BP marginals being passed to OSD may not be meaningful error probabilities
2. OSD optimizes for minimum Hamming weight, but for degenerate quantum codes, minimum weight ≠ most likely error
3. The factor graph structure may be providing incorrect soft information to guide OSD's search

Next Steps

Before OSD can be properly evaluated, the underlying BP architecture issues in #38 need to be addressed. Once BP provides meaningful error marginals, OSD should improve performance by:

• Finding syndrome-satisfying solutions
• Searching over the most uncertain variables
• Selecting the minimum-weight solution among candidates

Branch

The implementation is available on: fix/osd-decoder-improvements

[ChanceSiyuan]

Progress Update: BP+OSD Decoder Fixed

The BP+OSD decoder is now working correctly after fixing the cost function issue. Current results on d=3:

Decoder	Logical Error Rate	Physical Error Rate
BP-only	10.9%	p = 0.001
BP+OSD-15	6.8%	p = 0.001

Next steps for error threshold:

1. Run experiments across multiple physical error rates (p = 0.001 to 0.01)
2. Test on different code distances (d = 3, 5, 7)
3. Plot logical error rate vs physical error rate
4. Identify threshold where curves cross

The fixed implementation is available on branch fix/osd-decoder-improvements.

See docs/bp_osd_fix.md for technical details on the fix.

[ChanceSiyuan]

Issue Resolved: Error Threshold Obtained and Validated

This issue has been resolved with successful threshold computation and validation.

Results Summary

Metric	Value
Circuit-level threshold	~0.7% (p ≈ 0.007)
BP+OSD-15 improvement over BP-only	37.6% reduction in logical error rate
Validation	Consistent with literature (Bravyi et al. 2024, Higgott & Breuckmann 2023)

Implementation Evidence

Threshold Analysis Infrastructure:

• scripts/analyze_threshold.py - Main threshold analysis script with GPU acceleration
• scripts/generate_threshold_datasets.py - Dataset generation for multiple distances/error rates
• outputs/threshold_plot.png - BPDecoderPlus LER vs physical error rate curves
• outputs/threshold_comparison.png - Side-by-side comparison with ldpc library
• outputs/threshold_overlay.png - Both decoders overlaid

Documentation:

• docs/Getting_threshold.md - Complete reproduction guide with:
  • Two-stage DEM parsing (separator splitting + hyperedge merging)
  • XOR probability chain for observable prediction
  • Decoder configuration (BP iter=60, OSD order=10, damping=0.2)
• docs/bp_osd_fix.md - Details the critical OSD cost function fix (Hamming weight → LLR-based soft-weighted cost)
• docs/ldpc_comparison.md - Extensive validation against reference ldpc library

Key Fixes Applied:

1. OSD cost function now uses soft-weighted cost based on LLRs (not Hamming weight)
2. Proper XOR probability chaining for observable prediction with merged hyperedges
3. Connected components handling in factor graph contraction

The threshold of ~0.7% under circuit-level depolarizing noise matches the well-established benchmark from literature.

[ChanceSiyuan]

Closing as resolved - error threshold (~0.7%) obtained and validated against ldpc library