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.
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.
Many recently proposed Calderbank-Shor-Steane (CSS) quantum low-density parity-check (QLDPC) codes have sparse decoding graphs, enabling syndrome-based belief propagation (BP) decoding at low complexity. Their construction, however, often results in properties that impair BP performance, such as short cycles and degeneracy. In this work, we propose a general framework for introducing auxiliary variable nodes (AVNs) and auxiliary check nodes (ACNs) into the decoding graph of CSS codes, compatible with the standard stabilizer measurement framework. This provides an additional degree of freedom in the design of the decoding graph itself and can be used to tackle the aforementioned shortcomings. We show that recently proposed techniques, 4-cycle removal and subcode ensemble decoding, can be interpreted as instances of this framework. For 4-cycle removal, we find that the gains depend strongly on the BP iteration count and check-node message scaling. Building on this framework, we further propose a graph-derived subcode ensemble decoder and demonstrate under circuit-level noise that it substantially reduces the per-round logical error rate compared with BP on the corresponding 4-cycle-free decoding graph.
Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.
Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the X- and Z-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting.
We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let R∈(0,1) be the quantum rate and R1=(1+R)/2 the common component rate. As the radius ρ=(1−R)/2−γ approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, LQLR⋆=ℓΘ(R1/γ),LQLD⋆=Θ(γ1−R)(γ↓0). The asymptotically exact QLD radius tradeoff is ρL⋆=L+1L21−R. These conclusions extend to the average-radius setting.
For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint X/Z candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.
In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022].
In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity.
Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.
Quantum low-density parity-check (qLDPC) codes are an important component in the quest for quantum fault tolerance. Dramatic recent progress on qLDPC codes has led to constructions which are asymptotically good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. These constructions, while theoretically explicit, rely on inner codes with strong properties only shown to exist by probabilistic arguments, resulting in lengths that are too large to be practically relevant. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice. A previous construction of qLDPC codes based on the lifted product of an expander-based classical LDPC code with a repetition code (Panteleev and Kalachev, 2020) achieved a near-linear distance, and avoids the need for such intractable inner codes. Our main result is an efficient decoding algorithm for these codes that corrects a near-linear number of adversarial errors. En route, we give a similar algorithm for the hypergraph product version these codes, which are simpler but have distance growing only as the square root of the block length. Our decoding algorithms leverage the fact that the codes we consider are quasi-cyclic, meaning that they respect a cyclic group symmetry. Since the repetition code is not based on expanders, previous approaches to decoding expander-based qLDPC codes, which typically worked by greedily flipping code bits to reduce some potential function, do not apply in our setting. Instead, we reduce our decoding problem (in a black-box manner) to that of decoding classical expander-based LDPC codes under noisy parity-check syndromes. For completeness, we also include a treatment of such classical noisy-syndrome decoding that is sufficient for our application to the quantum setting.
Real-time quantum error correction requires classical decoders to process growing syndrome workloads with low and predictable latency. For quantum low-density parity-check (qLDPC) codes, iterative belief propagation (BP) repeatedly updates messages over sparse Tanner graphs, creating substantial memory-access and data-movement demands. We map normalized Min-Sum BP decoding of the [[144,12,12]] Bivariate Bicycle qLDPC code onto a DPU-based Processing-in-Memory (PIM) architecture. Within each DPU, 11 tasklets cooperatively decode one syndrome, while multiple DPUs process independent syndrome instances in parallel. Using uPIMulator and a data-qubit Pauli error model with ideal syndrome measurements, we compare throughput, per-syndrome processing time, logical error rate (LER), and single-syndrome tail latency against a 16-logical-CPU baseline. At a component-wise physical error probability of p=0.001 and one BP iteration, the projected aggregate kernel throughput of 2,560 DPUs reaches 1.071 x 10^7 decodes/s, compared with 1.22 x 10^6 decodes/s for the CPU, an 8.8x improvement. From two iterations onward, the measured LER remains below the physical error probability for every evaluated value of p. For one to five iterations, the maximum sampled serialized X+Z DPU compute latency remains below the 1 ms decoder-side reference for trapped-ion QEC, reaching approximately 0.873 ms at five iterations. These results show that near-memory processing can provide high aggregate throughput and sub-millisecond compute latency for qLDPC BP decoding under the evaluated conditions.