PaperlayerView exact revision on arXiv

Source-linked AI summary

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

William Gay, Fernando Granha Jeronimo, Abhi Shukul

arXiv:2609.40313v1quant-phcs.ITmath.IT

TL;DR

Can explicit quantum LDPC codes be combinatorially list decoded up to capacity and efficiently decoded there, beyond prior exact methods limited to the Johnson radius and large polynomial time? The construction uses quantum AEL codes, while a syndrome-input decoder exploits their local checks and structure to avoid potentially dense Gaussian elimination. The explicit quantum LDPC family approaches capacity with bounded list sizes, and the paper provides near-linear-time list decoding algorithms.

  • Problem

    Can explicit quantum LDPC codes be combinatorially list decoded up to capacity and efficiently decoded there, beyond prior exact methods limited to the Johnson radius and large polynomial time?

    Source: §1 · p. 4

  • Method

    The construction uses quantum AEL codes, while a syndrome-input decoder exploits their local checks and structure to avoid potentially dense Gaussian elimination.

    Source: §2 · p. 5

  • Results

    The explicit quantum LDPC family approaches capacity with bounded list sizes, and the paper provides near-linear-time list decoding algorithms.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    The construction and decoder provide explicit quantum LDPC codes with list decoding near the quantum Singleton bound and near-linear-time decoding.

    Source: §1.1 · pp. 4–5, §2 · p. 5

    Earlier Sum-of-Squares methods reached only the Johnson radius—about 0.293 for δ ≈ 1/2, well short of the target near 1/2—and incurred large polynomial running time.

    Source: §1 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Classical expander-based codes offered LDPC structure and efficient decoding, but it was unknown whether such combinatorial constructions could match algebraic codes’ list-decoding properties. The paper asks whether explicit quantum LDPC codes can reach capacity and be efficiently list decoded, and answers both questions affirmatively.

1 Introduction

  • It was not known whether combinatorial expander-based constructions could match algebraic codes’ list-decoding properties, despite their potential for LDPC structure and efficient decoding.The paper situates its questions alongside recent expander-based list-decoding results [JS25] [ST25].Source: §1 · p. 3
  • Prior qAEL work approached capacity for approximate quantum error correction and obtained non-LDPC capacity list decoding, while efficient quantum decoders were limited to unique decoding below the (1 − R)/4 scale [DHLV23] [GPT23] [LZ23].The quantum Singleton bound caps relative distance near (1 − R)/2.Source: §1 · pp. 3–4
  • Earlier exact qAEL list decoding reached only the Johnson radius using Sum-of-Squares, which is far from capacity and has large polynomial running time [BJM+24].For δ ≈ 1/2, the stated Johnson radius is approximately 0.293, short of the target near 1/2.Source: §1 · p. 4

1.1 Main result

  • The paper answers both questions affirmatively, giving explicit quantum LDPC codes approaching capacity and near-linear-time list decoding algorithms.The authors describe these as the first explicit quantum LDPC constructions approaching capacity, to their knowledge.Source: §1.1 · p. 4
  • For every target rate R and positive ζ, ξ, the explicit code family has rate at least R and check-matrix row and column weights bounded by a constant.The bound is w on the underlying binary coordinates.Source: §1.1 · p. 4
  • At radius τN ≥ δN − ξ, every X- or Z-syndrome has at most ℓ = O_R,ζ,ξ(1) stabilizer cosets containing a representative of block weight at most τN.The theorem’s randomized decoder outputs a list containing every such low-weight coset with probability 1 − o(1).Source: §1.1 · p. 5
  • The decoder may return extra syndrome-consistent cosets; its guarantee is to include every nearby coset, not to output only those cosets.The paper gives the X-error decoder and says the Z-error case follows by swapping X and Z.Source: §1.1 · p. 5

2 Proof Strategy

The decoder applies quantum AEL amplification and combines syndrome-based local lifting, weak-regularity candidate generation, and outer stitching to list decode up to the amplified distance in near-linear time. Its quantum-specific rigidity argument handles both distinct logical cosets and differences that are stabilizers.

Proof Strategy

  • The construction combines a high-rate outer CSS code, a constant-size inner CSS code, and a regular bipartite expander; its algorithm list decodes up to the amplified distance in near-linear time.The qAEL distance theorem relates the folded code’s distance to the inner-code distance, with loss depending on expansion.Source: §2 · p. 5
  • Local syndrome checks yield one lift per left vertex, avoiding a global solve that could destroy near-linear running time through dense intermediate matrices.The outer syndrome is retained as an affine outer syndrome rather than converted into a global received word.Source: §2 · p. 5
  • The list-size parameter ℓ scales as exp(exp(poly(1/ξ))), and the authors did not attempt to optimize it.This is a stated parameter cost of the construction.Source: §2 · p. 5
  • The decoder forms a left-oriented agreement CSP by listing nearby inner codewords at each left vertex and testing agreement on incident edges.For a low-weight error, expansion gives a large set of left vertices whose true inner blocks are locally listed and satisfy the constraints on a large rectangle.Source: §2 · p. 6
  • Quantum rigidity separates candidates in different logical cosets by quotient distance, while candidates differing by a stabilizer require a separate lower bound on nonzero inner-stabilizer weight.The stabilizer case is not separated by quotient distance alone.Source: §2 · p. 6
  • Weak regularity partitions the left vertices into a constant number of atoms, enabling enumeration of atom-constant assignments that cover low-weight error cosets on the algorithm’s success event.The partition size depends only on decoding slack and local list size.Source: §2 · p. 6
  • Outer stitching projects each surviving assignment to its logical component, decodes it up to an outer stabilizer, then recovers the global error coset without identifying a canonical representative.The final instantiation uses a constant-size inner code, a high-rate quantum Tanner outer code, and a sufficiently strong constant-degree expander.Source: §2 · p. 6

3 Preliminaries

The preliminaries set the code, graph, and complexity conventions, then define the CSS and expander objects used to construct qAEL codes. They also introduce the agreement-CSP and weak-regularity tools used in the decoder.

3 Preliminaries

  • Decoding-time statements assume the code, graph, and fixed local maps are already constructed, with local sizes and field parameters treated as constants.The notation eO suppresses polylogarithmic factors, and high-probability success means probability 1 − o(1) as block length grows.Source: §3 · p. 7

3.1 CSS codes and Quantum List Decoding

  • The section defines block CSS codes, their distances and rate, syndrome-indexed lists of low-weight error cosets, and the bounded-row-and-column-weight condition for LDPC.The LDPC bounds are measured on the underlying Fq-coordinates.Source: §3.1 · p. 7

3.2 Bipartite Spectral Expanders

  • A bipartite graph is an (n, ∆, λ)-expander when its second singular value is at most λ; the section also gives explicit constructions for sufficiently large admissible n.The expander mixing lemma and a stated consequence provide bounds on edges between vertex subsets.Source: §3.2 · p. 8

3.3 Quantum AEL Codes

  • Quantum AEL codes fold concatenated inner and outer CSS spaces, preserve the CSS structure, and have relative folded distance at least δ(C) − λ/∆·δ(D).When the outer family is LDPC and the inner parameters and degree are fixed, the resulting qAEL family is LDPC on the underlying coordinates.Source: §3.3 · p. 10

3.4 Constraint Satisfaction Problems

  • The left-oriented agreement CSP uses labels only on left vertices; right vertices group edge constraints that depend on the selected left label.The general bipartite 2-CSP definition counts satisfied edges, while this special case ignores right-side labels.Source: §3.4 · p. 11

3.5 Weak Regularity on Expanders

  • Weak regularity approximates edge-supported functions using factors with a bounded number of atoms, and functions constant on each atom are measurable with respect to that factor.A function is η-concentrated when it agrees with such a measurable function on at least a 1 − η fraction of points.Source: §3.5 · pp. 11–12

4 The List Decoding Algorithm

The section develops a randomized syndrome-input list decoder for X-errors, with the Z-error decoder obtained by exchanging X and Z. Using weak-regularity factors, value stability, and rigidity, it reduces candidate enumeration to assignments on atoms and achieves near-linear running time with high joint success probability by covering target cosets and applying verified affine outer decoding.

4.1 The Main Statement

  • For fixed local parameters, the syndrome-input qAEL decoder runs in near-linear time when the outer decoder is near-linear, and succeeds with probability 1−o(1).The theorem’s outputs have the input syndrome and a bounded number of cosets; the supplied passages do not expose the bound’s formula.Source: §4.1 · p. 13

4.2 Decoder Notation and Interfaces

  • The decoder computes a local lift and affine syndrome, generates at most Lmax candidate assignments, and affine-decodes each candidate’s projected outer word.The affine decoder returns a verified word or failure; the final list may include extra cosets because low weight is not tested.Source: §4.2 · p. 14, §4.3 · p. 15

4.4 Correctness

  • A candidate sufficiently close to the affine outer word is decoded to a verified output, and stitching that output recovers the target coset.Each assignment contributes at most one representative, bounding output length; candidate generation is the algorithm’s only randomized step.Source: §4.4 · pp. 16–17
  • Candidate generation yields, with probability 1−o(1), a family covering every target coset for the syndrome simultaneously, with at most Lmax assignments.For fixed local parameters, generating and explicitly writing the candidates takes eOε,ℓin(n) time.Source: §4.4 · pp. 16–17

4.5 Candidate Enumeration via Weak Regularity

  • Weak regularity underlies candidate enumeration: low-weight errors induce locally consistent assignments, while local rigidity makes every incorrect label violate at least (ε/2)∆ edges.The section frames this construction as the proof of the candidate-generation guarantee.Source: §4.5 · pp. 17–18
  • Weak-regularity atoms preserve proxy values when assignments have identical label counts in each atom, enabling enumeration by factor-measurable assignments.The concentration argument combines value stability under within-atom rearrangements with rigidity when labels of a fully satisfying assignment change.Source: §4.5 · p. 19
  • The regularity success event provides cut-norm control for every rectangle and covers all target errors simultaneously, without a union bound over errors.The event depends only on the fixed instance, not on the target error or the subsets involved.Source: §4.5 · p. 21
  • The algorithm enumerates factor-measurable assignments and projects them into candidate words, with near-linear running time and joint success probability 1 − o(1).Local list construction and CSP indicators take O(n) time; weak regularity takes eOε,ℓin(n), and constructing the factor and writing all candidates costs Oε,ℓin(n).Source: §4.5 · pp. 20–21

5 Explicit Instantiation

The section instantiates quantum AEL to construct explicit LDPC CSS families at chosen rates, with syndrome-input list decoding on both CSS sides. It combines quantum Tanner outer codes, constant-size inner codes, and explicit expanders.

5 Explicit Instantiation

  • For every target rate R and slacks ζ, ξ, an explicit LDPC CSS family has rate at least R and randomized syndrome decoding that captures all cosets through τ_N ≥ δ_N−ξ in near-linear time.The decoder succeeds with probability 1−o(1) and verifies each output representative’s syndrome.Source: §5 · pp. 21–22, §5.4 · p. 25

5.1 High-Rate Quantum Tanner Outer Codes

  • Quantum Tanner outer codes provide high-rate LDPC families with verified syndrome decoders for errors of weight at most ρ_out n, running in near-linear time.The section takes direct sums of b_out copies to obtain the qAEL outer alphabet while preserving folded rate, distance, and decoding radius.Source: §5.1 · p. 23

5.2 A Constant-Size Inner Code at the Singleton Bound

  • For fixed inner rate and slack, sufficiently large admissible constant Δ yields a binary-linear CSS code whose X and Z codes are classically list decodable at radius τ_inΔ.The separate stabilizer-distance condition is needed for the quantum rigidity lemma; ordinary quotient distance alone does not rule out low-weight stabilizers distinguishing local hypotheses.Source: §5.2 · pp. 23–24

5.3 Expander and Stitching Parameters

  • Explicit bipartite expanders exist for every sufficiently large admissible n, supplying the expander family used in the construction.The qAEL distance theorem is applied to certify the resulting distance.Source: §5.3 · p. 24

Hence (4.5) follows whenever

  • For fixed ε, ℓ_in, δ_out, and ρ_out, taking the constant degree Δ sufficiently large meets the remaining requirements because the spectral ratio, distance loss, and α tend to zero.Their respective orders are O(Δ^−1/2), O(Δ^−1/2), and O(Δ^−1).Source: Hence (4.5) follows whenever · p. 24

5.4 Proof of the Quantum AEL Parameters

  • At thresholds ρ_in=δ_R−ε/2 and δ_R, the inner assumptions and stitching conditions permit applying the decoder theorem on both CSS sides, while fixed inner parameters and an LDPC outer family give LDPC.The application yields the radius, list-size, runtime, completeness, and syndrome-verification guarantees.Source: §5.4 · p. 25

5.5 Proof of the Main Theorem

  • With a near-linear outer decoder and all remaining work near-linear in N, Proposition 5.1 gives the claimed near-linear syndrome-input decoders on both CSS sides.The binary LDPC weight bound is constant in N and depends only on (R, ζ, ξ).Source: §5.5 · p. 26

A Deferred Proofs from the Preliminaries

The deferred proofs establish how folding preserves quotient dimensions and how the qAEL checks retain bounded weights. They also derive an expander-neighborhood estimate from the mixing lemma.

A Deferred Proofs from the Preliminaries

  • The expander mixing lemma bounds the vertices outside S by |B| < λ²n/(Δ²β²), yielding the stated neighborhood conclusion.The symmetric statement follows by interchanging the two sides of the bipartite graph.Source: A Deferred Proofs from the Preliminaries · p. 30
  • Folding is a coordinate permutation, so it preserves quotient dimension; the resulting folded block size is Δb_in with blocklength n.The dimension calculation uses the isomorphism induced by Φ_X.Source: A Deferred Proofs from the Preliminaries · pp. 30–31
  • The qAEL family has bounded binary row and column weights because local checks have constant support and lifted outer checks inherit constant bounds.Folding does not change row weight, and the same bounded-weight argument applies to Z-checks.Source: A Deferred Proofs from the Preliminaries · p. 31

B Existence of the Constant-Size Inner Code

The appendix proves existence of a constant-size inner CSS code by sampling orthogonal subspace pairs and transferring distance and list-decoding properties. A successful pair can be found and verified offline.

B Existence of the Constant-Size Inner Code

  • Uniform marginals for orthogonal pairs let random-subspace distance and list-decoding guarantees transfer to the sampled spaces and their orthogonal complements.List decodability is monotone under passage to a subcode, and the random-linear-code theorem supplies constant local lists at fixed parameters.Source: B Existence of the Constant-Size Inner… · pp. 31–32
  • With positive probability, one orthogonal-pair sample simultaneously gives the required distance and local list-decoding properties, enabling a constant-size inner code.The distance argument establishes the four spaces’ distances, while support-preserving maps transfer the local guarantees to the folded X and Z codes.Source: B Existence of the Constant-Size Inner… · pp. 32–33
  • Trace-dual bases convert the sampled F_Q-subspaces into binary CSS codes while preserving block support and the folded rate.The resulting folded rate is k/Δ=R_in.Source: B Existence of the Constant-Size Inner… · p. 32
  • Because Q and Δ are constants for the eventual family, one can search for a successful orthogonal pair offline and exhaustively verify its required properties.The selected inner code and brute-force local decoder can then be hardwired.Source: B Existence of the Constant-Size Inner… · p. 33
Loading 2609.40313v1…