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

arXiv:2609.40313 · quant-ph, cs.IT, math.IT · Submitted 2026-09-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time".

Kai: Explicit constructions for quantum LDPC codes achieving capacity-approaching list decoding and near-linear time decoding are presented, addressing a long-standing challenge in quantum coding theory.

Mira: First, who's behind it and why it matters.

Title and authors: Kai: To summarize what we've seen so far about "Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time," the authors detail that they use a quantum analogue of Alon–Edmonds–Luby amplification, which involves combining an outer CSS code D, a constant-size inner CSS code C, and a regular bipartite expander graph G = (L, R, E).

Mira: The summary emphasizes that the relative folded distance delta(F) satisfies delta(F) at least delta(C) - lambda delta(D), which is important because it shows how the distance properties of the inner code are preserved even with some loss due to using an expander graph.

Lev: That distance relationship is key for me because it tells us precisely how much performance we trade off when we introduce the expander graph structure into the quantum AEL construction; it gives us a quantifiable measure of that trade-off.

Kai: Furthermore, they describe a randomized syndrome-input decoder called QAEL-Syndrome-DecodeX that runs in time O epsilon R, zeta, xi(N), which is what makes the decoding near-linear in terms of the block length N.

Mira: That algorithmic efficiency is impressive because it means the decoding process doesn't have to solve a massive global system, but instead exploits the structure of qAEL checks to perform a local search.

Lev: Exploiting local structure sounds promising for hardware design, but I wonder about the complexity of that candidate enumeration step where they use Weak Regularity decomposition to find rigid assignments that are block-length independent.

Kai: They describe how this approach converts an unknown global error into an "unknown collection of inner codewords whose folding is close to the known folded lift rR," which allows for a local search strategy.

Mira: That local search strategy sounds like it avoids the exponential complexity we usually see in decoding general quantum codes, provided that the constraints on rigidity hold up under analysis.

Lev: I wonder if that rigidity argument truly produces an enumeration of candidate families that is independent of the block length N, or if it still scales exponentially with N in practice.

The paper's summary: Kai: Looking at the suggested improvements in "Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time," they focus heavily on making the entire framework more concrete and implementable for actual systems.

Mira: One major improvement is that they explicitly construct parameters for an arbitrary inner and outer code family, meaning we don't have to rely on abstract existence proofs but can actually instantiate specific codes based on target rate R and slack parameters zeta, xi.

Lev: Instantiating the parameters is what I need because running a real quantum computer requires knowing the exact connectivity and required physical qubit counts upfront; those explicit choices are essential for designing hardware architectures.

Kai: They also detail how they manage distance loss and candidate-generation errors by choosing specific constants, for example, requiring the expansion parameter to satisfy A sqrt < epsilon six/twenty-three squared to ensure the spectral condition holds.

Mira: That spectral condition constraint is where my theoretical concerns come in; it shows they've rigorously tied the necessary expansion properties directly to achieving the required list decoding radius, which is a solid link between theory and structure.

Lev: I see how managing candidate-generation error through a sufficiently large constant degree helps control the complexity of that enumeration stage, making sure we don't have an exponentially growing number of possibilities to check.

Kai: The paper also outlines how the final stitching stage recovers the correct global error coset by projecting it into its logical component in CX/C Z, ensuring that changing the outer word by an element of D Z only changes the qAEL word by an element of F Z.

Mira: That final step sounds like a way to ensure that the local search we do actually lands us on the correct global error class without needing a full, expensive global search.

Lev: If that projection mechanism is robust, it significantly simplifies the requirements for implementing fault tolerance because we can localize where the errors are likely to manifest.

The paper's improvements: Kai: So, to wrap up on "Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time," the main contribution is providing explicit, constructive methods for quantum codes that achieve capacity limits while maintaining the essential LDPC property and list decodability with constant list sizes.

Mira: The implication is that we now have a concrete family of codes where the error correction capability approaches the information-theoretic limit, and we can decode them efficiently using near-linear time algorithms.

Lev: From a hardware standpoint, this gives us a very clear set of design constraints and performance guarantees to work with when designing physical quantum processors for communication tasks.

Kai: The real excitement is that this moves us past purely random codes or codes where the structure isn't guaranteed; we have a specific mechanism rooted in expander graphs that ensures these properties hold.

Mira: I think the impact is significant because it provides a pathway for building quantum communication systems that are both theoretically optimal in terms of capacity and practically efficient in their decoding speed.

Lev: I just want to reiterate that while the construction is explicit, running this on current NISQ hardware will still require careful parameter tuning based on these constraints, especially regarding the required expansion factor.

Kai: Exactly; the future work seems to be moving toward applying these explicit constructions directly to more complex quantum error correction protocols or perhaps exploring how they integrate with fault-tolerant computation designs.

Mira: It really sets a high bar for what we expect from quantum codes that aim for both theoretical optimality and practical speed in communication.

Conclusion: Kai: So, we've just walked through the technical details of "Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time," covering everything from the AEL construction to that near-linear time decoding algorithm.

Mira: It really boils down to having a concrete blueprint for quantum codes that hit capacity limits and stay efficient, which is exactly what this paper delivers by tying the expander graph structure to list decodability.

Lev: I think the real value here is seeing how researchers can translate these abstract theoretical bounds into something actually runnable on current hardware setups, given the specific parameter choices they made.

Kai: That's right; we've seen how William Gay, Fernando Granha Jeronimo, and Abhi Shukul built this family of codes with explicit parameters for rate R and slack zeta.

Mira: The implication is that we can start designing quantum communication protocols knowing exactly what kind of error correction capability we are targeting without needing to guess at the code structure.

Lev: And from a practical side, the near-linear time decoding algorithm means that as systems scale up in block length N, they don't suddenly become computationally intractable during transmission recovery.

Kai: The excitement is definitely high because this moves us beyond just theoretical bounds; we have an explicit construction method rooted in expander graphs that actually ensures these desired properties hold for physical qubits.

Mira: I agree, it provides a strong pathway for building quantum communication systems that are both theoretically optimal in terms of capacity and practically efficient in their decoding speed.

Lev: I just want to emphasize again that while the construction is explicit, running this on current NISQ hardware will still require careful parameter tuning based on those constraints, especially regarding the required expansion factor.

William Gay, Fernando Granha Jeronimo, Abhi Shukul

University of Illinois, Urbana-Champaign

quant-ph, cs.IT, math.IT

Submitted: 2026-09-30

Updated: 2026-09-30

Comments: SODA 2027, to Appear

Code: https://github.com/Granha/quantum_ael_lean_formalization

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 86/100

The gist: Explicit constructions for quantum LDPC codes achieving capacity-approaching list decoding and near-linear time decoding are presented, addressing a long-standing challenge in quantum coding theory.

Key concepts

Quantum LDPC Codes: These are a specific type of quantum error-correcting code structure designed to be efficient. They achieve capacity-approaching performance and possess the Local Decoding Property (LDPC), which means errors can be corrected locally using only local checks, making them suitable for robust quantum communication.
Quantum AEL Amplification: This is a construction technique based on the quantum version of Alon–Edmonds–Luby amplification. It uses three components—an outer code, an inner code, and an expander graph—to build a powerful new code structure that inherits good distance properties while maintaining high rates.
List Decoding: Instead of finding the single most likely error (like standard decoding), list decoding finds a small set of possible errors. This is crucial for AI systems because it allows the decoder to output a list of potential error scenarios, enabling robust detection and mitigation against complex noise or adversarial attacks.

Terminology

CSS Codes — 9× in this paper · explained in 2 episodes
Accuracy — 3× in this paper · explained in 1 episode
Decode — 3× in this paper · explained in 2 episodes
IEEE Symposium on Foundations of Computer Science — 3× in this paper
Trace — 3× in this paper · explained in 2 episodes
Verification — 3× in this paper · explained in 2 episodes
Adam — 2× in this paper · explained in 2 episodes
Redundancy — 2× in this paper · explained in 2 episodes
Adjacency Matrix — 1× in this paper · explained in 1 episode
Annual ACM Symposium on Theory of Computing — 1× in this paper
Combinatorial Optimization — 1× in this paper · explained in 2 episodes
Consistency — 1× in this paper · explained in 3 episodes
Core — 1× in this paper · explained in 2 episodes
Elias — 1× in this paper · explained in 2 episodes
Embeddings — 1× in this paper · explained in 2 episodes
Hamming Distance — 1× in this paper · explained in 2 episodes

Summary

Explicit constructions for quantum LDPC codes achieving capacity-approaching list decoding and near-linear time decoding are presented, addressing a long-standing challenge in quantum coding theory. This work provides the first explicit constructions of such codes with constant list sizes, leveraging expander graphs to ensure the crucial LDPC property while simultaneously achieving performance near the quantum Singleton bound.

The Main Result

The paper establishes that for every rate loss R and slack parameters ζ, ξ, there exists an infinite family of F2-linear vector-space CSS codes on N folded blocks of size b with specific properties. These properties include:

Each code QN has a rate RN ≥ R. Its X- and Z-check matrices have row and column weights at most w on the underlying binary coordinates.
There is an explicit lower bound δN ≤ δ(QN) satisfying δN ≥ 1 − RN2−1 − ζ2/2n poly(1/ϵ) where N is the block-length and ϵ is the slack to the Johnson bound.
For some radius τN ≥ δN − ξ, the code is (τN, l)-list decodable: for every X- or Z-syndrome, at most l = OR,ζ,ξ(1) stabilizer cosets contain a representative of block weight at most τN N.
There is a randomized syndrome-input decoder running in time OeR,ζ,ξ(N), which outputs a list of at most l cosets containing every such low-weight error class with probability 1 − o(1).

Code Construction via Quantum AEL

The explicit construction is based on the quantum analogue of Alon–Edmonds–Luby (AEL) amplification, utilizing three main components:

- a high-rate outer CSS code D.

- a constant-size inner CSS code C.

- a regular bipartite expander G = (L, R, E).

The construction involves encoding an outer symbol by C, placing the resulting local coordinates on the edges of G, and folding the edges into blocks indexed by R. The folded qAEL CSS code F inherits distance properties from the inner code with some loss depending on expansion. The relative folded distance satisfies δ(F) ≥ δ(C) − λδ(D).

List Decoding Algorithm

The paper introduces a randomized syndrome-input list decoder, QAEL-Syndrome-DecodeX, which operates in near-linear time. The algorithm proceeds as follows:

Compute the local lift r = (ru)u∈L from an affine outer syndrome s using the parity checks.
Compute the affine outer syndrome σs from s and r using a specific formula involving the lifted outer checks and inner code projections.
Run CandGen(rR), a randomized procedure that computes local lists and returns at most Lmax assignments (where Lmax scales as l2O(l3in/ε6)).
For each assignment, form the tentative outer word yba and run AffDecout(yba, σs), which uses the outer code's syndrome decoder Decout in time Tout(n).
Discard failures and verify every output representative to obtain a list of cosets containing every low-weight error class.

Key Algorithmic Insights

The efficiency of the algorithm stems from exploiting the structure of qAEL checks rather than solving a global system. The decoding process converts an unknown global error into an unknown collection of inner codewords whose folding is close to the known folded lift rR. This allows for a local search approach:

**- The constraint satisfaction problem (CSP) formulation requires finding assignments that are rigid, meaning changing a label at a good vertex must violate many constraints into T. This rigidity argument, combined with weak-regularity decomposition, produces an enumeration of candidate families that is block-length independent. **

**- The final stitching stage recovers the correct global error coset by projecting the inner codeword to its logical component in CX/C⊥Z, ensuring that changing the outer word by an element of D⊥Z changes the qAEL word only by an element of F⊥Z. **

Parameter Selection and Instantiation

The proof constructs explicit parameters for an arbitrary inner and outer code family. The core constraints involve selecting constants based on the target rate R, slack parameters ζ, ξ, inner list size lin, and outer decoder time Tout(n). For instance:

**- The required expansion parameter is chosen such that Aexp√∆ < ε6/23l2, ensuring the spectral condition holds. **

**- The distance loss and candidate-generation error are managed by choosing a sufficiently large constant degree ∆.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed the provided paper, Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time. This work provides a rigorous framework for constructing and decoding explicit quantum codes that achieve list decoding capacity while maintaining the desirable Local Decoding Property (LDPC).

The core improvements this research enables are centered on developing quantum error correction and communication systems with high reliability, high throughput, and guaranteed near-optimal performance under adversarial conditions.

Here are the specific improvements to AI systems based on this scientific paper:

) 1. Construction of Quantum LDPC Codes for High-Capacity Communication

The paper provides an explicit construction method (via quantum AEL amplification using expander graphs) for family of quantum codes that achieve list decoding capacity up to the Singleton bound.

This allows AI systems to be encoded into quantum states with a guaranteed error correction capability approaching the absolute information-theoretic limit.
AI systems can transmit data across noisy or adversarial channels while maintaining extremely high fidelity, as the code structure is explicitly designed for maximum distance and list decoding radius.

) 2. Near-Linear Time Quantum List Decoding Algorithms

The research introduces a randomized syndrome-input decoder that operates in near-linear time (in block length) to list decode these quantum codes up to capacity.

This transforms quantum error correction from an exponential or high-polynomial complexity task into a highly efficient, scalable process.
AI systems can rapidly recover corrupted information packets from noisy quantum transmissions, enabling real-time processing of complex quantum data streams (e.g., in distributed quantum computing or secure communication networks).

) 3. Robustness Against Adversarial Errors via LDPC Structure

The paper shows that the constructed codes possess the LDPC property, which is crucial for local syndrome extraction and fault tolerance. Furthermore, the decoding algorithm explicitly handles low-weight error classes by leveraging expander mixing properties (Weak Regularity).

This ensures that AI systems are robust against structured adversarial noise or localized errors. The system can reliably identify and correct a large number of errors simultaneously without requiring a global search over the entire state space.
The ability to recover cosets rather than just single representatives means the system can output a list of all possible low-weight error scenarios, allowing for sophisticated error detection and mitigation strategies in real-time.

) 4. Hardware Implementation and Parameter Optimization (Explicit Instantiation)

Section 5 provides explicit parameter choices for the inner code (constant size at the Singleton bound), outer Tanner codes, and expander graphs that satisfy all necessary conditions (e.g., spectral ratios, distance loss bounds).

This allows engineers to design specific quantum hardware architectures—such as superconducting circuits or trapped ions—with known performance guarantees regarding required physical qubit counts and connectivity.
It enables the optimization of code parameters for specific application constraints (e.g., choosing the optimal block size, rate, and expansion factor based on desired error tolerance).

) 5. Enhanced Quantum Fault Tolerance

The synergy between the quantum AEL amplification and the explicit list decoding algorithm provides a pathway toward quantum fault tolerance. The decoder works by converting an error in the coded space into a collection of inner codewords whose folding is close to a known lifted structure, effectively performing correction locally.

This capability can be directly applied to building quantum memory modules or processors that are inherently resilient to local decoherence events, as the decoding mechanism is designed around local stabilizer checks.

In summary, this research allows for the creation of a new class of quantum communication and computation systems that are simultaneously:

Theoretically optimal in terms of capacity (achieving list decoding capacity).
Algorithmic in terms of speed (near-linear time decoding).
Structurally robust (LDPC property).

The resulting AI systems can perform high-throughput quantum data transmission and computation with guaranteed fidelity, even when facing significant noise or adversarial attacks, by leveraging explicit, near-optimal quantum error correction codes.