PaperlayerView exact revision on arXiv

Source-linked AI summary

Good Quantum Locally Testable Codes from Product Expansion

Mitali Bafna, Anqi Li, Quynh T. Nguyen

arXiv:2609.26735v1quant-phcs.CCcs.ITmath.IT

TL;DR

The paper addresses the polylogarithmic losses in prior quantum LTC constructions and asks whether structured Reed–Solomon codes can improve their parameters. It combines the DLV high-dimensional expansion framework with non-Abelian cubical complexes and symmetry-compatible local codes, obtaining constant-parameter quantum codes under a product expansion conjecture.

  • Problem

    The DLV construction has inverse-polylogarithmic distance and soundness because Abelian Cayley graphs require Θ(log n) generators for constant spectral gap, while using structured RS codes as local codes poses a further open question.

    Source: §1.1 · p. 3, §2.2 · p. 5

  • Method

    The construction instantiates the DLV framework on non-Abelian cubical complexes with symmetry-compatible Reed–Solomon local codes whose product expansion is assumed.

    Source: §1.1 · p. 3, §2.4.1 · p. 8, §5 · p. 17

  • Results

    Assuming Conjecture 5.6, an infinite family of quantum CSS codes on N qubits has K = Ω(N), D = Ω(N), constant soundness, and constant check weights.

    Source: §5.5 · p. 21

  • Takeaways & Limitations

    Using non-Abelian complexes crosses the DLV polylog bottleneck, and compatible local-code symmetries let the framework lift product expansion to global quantum local testability.

    Source: §1.1 · p. 3

    The construction’s stated guarantees are conditional on Conjecture 5.6, the product expansion conjecture over binary extension fields.

    Source: §5.4 · p. 20

Abstract

from arXiv · show

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.

1 Introduction

The introduction frames good locally testable codes as a goal and asks whether structured Reed–Solomon local codes can improve quantum LTC parameters. The paper presents a conjecture-dependent construction using non-Abelian cubical complexes and symmetry-compatible local codes.

1 Introduction

  • High-dimensional expansion constructions use cubical complexes and local codes whose tensor products are robustly locally testable, a property lifted to global testability.The paper calls this local-code property product expansion [PK22a] [KP25].Source: §1 · p. 2
  • Earlier work obtained almost-good qLTCs with constant rate and locality but inverse-polylogarithmic distance and soundness; good classical LTCs had also remained an open goal.Good qLTC parameters improve those applications that use almost-good qLTCs.Source: §1 · p. 2

1.1 Our Work

  • The motivating question is whether structured RS codes can serve as local codes in the DLV framework, improving on prior RS-based quantum codes with dense Z checks.Source: §1.1 · p. 3
  • Assuming Conjecture 5.6, an explicit binary quantum CSS code family has constant rate, quantum distance, soundness, and locality.Source: §1.1 · p. 3
  • Non-Abelian cubical complexes bypass the polylog bottleneck, while compatible Reed–Solomon symmetries make every local view a tensor codeword whose product expansion lifts to global local testability.The construction uses the DLV framework with an appropriate choice of RS codes.Source: §1.1 · p. 3

2 Technical Overview

The overview builds from local constraints on cubical complexes to a quantum construction using non-Abelian complexes and Reed–Solomon codes. Its key ingredients are symmetry-compatible local views and a conjectured high-rate product expansion property.

2.1 LTCs from Left-Right Cayley Complexes

  • In the Left-Right construction, edge constraints make vertex views tensor codewords; robust testability of those views lifts to global local testability.Constraint counting gives rate 2rate(CA) + 2rate(CB) − 3, positive when the local-code rates sum to more than 3/2.Source: §2.1 · p. 4

2.2 Generalizing to Higher Dimensions

  • The DLV higher-dimensional framework requires expanding Cayley graphs, high-rate local codes with product expansion, and face views that are tensor codewords; Abelian generators incur Θ(log n) size and polylogarithmic losses.Source: §2.2 · p. 5

2.3 Constructing LTCs over Right-Right Non-Abelian Cayley Complexes

  • Right-Right non-Abelian complexes create endpoint-dependent label permutations, so local codes must be invariant under those symmetries for every vertex view to remain a tensor codeword.The complex requires AB = BA and |AB| = |A||B| to define its squares.Source: §2.3 · pp. 5–6

2.4 Our Construction in 2-Dimensions: Complex and Local Codes

  • Projective Reed–Solomon codes fit the RSV complex’s projective-line labels, but induced permutations introduce scaling factors that must be handled to preserve tensor-code local views.Compatible face matrices allow edge-specific scaled PRS constraints and vertex-specific scalars.Source: §2.4 · pp. 6–7

2.4.1 Product Expansion of Reed-Solomon Codes

  • High-rate RS product expansion fails on shared domains such as Fq⋆, motivating carefully chosen coprime-order subgroups; the construction conjectures a higher-dimensional variant over binary extension fields.The chosen 4-dimensional complex uses edge-label domains P1(Fsi), with si powers of 2, so its vertex views are tensor PRS codes to which the conjectured product expansion applies.Source: §2.4.1 · pp. 7–8

3 Preliminaries

The preliminaries define cubical complexes built on group cosets and projective Reed–Solomon codes, including their duality and symmetry properties.

3.1 Cubical Complexes

  • Vertices are pairs in (G/H) × {0, 1}^k, and cubes in directions S have dimension |S| with faces formed by fixing type bits.Source: §3.1 · p. 8
  • Two incident edges in distinct directions determine a unique square through their endpoints.Source: §3.1 · p. 8
  • A cubical complex is λ-expanding when each direction-and-type bipartite graph has second eigenvalue at most λ.Source: §3.1 · p. 8

3.2 Projective Reed-Solomon Codes

  • PRS_d evaluates homogeneous degree-d polynomials on P1(F_s), giving parameters [s + 1, d + 1, s + 1 − d]_E.Source: §3.2 · p. 9
  • The dual of PRS_d is PRS_{s−1−d}, established by orthogonality of evaluations and complementary code dimensions.Source: §3.2 · p. 9
  • Invertible 2 × 2 matrices induce weighted Möbius coordinate actions that preserve PRS_d by bijectively transforming its homogeneous polynomials.Source: §3.2 · p. 9

4 The Cubical Complex and Local Codes

This section equips the non-Abelian cubical complex with Reed–Solomon local codes whose symmetries make vertex local views tensor codewords, developing the construction in two dimensions and then extending it to four. In the higher-dimensional generalization, it describes how rescaling and reindexing express the constraints on 3-faces containing a given face as constraints on direction-i lines.

4.1 The Complex and Its Symmetries

  • The complex’s symmetry properties make vertex local views consistent, yielding a well-defined global code.The complex is constructed as X = Γ\T, with vertices (G/H) × {0, 1}^4.Source: §4.1 · p. 10

4.2 Setting up Local Codes on the 2d Complex

  • Because endpoint labels differ by β_e, the construction uses Frobenius coordinate permutations and compatible rescaling weights; degree divisibility is crucial, and these operations preserve product expansion.Source: §4.2 · p. 11

4.3 Local Views of Vertices in the 2d Construction

  • In the 2d construction, the checks on every incident edge hold exactly when the vertex’s square assignment comes from a tensor codeword.Applying the argument in both directions yields the row and column constraints defining C1 ⊗ C2.Source: §4.3 · pp. 13–14

4.4 Generalization to Higher Dimensions

  • In four dimensions, satisfying the 3-face checks around any face is equivalent to the local assignment arising from a tensor product of codes in the missing directions.The 3-face checks use rescaled, optionally permuted base codes.Source: §4.4 · pp. 16–17
  • At the designated vertex w of a 3-face τ missing direction i, dividing the constraint coordinatewise by νw(Q) gives P tiCi.Source: §4.4 · p. 17
  • Along each edge of τ other than direction i, the rescaled codeword descriptions at the endpoints are equivalent, so the description propagates from w to every vertex of τ.The proof uses Q-independent ratios for the other direction factors and an invertible linear substitution with nonzero constant factors in direction i.Source: §4.4 · p. 17
  • For each f and v, rescaling and reindexing the symbols of the 4-faces containing f makes their 3-face constraints exactly the Ci constraints on every direction-i line for each i not in S.Source: §4.4 · p. 17

5 Rate, Distance, and Soundness Analysis

This section defines the CSS code on the cubical complex and analyzes its rate, distance, and soundness using local Reed–Solomon codes. Assuming product expansion, the analysis yields an infinite family with linear rate and distance, constant soundness, and bounded check weights.

5.1 Defining the Quantum Code

  • The code is defined from a cochain complex on the cubical complex and local codes; its check matrices define a CSS code encoding K qudits into N qudits over E.The physical qudits occupy coordinates of C2, and bounded si yield bounded row and column weights of HZ and HX.Source: §5.1 · pp. 17–18

5.2 Rate

  • For the rate bound, local-code rates R1, R2 below µ and R3, R4 above 1−µ are the stated sufficient conditions; the main-theorem choice µ = 1/16 gives K = Ω(N).The proof adapts the dimension-count argument of [DLV24] to local views that are tensor codes.Source: §5.2 · p. 18, §5.5 · p. 22

5.3 Distance and Soundness

  • If the local-code tuples and their duals are ρ-product-expanding and X has spectral expansion λ, the resulting CSS code has D = Ω(N) and soundness κ > 0.The lemma also assumes bounded degree ratio and bounded si; λ must be sufficiently small in terms of ρ and β.Source: §5.3 · p. 19

5.4 Product Expansion of Reed-Solomon Codes

  • Conjecture 5.6 posits product expansion for Reed–Solomon codes over binary extension fields; Lemma 5.7 transfers it to projective Reed–Solomon code tuples and their duals under its degree conditions.The transfer uses code equivalence by coordinate permutations and nonzero coordinate scalings, which preserves Hamming weights.Source: §5.4 · p. 20

5.5 Proof of Main Theorem

  • Assuming Conjecture 5.6, the construction gives an infinite family of quantum CSS codes with K = Ω(N), D = Ω(N), constant soundness, and constant check weights.Expanding the cochain maps over F2 gives qubit codes; because E is fixed, the resulting parameter changes remain constant-factor bounded.Source: §5.5 · pp. 21–22
  • With η = 1/17 and β = 256, Lemma 5.7 gives a product-expansion constant ρ > 0 independent of L, and sufficiently large L puts every 2√sᵢ/(sᵢ + 1) below Lemma 5.4’s threshold.With µ = 1/16, Lemma 5.2 gives K = Ω(N).Source: §5.5 · p. 22

6 The Non-Abelian Cubical Complex

The construction uses a non-Abelian cubical complex formed from a quotient of a product of four trees. Its basis-change structure supports compatible edge labels and the spectral expansion needed for the code analysis.

6 The Non-Abelian Cubical Complex

  • The complex is built from a quotient of a Cartesian product of four Bruhat–Tits trees, with vertices represented by cosets and type bits.Rungtanapirom, Stix, and Vdovina [RSV19] supply the underlying complex construction.Source: §6 · p. 22, §6.1 · p. 25

6.1 Proof of Lemma 4.1

  • Projective-line labels identify incident edges, while comparison matrices track how edge labels change between vertex bases and remain consistent around squares.A common change-of-basis matrix works for the entire book of squares around an edge because vertex bases are fixed independently of the square.Source: §6 · p. 23, §6.1 · pp. 24, 26, 27

6.2 Expansion of the cubical complex

  • For the characteristic-two expansion argument, the authors construct a graph cover and transfer the spectral bound for tree quotients to each base graph Bi using Morgenstern’s theorem [Mor94].The expansion proof imposes a parity restriction on the quotient subgroup to meet the theorem’s representative condition.Source: §6.2 · pp. 27–28
Loading 2609.26735v1…