Motivated by recent advances in locally testable codes and quantum LDPCs based on robust testability of tensor product codes, we explore the local testability of tensor products of (an abstraction of) algebraic geometry codes. Such codes are parameterized by, in addition to standard parameters such as block length
n and dimension
k, their genus
g. We show that the tensor product of two algebraic geometry codes is robustly locally testable provided
n=Ω((k+g)2). Apart from Reed-Solomon codes, this seems to be the first explicit family of two-wise tensor codes of high dual distance that is robustly locally testable by the natural test that measures the expected distance of a random row/column from the underlying code.
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.
For every fixed integers
r≥4 and
2≤k≤r−2, we construct
r-dimensional cubical sheaf complexes whose degree-
k CSS codes have positive constant rate, linear distance, and constant soundness, with bounded row and column weights. Taking
r=4 and
k=2 gives a family of asymptotically good binary qLTCs.
At the core of our construction is a uniform product-expansion theorem for explicit Reed-Solomon codes on norm-one evaluation sets. The key point is that the expansion constant stays bounded away from zero as the local code lengths grow. We place these codes on arithmetic cubical complexes, obtaining constant local expansion for both the resulting sheaf and its dual. Together with the local-to-global framework of Dinur, Lin, and Vidick (FOCS 2024) and sheaf duality, this gives linear distance and constant soundness, while an asymmetric choice of local code dimensions gives positive rate. The resulting codes are explicit and polynomial-time computable.
A collection of classical codes
C1,…,Cm has product expansion if every low-weight word in the sum of their extensions to the product space can be written as a sum of words supported on few lines, each line being a codeword of the corresponding
Ci. For
m=2 product expansion is equivalent to robust testability of the tensor code, while for
m≥3 it is strictly stronger; it is the hypothesis on the local codes behind recent constructions of good quantum LDPC codes, good quantum locally testable codes, and quantum codes with transversal non-Clifford gates. No explicit family over a fixed field was previously known to achieve constant rate, linear distance for both the code and its dual, and 3-fold product expansion at growing length. We prove that for the one-point evaluation codes
Ci of length
Ni=728⋅27i−1 and pole order
⌊Ni/5⌋ on the Garcia--Stichtenoth tower over
F729, the triple
(Ci,Ci,Ci) has product expansion with a constant independent of
i. The dual codes
Ci⊥ then form an explicit fixed-field family of rate tending to
109/130 and relative distance at least
8/65. The proof is geometric: we view the words of the sum code as arrays on the product of three copies of the
i-th curve of the tower, where the parity checks are sections of a line bundle. An exact generation theorem describes the sum-code words supported on the grid footprint of a suitable divisor. A support-localisation argument then shows that every low-weight array lies on such a divisor, after deleting a small number of coordinates. We also give a sufficient criterion for three-fold product expansion in terms of degree and genus ratios, yielding explicit families over every non-prime finite field of order at least
512. The principal conclusions have been formally verified in Lean 4.
Designing quantum codes with both transversal non-Clifford gates and good error-correcting parameters is an important goal in fault-tolerant quantum computation. Here, we construct an explicit family of binary CSS codes with constant rate and linear distance that admit fully addressable transversal
T gates. Specifically, any prescribed tensor product of logical powers of
T is implemented by a tensor product of physical powers of
T, without any subsequent correction. Our construction combines algebraic-geometry codes with suitable binary embedding to obtain generalized divisibility of binary codes. This divisibility then enables fully addressable transversal
T gates. Furthermore, we formulate the minimum binary embedding length problem as a minimum-weight problem over an affine space and numerically improve the constants in the asymptotic rate and relative-distance bounds.
Beginning with the work of Dinur, Lin, and Vidick (FOCS, 2024), tensor codes with constant product expansion have been foundational to recent advances in quantum locally testable codes (qLTCs) based on cubical complexes. Informally, product expansion says that any low-weight parity check of the tensor code can be written as the sum of few parity checks of each component code in each dimension. Recent work of Kalachev and Panteleev (FOCS, 2025) showed that tensors of random linear codes have constant product expansion. In this work we initiate the study of random linear codes with prescribed automorphism groups. For every sufficiently large prime
k, we construct pairs of rate
1/2 MDS codes of length
2k, over finite fields whose size depends on
k, that have constant two-sided product expansion and are invariant under the simultaneous cyclic shift of two cycles of length
k. This shift is the local action in the cube complexes of Rungtanapirom, Stix, and Vdovina (Internat. J. Algebra Comput., 2019). Along the way we give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of [KP25], does not rely on explicit constructions of asymptotically optimal locally testable codes. Our proof relies on several new techniques that we view as interesting in their own right. Instead of working directly over finite fields, we work over the reals and use random Rademacher matrices for the generator matrices of the component codes. From here, we show how to relate product expansion to the operator norm of sparse restrictions of carefully chosen Gram matrices, which we bound using tools from random matrix theory. More generally, we propose a method for studying properties of random linear codes by lifting to random codes over
R and
C, which we anticipate will be applicable more broadly to existential problems in coding theory.