lottery-bp-decoding

name

lottery-bp-decoding

description

Lottery BP methodology for scalable quantum error correction decoding. Introduces randomness during belief propagation decoding to improve accuracy by 2-8 orders of magnitude for topological codes (surface, toric, BB codes). Use when: quantum error correction, qLDPC decoding, scalable quantum decoders, belief propagation for quantum codes, syndrome processing, PolyQec architecture, or when building fault-tolerant quantum computing systems requiring real-time decoding.

Lottery BP: Scalable Quantum Error Decoding

Core Innovation

Standard Belief Propagation (BP) decoders for quantum LDPC codes suffer from error degeneracy — multiple equivalent error patterns produce identical syndromes, causing BP to fail. Lottery BP breaks this symmetry by introducing controlled randomness during decoding iterations.

Key Concepts

1. Lottery BP Decoder

• Add randomness to variable node updates during BP message passing
• Each decode attempt uses different random seeds
• Multiple independent attempts → select lowest-weight solution
• Improves accuracy by 2-8 orders of magnitude over standard BP for topological codes

2. Syndrome Vote (Pre-processing)

• Compress multiple rounds of measurement syndromes into a single syndrome
• Majority voting across temporal syndrome rounds
• Increases latency margin and mitigates decoder backlog
• Essential for multi-round measurement error handling

3. PolyQec Architecture

Two-level decoding hierarchy:

• Local decoder: Lottery BP (fast, high accuracy for most errors)
• Global decoder: Ordered Statistics Decoding (OSD) (slow, used only when BP fails)
• Lottery BP's improved local accuracy reduces OSD invocations by 3-5 orders of magnitude

4. Syndrilla Simulator

• PyTorch-based modular decoding simulation pipeline
• GPU-accelerated (1-2 orders of magnitude faster than CPU)
• Extensible interface for adding new decoder types
• Integrated metrics for fair decoder comparison

Algorithm Steps

def lottery_bp(syndrome, H, max_iterations, num_lotteries):
    """
    syndrome: measured syndrome vector
    H: parity check matrix
    max_iterations: BP iterations per lottery
    num_lotteries: number of random attempts
    """
    best_solution = None
    best_weight = infinity
    
    for lottery in range(num_lotteries):
        # Initialize with random perturbation
        messages = initialize_messages(H, seed=lottery)
        
        # Run BP with randomized updates
        for iteration in range(max_iterations):
            # Variable node update with random noise
            variable_msgs = update_variable_nodes(messages, random_noise=True)
            # Check node update  
            check_msgs = update_check_nodes(variable_msgs, H)
            messages = merge_messages(check_msgs)
            
            # Estimate error pattern
            estimate = compute_estimate(messages)
            
            if syndrome_check(estimate, H, syndrome):
                weight = hamming_weight(estimate)
                if weight < best_weight:
                    best_weight = weight
                    best_solution = estimate
                break  # Valid solution found
        
        if best_solution is not None:
            break  # Found valid solution
    
    return best_solution

When to Use

• Scalable quantum decoding: Need to decode millions of qubits in real-time
• Topological codes: Surface code, toric code, bivariate bicycle codes
• Resource-constrained QCIs: Limited classical compute for quantum-classical interfaces
• Error floor improvement: Need better performance in low physical error rate regime

Key Parameters

Parameter	Description	Typical Value
num_lotteries	Random decode attempts	10-100
max_iterations	BP iterations per attempt	50-200
syndrome_window	Rounds for syndrome voting	3-7
random_strength	Noise amplitude in updates	tuned per code

Pitfalls

• Too few lotteries: May not find valid solution for degenerate codes
• Too many lotteries: Increases latency, defeats scalability goal
• Missing syndrome vote: Multi-round measurement errors cause catastrophic failures
• No OSD fallback: Lottery BP may fail on rare error patterns; OSD fallback needed

Related Patterns

• Min-sum decoder: Alternative to BP with lower complexity (works well for Margulis codes)
• OSD (Ordered Statistics Decoding): Global fallback decoder, computationally expensive
• Predecoding: Lightweight first-pass decoding to reduce workload (see qLDPC predecoding)

References

• arXiv:2605.00038 "Lottery BP: Unlocking Quantum Error Decoding at Scale" (Zhu et al., May 2026)