PaperlayerView exact revision on arXiv

Source-linked AI summary

From Random Quantum Codes to Explicit qLDPC Codes via Local Properties

Fernando Granha Jeronimo, Xiaojuan Ma, Nikhil Shagrithaya

arXiv:2609.40252v1cs.ITmath.ITquant-ph

TL;DR

The paper addresses the challenge of constructing explicit quantum LDPC codes with properties associated with optimal random codes. It develops a quantum LCL framework and uses it to construct explicit qLDPC families with list-decoding and list-recovery properties.

  • Problem

    Constructing explicit codes with the optimal properties of random codes remains elusive, especially when the quantum codes are required to be LDPC.

    Source: §1 · p. 4

  • Method

    The paper develops a quantum LCL framework and uses a CSS-AEL construction to preserve qLCL guarantees for folded properties.

    Source: §1 · p. 5, Construction: derandomizing LCL via AEL · p. 8

  • Results

    The paper gives explicit qLDPC families that are quantum list decodable and list recoverable, plus folded CSS constructions excluding specified injective-logical qLCL witnesses.

    Source: Construction: derandomizing LCL via AEL · pp. 8–9

  • Takeaways & Limitations

    The constructions retain qLDPC, and relative subspace-design constructions arise by specializing the profile class to kernel profiles.

    Source: Construction: derandomizing LCL via AEL · p. 8

    Random-ensemble expectations are taken over PCSS; the uniform exact-dimensional model is stated to satisfy the same estimate only up to a standard constant.

    Source: §4.3 · p. 16, §8.1.1 · p. 23

Abstract

from arXiv · show

Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code be an LDPC code. Local coordinate-wise linear (LCL) [Levi, Mosheiff, and Shagrithaya, FOCS 2025] witnesses provide a unifying language for many coding-theoretic properties, from distance to list decoding and list recovery. In particular, it provides a framework to study properties of random linear codes, which achieve optimal parameters for many properties of linear codes. For CSS quantum codes, however, a local witness has two distinct ranks: its physical rank before quotienting by stabilizers and its logical rank after quotienting. We develop a quantum version of the LCL framework for nested spaces $S \subseteq C$, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient $C/S$. The resulting theory gives a threshold theorem for random CSS codes, and as a consequence shows that the per-sector rate threshold is equal to the classical rate threshold. We also define a quantum analogue of subspace design [Guruswami and Xing, STOC 2013] and show that they can be described in a natural manner within the quantum-LCL framework. Finally, we give explicit constructions for arbitrary folded quantum-LCL properties, in a manner similar to the LCL derandomization of [Jeronimo and Shagrithaya, STOC 2026]. As a consequence, we obtain the first explicit constructions of quantum list-decodable codes and list-recoverable codes that have optimal list sizes, in addition to explicit quantum subspace design codes. We note that all our explicit constructions are qLDPC codes, an important property for quantum error-correcting codes.

1 Introduction

The introduction presents a quantum LCL framework for CSS codes that distinguishes physical representatives from logical independence in the quotient, and applies it to local properties and relative subspace designs. It outlines the paper’s contributions on quotient LCL thresholds and explicit qLDPC constructions for quantum list recovery and decoding.

1 Introduction

  • Classical LCL theory established rate thresholds for random linear codes and AEL-based explicit LDPC constructions for LCL properties [JS26], motivating quantum analogues.The introduction frames explicit quantum LDPC codes with optimal properties as a central challenge.Source: §1 · p. 4

Quantum LCL

  • For fixed witness width and local profile, the quotient-minor gap determines whether a flagged witness is absent or present with high probability in a random nested pair.The flag separates stabilizer-valued directions, governed by the codimension of S, from logical directions, governed by the codimension of C.Source: Quantum LCL · p. 7

Relative CSS subspace designs

  • Relative CSS subspace designs test physical representatives while requiring test subspaces to inject into the logical quotient; avoiding kernel-profile witnesses characterizes the design property.A CSS code must satisfy the relative design property in both sectors.Source: Relative CSS subspace designs · p. 8

Construction: derandomizing LCL via AEL

  • An explicit folded CSS family achieves quantum rate at least R − O(ε), excludes specified injective-logical qLCL witnesses, and is qLDPC.The construction uses AEL-robust folded qLCL gadgets; specializing to kernel profiles yields relative subspace-design codes.Source: Construction: derandomizing LCL via AEL · pp. 8–9
  • The work also gives explicit qLDPC quantum list-decodable and list-recoverable codes with optimal list sizes, including an infinite family with constant alphabet size.The list-decoding family has rate RQ and is (ρ, L)-quantum list decodable; its alphabet size depends only on R, ε, and L.Source: Construction: derandomizing LCL via AEL · p. 9
  • Compared with, the construction has constant rather than polynomial list size; compared with [BJM+24], its list-decoding radius exceeds the Johnson-bound radius, and all three constructions yield qLDPC codes over constant alphabets.Source: Construction: derandomizing LCL via AEL · p. 9
  • Theorem 1.12 announces an infinite family of qLDPC codes that are quantum list recoverable, with alphabet size depending only on R, ε, ℓ, and L.The supplied informal statement does not include the family’s parameter conditions.Source: Construction: derandomizing LCL via AEL · p. 9

Main-result map

  • The result map links Theorems 1.6, 1.9, 1.10, and 1.11–1.12 to formal threshold, gadget, explicit CSS-family and subspace-design, and list-recovery and list-decoding results, respectively.Source: Main-result map · p. 10

Contributions and organization

  • The paper formulates quotient LCL properties for nested pairs S ⊆ C, including logical flags and quotient-minor gaps, and proves a sharp fixed-type threshold theorem for random nested pairs.Source: Contributions and organization · p. 10
  • It introduces relative CSS subspace designs, proves their deterministic profile characterization, and identifies minimal bad profiles for expander amplification.Source: Contributions and organization · p. 10
  • It derandomizes folded qLCL profile classes using AEL-robust constant-size inner CSS gadgets and proves the corresponding CSS-AEL lifting theorem.Source: Contributions and organization · p. 10
  • The resulting explicit constructions include quantum list-decodable and list-recoverable codes with optimal list sizes, as well as quantum subspace-designable codes.Source: Contributions and organization · p. 10

2 Preliminaries

The preliminaries recast local code properties in terms of bounded-width witnesses with prescribed row spaces. For nested pairs, they distinguish a witness’s physical span from its logical image modulo stabilizers.

2 Preliminaries

  • The framework adds a logical row space to the LCL viewpoint, measuring a witness’s image in the quotient while retaining its ordinary row space.Folded vector alphabets are introduced after the threshold theorem, leaving the probabilistic argument in the scalar setting.Source: §2 · p. 10, §2.2 · pp. 11–12

2.1 Local profiles and row spaces

  • A b-local profile specifies coordinate-wise row constraints, while profile mass counts matrices satisfying those constraints within a row space.The exact row-span count bounds how many such matrices have row span equal to the specified space.Source: §2.1 · pp. 10–11

2.2 Nested pairs and logical row spaces

  • For a nested pair S ⊆ C, the quotient C/S is the logical quotient, and the witness’s logical row space records independent directions represented by its columns there.The kernel of the column map consists of linear combinations of columns that are stabilizers.Source: §2.2 · pp. 11–12
  • Logical distinctness constraints can distinguish columns by their cosets modulo S, rather than requiring distinct physical codewords.The profile condition is equivalent to excluding certain coordinate-difference vectors from the orthogonal complement of the logical row space.Source: §2.2 · p. 12

3 Quotient LCL properties

Quotient LCL properties extend local witnesses to nested spaces by tracking both physical row space and logical row space modulo stabilizers. The section develops flags, quotient minors, and a random-pair analysis for threshold estimates.

3 Quotient LCL properties

  • A quotient LCL witness obeys coordinate-wise profile constraints while its physical row space U and logical row space T are tracked separately.The logical flag is the additional data that adapts the classical LCL formalism to CSS codes.Source: §3 · p. 12, §3.1 · p. 13

3.1 Flags and realizations

  • A realization is a bounded-width matrix with columns in C, and its flag records ordinary and logical row spaces subject to dimension feasibility.In a fixed nested pair, realizable flags must be feasible; in the unconditioned parity-check ensemble, parity-feasibility suffices for the exact second-moment argument.Source: §3.1 · pp. 12–13

3.2 Quotient minors

  • Passing to a quotient minor along W < U changes the logical row space to T ∩ W, the logical directions that survive the restriction.The quotient construction preserves the local profile constraints and keeps the new matrix’s columns in C.Source: §3.2 · p. 13

4 Random nested linear pairs

  • The parity-check ensemble gives independent random checks before full-rank conditioning, enabling exact fixed-matrix and second-moment estimates.Conditioning on full rank recovers the uniform nested-subspace model.Source: §4 · p. 14, §4.1 · p. 14

4.2 Potential and quotient-minor gap

  • The parity-check cost of a flag is κ(U,T) = au + c(u − t), charging ordinary directions for C containment and stabilizer directions for S containment.Equivalently, stabilizer directions pay codim S and logical directions pay codim C.Source: §4.2 · p. 14
  • The quotient-minor gap compares a witness’s potential with the potential of its proper minors, where the logical part of each minor is T ∩ W.A positive quotient-minor gap implies positive raw potential.Source: §4.2 · p. 14

4.3 A fixed matrix

  • For a fixed flagged matrix, the probability its columns lie in C and its logical row space is T is q^-κ(U,T) ι(c,t).The expression includes an injectivity factor for the induced logical map; it is zero when t > c.Source: §4.3 · p. 15

5 Fixed-type threshold theorem

The fixed-type theorem uses quotient-minor gaps to distinguish when a flagged local witness is unlikely or likely to occur in a random nested pair. Its subcritical argument uses a first moment, and its supercritical argument controls dependent witness pairs with a second moment.

5 Fixed-type threshold theorem

  • The fixed-type theorem combines the subcritical first-moment bound with a supercritical second-moment bound for one profile and flag.The subcritical argument applies to a bad quotient minor; the supercritical argument controls the joint logical row space of dependent witnesses.Source: §5 · p. 16, §5.3 · p. 19

5.1 Subcritical direction

  • When the quotient-minor gap is negative, a proper minor witnesses the obstruction, so a first-moment bound on that minor controls the probability of the original type.The minor’s logical row space is T ∩ W, and its potential is related to the original type’s potential.Source: §5 · p. 16, §5.1 · p. 16

5.2 Joint flags and second moment

  • The supercritical proof separates independent witness pairs from dependent pairs by tracking their joint ordinary and logical row spaces.For pairs with full direct-sum joint row span, the parity-check restrictions are independent; the remaining contribution is bounded before applying Chebyshev’s inequality.Source: §5.2 · pp. 17–19

5.3 Fixed-type theorem

  • Theorem 5.6 fixes a b-local profile V and flag (U,T) with U ≠ 0; its supplied case (b) requires dim T ≤ m1 − m0, Γm0,m1(V,U,T) ≥ ε, and ε ≥ 2b² + 1.Source: §5.3 · p. 19

6 Threshold theorem for quotient LCL properties

The paper extends fixed-type bounds to quotient LCL properties and transfers them to uniform nested pairs. It then relates the nested-pair framework to CSS sectors and compares their rate thresholds with the classical threshold.

6 Threshold theorem for quotient LCL properties

  • The quotient LCL property threshold is governed by the largest feasible quotient-minor gap across its profiles and logical row spaces.When the gap is Ω(n), the bounds give exponentially sharp high-probability statements in the stated large-alphabet setting, even for profile families exponential in n but independent of q.Source: §6 · pp. 19–20

7 Uniform nested subspaces

  • Conditioning the parity-check ensemble on full rank yields the uniform nested ensemble, transferring the threshold theorem with only a constant loss in probability.The uniform-model maximization is restricted to flags feasible for the fixed dimensions.Source: §7 · pp. 20–21

8.1 Joint Sector Formulation

  • The joint-sector formulation analyzes qLCL behavior through the individual X and Z sectors.The framework applies the one-sector nested-pair theory to each sector before formulating joint-sector behavior.Source: §8 · p. 21, §8.1 · p. 22

8 CSS codes

  • A CSS code from S ⊆ C has X-type stabilizer labels S, Z-type stabilizer labels C⊥, and an X-logical quotient C/S.The joint logical quotient decomposes into the X- and Z-sector quotients.Source: §8 · p. 22

8.1.1 The normalized slope

  • If the normalized slope λ stays bounded away from 1, a random CSS code avoids realizing the flagged type with high probability.The paper defines a single-sector rate threshold and states that rates below it give low realization probability for the fixed type.Source: §8.1.1 · pp. 23–24
  • For every nonzero fixed flag, the one-sector rate threshold is at least the classical rate threshold, with equality when T = U.For a realized witness, T = U exactly when its image intersects the sector’s stabilizer space only in zero.Source: §8.1.1 · p. 24

X (V; UX, TX), Rflag

The section defines joint realization of local profiles for CSS codes, extending analysis from individual logical sectors to their joint logical space. CSS structure makes it possible to study joint avoidance through the individual sectors.

X (V; UX, TX), Rflag

  • The classical rate threshold for a finite profile family is the minimum classical threshold across profiles and allowed subspaces.The section’s proof applies the threshold bound twice and uses dim(UX + UZ) − dim W to obtain the claim.Source: X (V; UX, TX), Rflag · p. 24

8.1.2 Joint Realization

  • Joint logical-space behavior can be analyzed through the individual X and Z sectors: avoiding either sector realization prevents all columns of the joint matrix from appearing simultaneously.A joint profile is realized using matrices whose rows satisfy the local profile and whose columns belong to the corresponding sector spaces.Source: §8.1.2 · p. 25
  • A joint realization is defined using sector matrices for X and Z that together realize the profile and the combined subspaces and types.The definition requires sector matrices with rows constrained by the local profile and columns in their respective sector spaces.Source: §8.1.2 · p. 25
  • To require pairwise-distinct coset representatives, the framework avoids joint realizations whose combined type lies in LDistb.Source: §8.1.2 · p. 25

X (V; UX, TX), Rflag

The section establishes that the joint rate threshold for CSS codes equals the classical rate threshold. Below the sector thresholds, joint realizations are correspondingly unlikely.

X (V; UX, TX), Rflag

X (V; UX, TX) rZ < Rflag

  • The joint rate threshold equals the classical rate threshold for arbitrary sector parameters.The proof bounds the joint threshold by the classical one in both directions.Source: X (V; UX, TX) rZ < Rflag · pp. 25–26

X (V; UX, TX), Rflag

The section applies threshold preservation to joint-sector realization, the balanced CSS setting, and list-decoding and list-recovery consequences. In the balanced case, the rate condition simplifies, while the list-recovery bounds remain non-tight.

X (V; UX, TX), Rflag

  • The joint-sector event concerns a profile realized by combined X and Z subspaces and types, and its probability is bounded by a union bound over admissible choices.The proof then applies Proposition 8.5.Source: X (V; UX, TX), Rflag · p. 26

8.2 The Balanced Case

  • When kX = kZ, the condition max{rX, rZ} + δ ≤ Rcl(F) reduces to (1 + RQ)/2 + δ ≤ Rcl(F).In this balanced case, rX = rZ = (1 + RQ)/2.Source: §8.2 · p. 26

8.3 Consequences of Theorem 8.11

  • Threshold preservation lets bounds for random linear codes be applied to random CSS codes, and the list sizes are the same in the classical and quantum settings.The text contrasts this with, which gives list sizes L and L2, respectively, and notes that Section 12 derandomizes the matching-size result.Source: §8.3 · pp. 26–27
  • The list-decoding corollary follows by combining threshold preservation with the list-decoding upper and lower bounds of.Source: §8.3 · p. 26
  • For list recovery, the section states a lower-bound consequence based on, while the known bounds are not tight.[GG26] established a list-recovery guarantee for random linear codes; the section does not claim matching bounds.Source: §8.3 · p. 27

9 qLCL for Folded Coordinates

Section 9 extends the qLCL framework to folded coordinates, formulating local constraints while tracking physical and logical row spaces. It develops threshold statements for folded coordinates and joint sectors, and introduces kernel profiles for subspace-design constraints and their relative CSS version.

9.1 Folded coordinates

  • A folded length-n ambient space uses W^n, with local profiles imposing constraints separately on its folded coordinates.The section defines coordinate-zero subspaces and coordinate ranks for subspaces of W^n.Source: §9.1 · p. 27

9.2 Bilinear forms and CSS notation

  • The CSS formulation uses a nondegenerate coordinatewise Fq-bilinear pairing, which faithfully captures subspace commutation, while distance guarantees use the folded block metric.For W = Fs_q, a block-weight lower bound δn gives scalar relative distance at least δ/s, not necessarily δ; the construction is binary in the folded sense with Singleton-scale guarantees.Source: §9.2 · pp. 28–29

9.3 Folded qLCL witnesses

  • Folded qLCL witnesses distinguish the ordinary row space of a map from its logical row space after quotienting by S.A folded realization M has image in N and a prescribed logical row space ΛS(M), which equals the ordinary row space exactly when M(B) ∩ S = 0.Source: §9.3 · p. 29
  • When the folded quotient-minor gap is at most -epsilon, the folded parity-check ensemble admits a realization of the specified property with high probability.The subcritical result applies to nonzero U and T ≤ U; its proof uses quotient data and a first-moment bound.Source: §9.3 · p. 32
  • The folded threshold analysis adapts the scalar proof because local constraints can couple the s scalar rows within each coordinate, while its counting steps retain the same statements and constants.The section also establishes folded pair submodularity and a dependent-pair bound under a positive folded gap.Source: §9.3 · p. 33
  • The fixed-type threshold and the broader threshold theorems carry over verbatim to folded qLCL, with folded potentials and the same constants.The folded framework is a strict generalization of the scalar theory, not a reduction to it.Source: §9.3 · pp. 34–35

9.4 Joint Sector Formulation

  • The joint-sector formulation replaces scalar subspaces and profiles with subspaces of B* and folded profiles, and states a probability corollary for joint-sector satisfaction.In the balanced case, the stated condition is max{rX, rZ} + δ ≤ Rcl(F).Source: §9.4 · p. 35

9.5 Kernel profiles

  • Kernel profiles impose constraints by prescribing kernels, yielding local tests used to construct subspace-design codes.A coordinate map is allowed exactly when it vanishes on the coefficient directions annihilated by the prescribed subspace.Source: §9.5 · p. 35
  • At the actual normalizer rate ρN, the subspace-design potential equals the normalized qLCL potential; for α > ρN, negative α-design potential implies negative qLCL potential with slack (α − ρN) dim U.Quotient minors U′ < U test the same profile on all nonzero subspaces U′ ≤ V.Source: §9.5 · p. 36
  • The relative CSS definition permits nonzero S while explicitly requiring the tested representative subspace to have trivial intersection with S.After relabeling T = U, the quotient threshold theorem reduces to the classical fixed-width LCL threshold [LMS25, Section 4].Source: §9.5 · p. 36

10 Relative subspace designs for CSS codes

Relative subspace designs impose local zero constraints on physical representatives while requiring the tested subspace to inject into the logical quotient. The section characterizes these designs through relative profiles and folded quantum-LCL witnesses.

10.1 Definitions

  • A relative design tests subspaces A ≤ N with A ∩ S = 0, so stabilizer-only directions are excluded while coordinate zeros remain measured on physical representatives.The quotient N/S does not have coordinatewise representatives with a unique zero pattern, so the representative is tested before quotienting.Source: §10 · p. 37, §10.1 · p. 37

10.2 Basic properties

  • Ordinary α-subspace designs imply relative α-designs, and relative designs are preserved by restricting N or enlarging S.Both inheritance statements follow because these changes reduce the subspaces that must be tested.Source: §10.2 · p. 38
  • Relative-design validity up to dimension 1 yields a lower bound on logical distance for vectors in N \ S.The CSS version applies the relative-design condition in both sectors.Source: §10.2 · p. 38

10.3 Contained profiles and deterministic equivalence

  • Relative-design validity is equivalent to nonnegative design potential for every contained relative profile of dimension at most r.The profile characterization identifies these witnesses with folded qLCL realizations whose ordinary and logical row spaces both equal the profile space.Source: §10.3 · p. 39

11 Robust inner LCL

The section defines robustness for folded local constraints that may have stabilizer kernels, then uses random normalizers to obtain robust nested CSS inner gadgets. Kernel profiles recover relative subspace designs as a specialization.

11 Robust inner LCL

  • AEL-robust folded LCL handles maps whose kernels may consist of local stabilizers; kernel profiles specialize this framework to relative subspace designs.For kernel profiles, the entropy exponent is at most r^2, and their potential agrees with the subspace-profile potential.Source: §11 · pp. 40–41

11.1 Random normalizers are robust for LCL

  • With probability at least the theorem's stated bound, a random normalizer is simultaneously AEL-robust for every stabilizer subspace S it contains.The theorem applies to folded profile classes with bounded entropy exponent; the kernel-profile corollary gives robust relative designs when s ≥ C′r^2/ε.Source: §11.1 · p. 43

11.2 Random nested CSS inner gadgets

  • When ρX + ρZ > 1, random nested CSS inner gadgets are simultaneously robust in both sectors, and fixed-parameter gadgets can be found by exhaustive search.The two sector parameters are ρX + ε and ρZ + ε, with success probability at least 1 − q^−Ω(εsd).Source: §11.2 · p. 44

12 The CSS-AEL construction

The CSS-AEL construction combines robust inner CSS gadgets, outer logical distance, and an expander transform to produce global folded-LCL guarantees. Its lifting theorem yields CSS subspace designs when the inner pair is robust in both sectors.

12 The CSS-AEL construction

  • The CSS-AEL transform uses robust inner codes at left vertices, an outer code for inner logical symbols, and an expander permutation to regroup edge symbols.It turns inner LCL robustness and outer logical distance into a global LCL guarantee; relative subspace design is the kernel-profile case.Source: §12 · p. 45

12.1 Explicitness convention

  • Explicitness means polynomial-time output of generator or parity-check matrices, with exhaustive search over constant-size objects counted as explicit.Hidden constants may depend on fixed design dimension, target rate, and accuracy, but not block length.Source: §12.1 · p. 45

12.2 Expanders

  • The construction uses a d-regular bipartite λ-expander, with a regular multigraph allowed and the proof relying on its normalized biadjacency operator.The stated parameter theorems use explicit expanders with λ = O(d^−1/2).Source: §12.2 · p. 45

The CSS-AEL code is the CSS code defined by the nested pair

  • The nested global pair defines a valid CSS code, and its quantum rate is the product of the inner and outer rates.Exact CSS orthogonality is established before the rate calculation.Source: The CSS-AEL code is the CSS code… · p. 47

12.5 The lifting theorem

  • The AEL lift rules out global folded-LCL witnesses by combining inner robustness with outer logical distance.For relative subspace designs, robust inner pairs in both sectors and the stated expander condition yield an (αX + ϵ, αZ + ϵ)-CSS subspace design up to dimension r.Source: §12.5 · pp. 48–50
  • The lift's global guarantee is itself a folded-LCL property, with its explicit instantiation stated in that form.The subspace-design conclusion is the kernel-profile specialization.Source: §12.5 · p. 50

13 Leverrier–Z´emor quantum Tanner codes as outer codes

The section adapts binary quantum Tanner outer codes to the inner logical alphabet by scalar extension. The extension preserves rate and does not reduce block logical distance, and the Leverrier–Zémor family supplies explicit outer codes with high rate and positive distance in both sectors.

13.1 Scalar extension of binary CSS outer codes

13 Leverrier–Z´emor quantum Tanner codes as outer codes

  • The binary outer code's symbols are extended to the inner logical vector space; the resulting AEL outer symbols are not single bits.Source: §13 · p. 50

13.2 The Leverrier–Zémor outer family

  • The Leverrier–Zémor outer family is explicit, with quantum rate at least 1 − ξ and block logical distances at least δLZ(ξ)n in both sectors.Source: §13.2 · p. 51

14 Explicit parameter instantiation

The section gives an explicit AEL-based folded CSS construction from bounded-entropy profile ensembles, with rate near the target and folded-LCL guarantees up to dimension r.

14 Explicit parameter instantiation

  • The construction combines an AEL-robust inner CSS gadget with an outer CSS family having rate close to one and constant block logical distances in both sectors.The inner gadget handles the supplied profile classes; the outer code is over the logical alphabet produced by that gadget.Source: §14 · p. 52
  • The inner gadget can be made deterministic by exhaustive search because its parameters are constant and the profile ensembles are explicit.The construction requires the profile classes to be supplied uniformly in the inner parameters, which it chooses last.Source: §14 · pp. 51–52
  • Under the stated outer-code assumptions, the construction gives explicit folded CSS codes of quantum rate at least R − O(ε) that are folded LCL up to dimension r.The theorem applies to explicit folded profile ensembles in both sectors.Source: §14 · p. 52
  • The resulting fold size is poly(r, h, 1/ε)q^O(r^2).The parameters s and d, and therefore the fold size sd, are independent of the block length n.Source: §14 · p. 53

15 Consequences of Derandomization

The paper applies its derandomization theorem to folded profile ensembles, yielding explicit quantum list-decoding and list-recovery codes with optimal list sizes, as well as CSS subspace designs and distance guarantees.

15 Consequences of Derandomization

  • Theorem 14.2 yields explicit CSS constructions for folded profile ensembles, with folded-LCL guarantees up to dimension r when the sector rates satisfy the stated condition.The theorem is presented for arbitrary explicit folded profile ensembles.Source: §15 · p. 53
  • The constructions give explicit folded quantum list-decodable and list-recoverable codes with optimal list sizes.The list-decoding theorem gives rate RQ − O(ε) and fold alphabet size Sfold = poly(L, 1/ε)q^O(L^2).Source: §15 · pp. 53–54
  • Specializing to kernel profiles yields CSS subspace designs up to dimension r, with αX and αZ at most (1 + R)/2 + O(ε).The design condition strengthens the distance bound from dimension one to all dimensions up to r.Source: §15 · p. 54
Loading 2609.40252v1…