Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Kun Zhu

Published Jul 15, 2026• 0 citations
Publisher

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.

DOI
10.31224/7601

Related papers

Single-shot state preparation thresholds in quantum LDPC codes: soundness, confinement, and statistical mechanics

Yuanchen Zhao, Yi Yuan, Zhengyi Han +1 more

Single-shot error correction does not by itself establish equally direct and robust logical-state initialization. We study preparation of CSS quantum low-density parity-check code states using one noisy round of the code's checks. We prove that linear confinement over a weight range growing at least logarithmically, together with at least logarithmic distance, suffices for a nonzero threshold under independent local-stochastic readout and data noise in the relevant CSS sector. The threshold is certified by ideal recovery of a decoder-defined logical channel. The key is a correction rule that preserves the logical class under local syndrome changes, allowing the proof to proceed without a local-stochastic bound on the preparation residual. This gives a single-block guarantee for quantum expander codes without dimension jumps or batching. Under the stronger linear-soundness hypothesis, we establish local-stochastic residual noise, enabling composition with compatible fault-tolerant gadgets. For a retained-record formulation, we also derive an exact statistical-mechanical representation of optimal final recovery at fixed preparation decoder. A decoder-dependent logical-sector order parameter characterizes asymptotically successful block decoding. Monte Carlo results for the three-dimensional toric code provide finite-size evidence for a threshold beyond both linear sufficient conditions. These results distinguish logical robustness from local-stochastic residual-noise control and identify decoder consistency as a route to single-shot initialization.

quant-pharXiv:2609.39965•Oct 1, 2026•0 citations

Logical-Class Diagnostic Layer for Stabilizer Codes and Decoders via Supercharge Structures

Hai Lin

We develop a decoder-agnostic logical-class diagnostic layer for abelian Pauli stabilizer codes, motivated by fault-tolerant quantum computing. An ancilla fermionic register defines a nilpotent supercharge whose clean degree-zero harmonic sector is the code space. Projected-return blocks derived from graded commutators organize the recovery test of whether a decoder-selected correction preserves every encoded input for every error in a declared same-syndrome family; the passing syndromes form the certified faithful window. Demoting the supercharge to an exact binary diagnostic formulation classifies residuals modulo stabilizers, separating a check violation, a harmless stabilizer residual, and a syndrome-silent nontrivial logical action, with a two-sector form for CSS codes. Because the unknown fault cancels, the relative logical class of two record-compatible candidates is computable online. We verify the diagnostic formalisms on the Steane code and specify a static--circuit bridge audit protocol for the Gross bivariate-bicycle quantum low-density parity-check (qLDPC) code. The method supplements existing decoders without additional physical qubits for software use.

quant-pharXiv:2611.01360•Nov 3, 2026•0 citations

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time

William Gay, Fernando Granha Jeronimo, Abhi Shukul

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.

quant-pharXiv:2609.40313•Oct 1, 2026•1 citation

Auxiliary Nodes for BP Decoding of Quantum LDPC Codes

Daniel Tandler, Paul Bezner, Stephan ten Brink

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.

arXiv:2607.12187•Jul 13, 2026•0 citations

Quantum List Recovery and Decoding: Achievability and Limitations

Fernando Granha Jeronimo, Xiaojuan Ma

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\in(0,1)\) be the quantum rate and \(R_1=(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, \[ L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. \] 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.

quant-pharXiv:2609.40262•Oct 1, 2026•0 citations

An Efficient Decoder for a Linear Distance Quantum LDPC Code

Shouzhen Gu, Christopher A. Pattison, Eugene Tang

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.

arXiv:2206.06557•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•56 citations
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.
Single-shot error correction does not by itself establish equally direct and robust logical-state initialization. We study preparation of CSS quantum low-density parity-check code states using one noisy round of the code's checks. We prove that linear confinement over a weight range growing at least logarithmically, together with at least logarithmic distance, suffices for a nonzero threshold under independent local-stochastic readout and data noise in the relevant CSS sector. The threshold is certified by ideal recovery of a decoder-defined logical channel. The key is a correction rule that preserves the logical class under local syndrome changes, allowing the proof to proceed without a local-stochastic bound on the preparation residual. This gives a single-block guarantee for quantum expander codes without dimension jumps or batching. Under the stronger linear-soundness hypothesis, we establish local-stochastic residual noise, enabling composition with compatible fault-tolerant gadgets. For a retained-record formulation, we also derive an exact statistical-mechanical representation of optimal final recovery at fixed preparation decoder. A decoder-dependent logical-sector order parameter characterizes asymptotically successful block decoding. Monte Carlo results for the three-dimensional toric code provide finite-size evidence for a threshold beyond both linear sufficient conditions. These results distinguish logical robustness from local-stochastic residual-noise control and identify decoder consistency as a route to single-shot initialization.
We develop a decoder-agnostic logical-class diagnostic layer for abelian Pauli stabilizer codes, motivated by fault-tolerant quantum computing. An ancilla fermionic register defines a nilpotent supercharge whose clean degree-zero harmonic sector is the code space. Projected-return blocks derived from graded commutators organize the recovery test of whether a decoder-selected correction preserves every encoded input for every error in a declared same-syndrome family; the passing syndromes form the certified faithful window. Demoting the supercharge to an exact binary diagnostic formulation classifies residuals modulo stabilizers, separating a check violation, a harmless stabilizer residual, and a syndrome-silent nontrivial logical action, with a two-sector form for CSS codes. Because the unknown fault cancels, the relative logical class of two record-compatible candidates is computable online. We verify the diagnostic formalisms on the Steane code and specify a static--circuit bridge audit protocol for the Gross bivariate-bicycle quantum low-density parity-check (qLDPC) code. The method supplements existing decoders without additional physical qubits for software use.
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.
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.
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 XXX- and ZZZ-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)R\in(0,1)R∈(0,1) be the quantum rate and R1=(1+R)/2R_1=(1+R)/2R1​=(1+R)/2 the common component rate. As the radius ρ=(1−R)/2−γρ=(1-R)/2-γρ=(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). L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). LQLR⋆​=ℓΘ(R1​/γ),LQLD⋆​=Θ(γ1−R​)(γ↓0). The asymptotically exact QLD radius tradeoff is ρL⋆=LL+11−R2. ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. ρL⋆​=L+1L​21−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/ZX/ZX/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.
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.