Efficient atom loss decoding via Pauli boundedness and adaptive reweighting

Atom loss is a major error source in neutral atom quantum computers. Its non-Pauli and correlated nature poses significant challenges to decoding. Existing loss-aware decoders are either computationally inefficient, do not provide a satisfactory logical error rate, or require extensive machine learning training. To address these challenges, we propose the Pauli Boundedness framework, generalizing existing loss-to-Pauli approximations and enabling rigorous analysis. Using this framework, we define an approximation that statistically recovers the physical atom-loss effects while guaranteeing low weights, inducing a MILP-based decoder that outperforms prior such decoders. Applying this framework to surface codes and MWPM decoding, we strategically decompose loss-induced Pauli errors into edge-like errors to optimize the provable effective code distance. We further design a new atom-replenishing syndrome extraction circuit that localizes the effect of atom loss, achieving higher effective code distances with negligible extra space-time cost compared with previous circuits. Circuit-level simulations demonstrate that our approach attains higher thresholds compared to existing decoders. Combined with recent fast correlated decoding techniques, our method enables efficient, high-threshold loss decoding for transversal logical circuits using MWPM.