List Decodable Quantum LDPC Codes

1 Introduction

• QLDPC checks act on few qubits, an implementation-relevant property, while algebraic list-decoding techniques often obstruct the LDPC property.Source: §1 · pp. 3–4

1.1 Our Results

• The quantum AEL procedure combines inner and outer CSS codes by concatenation and folding, and yields list decoding using only unique-decodability of the outer code.With a QLDPC outer code and constant graph degree, the resulting code remains QLDPC.Source: §1.1 · p. 4
• For any constant 0 < ρ < 1 and sufficiently small ε1, ε2, the construction gives polynomial-time constructible QLDPC codes with rate at least ρ, relative distance δ ⩾ 1−ρ−ε1, and efficient list decoding up to τ ≈ J(δ) > δ/2.The result uses an efficient unique decoder for the outer code; the paper gives δ ≈ 1/2 and τ ≈ 0.293 > 0.25 as a parameter choice.Source: §1.1 · p. 4

1.2 Technical Overview

• Sum-of-Squares convex relaxations reduce list decoding of AEL-amplified codes to outer-code unique decoding, using low-degree distance proofs that address quantum distance's SoS obstacle.The new proof separates local and global aspects of distance for the amplified codes.Source: §1.2 · p. 5

1.3 Related work

• Prior AEL-related quantum constructions achieved either list-decodable codes or QLDPC codes, not both simultaneously.Source: §1.3 · p. 6
• The current reduction reaches the Johnson bound, while decoding beyond it remains open; the polynomial-time algorithms are also far from known linear-time unique decoders.The discussion identifies use of additional amplification structure as a possible route beyond the bound.Source: §1.3 · p. 6

2.1 Quantum CSS codes and list decoding

• Quantum CSS codes arise from pairs of subspaces satisfying an orthogonality condition, and are a subclass of stabilizer codes.The section also extends CSS codes to vector spaces, enabling folding in the quantum setting.Source: §2.1 · p. 7
• Folding groups coordinates into blocks, changing the representation and folded dimension while leaving the rate unchanged.The dimension and blocklength both change by the block size.Source: §2.1 · pp. 7–8
• Quantum list decoding takes a syndrome as input and returns a list of possible errors, reflecting no-cloning and the loss of codeword information.Efficient decoding means producing a list containing the possible errors in polynomial time.Source: §2.1 · p. 8

2.2 Duality preserving maps

• Duality-preserving maps let the concatenation construction preserve the orthogonality constraint required for a quantum CSS code.The section constructs such maps using dual systems and applies them to change the base field.Source: §2.2 · pp. 9–10

2.3 Expander Graphs

• The expander definition uses a d-regular balanced bipartite graph whose second singular value is at most λd.The section notes that constant-degree, constant-λ expander families can be obtained from double covers of Ramanujan graphs.Source: §2.3 · p. 10

3.1 Concatenation of CSS Codes

• Concatenating compatible outer and inner CSS codes with duality-preserving maps produces a vector-space CSS code of dimension kout·kin.The construction requires the inner and outer block parameters to match.Source: §3.1 · p. 11
• The concatenated code is LDPC when the outer code is LDPC and the inner block size dbin is constant.Its generators combine sparse outer-code generators with generators whose weight is bounded by dbin.Source: §3.1 · pp. 11–12

3.2 AEL Amplification and Folding CSS Codes

• AEL amplification concatenates the codes, shuffles symbols along expander edges, then gathers right-vertex neighborhoods and folds them into the final code.The graph's vertex-set sizes match the outer blocklength, and its degree matches the inner blocklength.Source: §3.2 · p. 12
• The amplified code F has distance significantly better than the concatenated code E.The next section establishes a lower bound on its distance.Source: §3.2 · p. 13
• AEL amplification changes the metric from left-vertex neighborhoods to right-vertex neighborhoods, where expansion increases codeword separation.The section identifies this metric change as the source of the distance improvement.Source: §3.2 · p. 13

4.1 Partial Minimizer

• A partial minimizer moves a vector closer to a reference codeword without changing its coset.The proof uses it to compare bounds on the distance measured in the concatenated code.Source: §4.1 · p. 14, §4.2 · p. 14

4.2 Distance proof

• The distance proof establishes that non-equivalent codewords are nearly δin apart in the right-vertex metric.The section says the bound can approach the inner-code distance with a sufficiently good expander.Source: §4 · p. 13, §4.2 · p. 14
• The proof invokes the expander mixing lemma to bound the upper side of the partial-minimizer distance comparison.The resulting argument yields the AEL distance bound.Source: §4.2 · pp. 14–15
• For an (n, d, λ)-expander, the folded AEL code has relative distance δR ≥ δin − λδout.The bound is stated for outer and inner CSS codes with relative distances δout and δin, respectively.Source: §4.2 · p. 15

5 Additional Preliminaries: Sum-of-Squares Hierarchy

• The SoS hierarchy supplies increasingly powerful convex relaxations, with level t expressible as an SDP of size n^O(t).Its solutions can be represented by pseudoexpectation operators, and degree-t pseudoexpectations relax distributions over assignments.Source: §5 · pp. 15–16
• SoS solutions enforce constraints expressible by low-degree polynomials, including constraints involving at most k variables at degree k.Local functions depending on k coordinates can likewise be represented by degree-k polynomials.Source: §5 · p. 16
• Conditioning on a local event produces a lower-degree pseudoexpectation that continues to respect the original constraints.Conditioning on a k-local event reduces the degree from t to t−2k when the event has positive pseudoexpectation.Source: §5 · p. 17

5.1 SoS relaxations for codes

• The code-specific SoS setup defines AEL pseudocodewords and their distances, then uses an expander-mixing variant inside the SoS proof system.The variant exploits non-negativity of sums of squares of low-degree polynomials.Source: §5.1 · pp. 18–19

• The partial minimizer is extended to a vector-valued local function for use inside pseudoexpectations, with monotonicity defined to hold locally.Source: §6 · p. 19
• The distance bound for η-good pseudocodewords is the key statement needed to apply the framework of [JST23] to quantum AEL.Source: §6 · p. 19
• The proof follows the earlier distance argument by bounding the expected disagreement quantity from below and above.Source: §6 · pp. 19–20
• The expander mixing lemma supplies the upper bound in the distance proof.Source: §6 · p. 20

7.1 Covering Lemma

• For quantum AEL codes, the alphabet-free Johnson bound limits the list to at most sd · n + 1 cosets.The covering argument bounds the list using the support size of a distribution over EX.Source: §7.1 · p. 21
• The algorithmic covering lemma finds a degree-t pseudocodeword in time n^O(t) that preserves covering properties for nearby codewords.It optimizes a convex function over pseudocodewords, which can be found via semidefinite programming.Source: §7.1 · p. 22

7.2 Putting things together

• Random conditioning makes the pseudocodeword η-good so the SoS distance proof applies, and repeated trials recover the full list with high probability.Each coset has a small but constant chance of being output in one trial; the algorithm repeats trials and uses a union bound.Source: §7.2 · pp. 23, 25
• With an outer code uniquely decodable to radius δdec and λ < δdec, the randomized SoS decoder returns a list containing the true cosets with probability at least 1 − γ.The stated algorithm uses s^O(d)/ε^4 levels of the SoS hierarchy.Source: §7.2 · pp. 23–24
• The randomized algorithm immediately gives a list-size upper bound of 1/p, with better combinatorial bounds available from the covering lemma and approximate Carathéodory theorem.The paper notes that pruning the list is difficult for quantum codes, motivating a derandomized version with much larger list sizes.Source: §7.2 · pp. 23, 27

7.3 Derandomization

• Algorithm 7.7 can be derandomized by enumerating its random choices and using common-threshold rounding, yielding a deterministic polynomial-size list in O(qbout n)·T(n) time.The shared threshold produces only qbout·n distinct roundings to try.Source: §7.3 · pp. 27–28

7.4 Near-MDS Quantum LDPC Codes list decodable up to Johnson bound

• For every 0 < ρ < 1 and 0 < ε1, ε2 < 1/2, an infinite QLDPC family has rate at least ρ, distance at least 1−ρ−ε1, and list decoding to the Johnson bound.The theorem obtains the family by instantiating AEL distance amplification; the amplified code remains LDPC.Source: §7.4 · pp. 28–29
• The construction uses a quantum Reed–Solomon inner code and a folded [LZ23] binary QLDPC outer code, preserving its rate and unique-decoding properties after folding.AEL amplification preserves the outer code’s LDPC property in the final code.Source: §7.4 · pp. 28–29

• The appendix presents correlation-rounding proofs largely borrowed from [JST23], for pseudocodewords viewed as relaxations of distributions on edge assignments.Source: A Correlation Rounding · p. 33
• Conditioning on a random right vertex decreases average pseudovariance in L in proportion to average covariance across uniformly chosen pairs in L × R.Source: A Correlation Rounding · p. 33
• A pseudocodeword that is not η-good loses average pseudovariance by Ω(η^2) under random conditioning, yielding an η-good pseudocodeword after a small constant number of conditionings depending on η.Source: A Correlation Rounding · pp. 33–34
• The resulting factorization of pseudoexpectations applies only to products arising from the uniform measure on L × R.Source: A Correlation Rounding · p. 34

• The vector-valued expander mixing bound follows by applying ordinary expander mixing coordinate-wise and then using Cauchy–Schwarz.Source: B Expander Mixing Lemma for SoS · pp. 34–35
• SoS non-negativity proves a matrix is positive semidefinite, enabling vector-valued expander mixing to establish expander mixing for pseudoexpectations.Source: B Expander Mixing Lemma for SoS · p. 35
• Only the positive-semidefinite step uses SoS non-negativity; the remaining argument can also use linear-programming hierarchies.Source: B Expander Mixing Lemma for SoS · p. 35
• The proof's pseudoexpectation matrix is shown positive semidefinite by checking that its quadratic form is nonnegative for every vector.Source: B Expander Mixing Lemma for SoS · p. 35

C Covering Lemma

• Claim C.2 states that the norm-minimizing g0 in T satisfies ⟨g0, χ(h)⟩ > α^2 for every h ∈ H.Source: C Covering Lemma · p. 36
• The lemma constructs a distribution D with support at most sd·n+1 by expressing g0 as a convex combination of elements in χ(EX).Carathéodory's theorem supplies the support bound.Source: C Covering Lemma · p. 36
• To prove Claim C.2, the argument considers a convex mixture of g0 and χ(h) that would have smaller squared norm if some h had inner product at most α^2.The proof expands the mixture's squared norm and says its quadratic minimum is strictly below ∥g0∥² when ∥g0∥ > α.Source: C Covering Lemma · p. 36