Near-Singleton Logical List Decoding of Quantum LDPC Codes from Faulty Syndromes

Abstract

Quantum low-density parity-check (QLDPC) codes promise scalable quantum memories, but their decoders receive only sparse check outcomes that may themselves be wrong. We prove that one such record supports logical list decoding near the Singleton radius in a fixed folded-block metric. For any fixed rate and positive gap below that radius, we construct bounded-locality

Calderbank--Shor--Steane (CSS) QLDPC families with a randomized near-linear-time decoder. The decoder returns a constant number of Pauli candidates, independent of blocklength. An exact record gives zero-residual coverage of every compatible logical class within the target radius. If an adversarial fraction below a fixed threshold of outcomes is faulty, every compatible error within that radius has stabilizer-reduced relative distance at most a constant times that fraction from some returned candidate. The main advance is to reduce the high-weight logical ambiguity before residual correction begins. Each local syndrome outcome cuts the error space to an affine slice. We prove the quotient-compatibility conditions that let the published Alon--Edmonds--Luby (AEL) average-radius bound control distinct logical classes, leaving only a constant number of alternatives. We then turn the observed slices into the agreement graphs used by fast regularity enumeration. An existing single-shot quantum-Tanner decoder handles the small remainder. The resulting front end preserves the sparse measurement record, and its residual grows linearly with syndrome corruption below the stated threshold.