Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.28028

Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs

Yeyuan Chen, Miryam Mi-Ying Huang, Yinchen Liu, Er-Cheng Tang

cs.ITcs.CCquant-phSubmitted Sep 23, 2026• Announced Sep 24, 2026• 4 citations
arXivHTMLPDF

Abstract

For every fixed integers $r \ge 4$ and $2 \le k \le 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.

AI Summary

The paper addresses whether binary quantum locally testable codes can simultaneously have constant rate, linear distance, constant soundness, and bounded check weights and qubit degrees. It constructs explicit, polynomial-time computable families claiming all these properties: $[[N,K,D,\rho]]$ with $K=\Omega(N)$, $D=\Omega(N)$, and $\rho=\Omega(1)$. More generally, the construction works on $r$-dimensional cubical sheaf complexes for every fixed $r\ge4$ and $2\le k\le r-2$; $r=4,k=2$ gives the binary application. The stated rate lower bound is $K/N\ge[2\binom{r}{k}2^{r-k}]^{-1}$, hence $1/48$ in that case. The main coding ingredient is product expansion for Reed–Solomon codes evaluated on norm-one sets of lengths $q_i+1$, where $q_i=2^{2(A+i)}$. For relative redundancies at least $\beta$, every nonempty subtuple has expansion at least $c_r\beta^r$, independently of $A$. The proof enlarges supports to polynomial hulls and establishes inner generation using Frobenius-based derivative isolation and cylinder gluing. Frobenius-twisted local codes descend to arithmetic quotients of products of trees, whose parallel-face graphs satisfy $\lambda\le\max_i2\sqrt{q_i}/(q_i+1)$. DLV local-to-global expansion and sheaf duality supply distance and soundness; asymmetric local dimensions supply rate. The guarantees are asymptotic, with constants depending on fixed local parameters. Logical gates are not studied. The norm-one expansion theorem does not resolve the distinct Bafna–Vyas conjecture, and the paper notes concurrent constructions of good qLTCs.

Some signs of AI-generated textAI use disclosed
the main construction and technical ideas in the current paper were generated with GPT-6 Astra on September 7th

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Product Expansion of Random Codes via Analytic Techniques

Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner

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 $\mathbb{R}$ and $\mathbb{C}$, which we anticipate will be applicable more broadly to existential problems in coding theory.

arXiv:2610.02512•Oct 1, 2026•2 citations

Good Quantum Locally Testable Codes from Product Expansion

Mitali Bafna, Anqi Li, Quynh T. Nguyen

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.

quant-pharXiv:2609.26735•Sep 23, 2026•5 citations

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

Irit Dinur, Ting-Chun Lin, Thomas Vidick

We introduce a high-dimensional cubical complex, for any dimension$t \in \mathbb{N}$, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case$t=2$), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes$h_{1}, \ldots,h_{t}$as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For$t=4$our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.

arXiv:2402.07476•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•34 citations

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

Itay Cohen, Itai Leigh, Assaf Reiner +2 more

Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.

quant-pharXiv:2610.00525•Oct 2, 2026•1 citation

Asymptotically Good Quantum Locally Testable Codes

William Gay, Fernando Granha Jeronimo

We construct explicit families of asymptotically good quantum locally testable codes over qubits. More precseily, we construct explicit quantum LDPC CSS codes over qubits having constant rate, constant relative distance and constant weight local testers with constant soundness.

quant-pharXiv:2609.20780•Sep 18, 2026•9 citations

Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes

Sumegha Garg, Akash Kumar Sengupta

We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that constant rate AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman (1994), which proved robust local testability of Reed-Solomon codes. We establish an algebraic-geometric framework that enables us to geometrically interpret codewords in tensor products of AG codes. Thereby, we use tools from intersection theory of algebraic surfaces to prove a divisibility criterion for AG codes, that generalizes the bivariate divisibility result of Polishchuk-Spielman.Over the years, robust local testability of tensor products has played a key role in the development of classical locally testable codes (LTCs) as well as quantum Low Density Parity Check (qLDPC) codes and quantum Locally Testable Codes (qLTCs). To the best of our knowledge, after Reed-Solomon codes, our result provides the first explicit family of robustly locally testable codes with constant rate and linear dual-distance. Moreover, our result, when combined with Golowich-Guruswami (2024), yields new explicit families of good quantum CSS codes of length N which are locally testable with locality $O(\sqrt N )$ and constant soundness.

Annual Symposium on Foundations of Computer Science•Dec 14, 2025•0 citations
For every fixed integers r≥4r \ge 4r≥4 and 2≤k≤r−22 \le k \le r-22≤k≤r−2, we construct rrr-dimensional cubical sheaf complexes whose degree-kkk CSS codes have positive constant rate, linear distance, and constant soundness, with bounded row and column weights. Taking r=4r=4r=4 and k=2k=2k=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.
The paper addresses whether binary quantum locally testable codes can simultaneously have constant rate, linear distance, constant soundness, and bounded check weights and qubit degrees. It constructs explicit, polynomial-time computable families claiming all these properties: [[N,K,D,ρ]][[N,K,D,\rho]][[N,K,D,ρ]] with K=Ω(N)K=\Omega(N)K=Ω(N), D=Ω(N)D=\Omega(N)D=Ω(N), and ρ=Ω(1)\rho=\Omega(1)ρ=Ω(1). More generally, the construction works on rrr-dimensional cubical sheaf complexes for every fixed r≥4r\ge4r≥4 and 2≤k≤r−22\le k\le r-22≤k≤r−2; r=4,k=2r=4,k=2r=4,k=2 gives the binary application. The stated rate lower bound is K/N≥[2(rk)2r−k]−1K/N\ge[2\binom{r}{k}2^{r-k}]^{-1}K/N≥[2(kr​)2r−k]−1, hence 1/481/481/48 in that case.
The main coding ingredient is product expansion for Reed–Solomon codes evaluated on norm-one sets of lengths qi+1q_i+1qi​+1, where qi=22(A+i)q_i=2^{2(A+i)}qi​=22(A+i). For relative redundancies at least β\betaβ, every nonempty subtuple has expansion at least crβrc_r\beta^rcr​βr, independently of AAA. The proof enlarges supports to polynomial hulls and establishes inner generation using Frobenius-based derivative isolation and cylinder gluing. Frobenius-twisted local codes descend to arithmetic quotients of products of trees, whose parallel-face graphs satisfy λ≤max⁡i2qi/(qi+1)\lambda\le\max_i2\sqrt{q_i}/(q_i+1)λ≤maxi​2qi​​/(qi​+1). DLV local-to-global expansion and sheaf duality supply distance and soundness; asymmetric local dimensions supply rate.
The guarantees are asymptotic, with constants depending on fixed local parameters. Logical gates are not studied. The norm-one expansion theorem does not resolve the distinct Bafna–Vyas conjecture, and the paper notes concurrent constructions of good qLTCs.
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 kkk, we construct pairs of rate 1/21/21/2 MDS codes of length 2k2k2k, over finite fields whose size depends on kkk, that have constant two-sided product expansion and are invariant under the simultaneous cyclic shift of two cycles of length kkk. 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\mathbb{R}R and C\mathbb{C}C, which we anticipate will be applicable more broadly to existential problems in coding theory.
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.
We introduce a high-dimensional cubical complex, for any dimensiont∈Nt \in \mathbb{N}t∈N, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (caset=2t=2t=2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codesh1,…,hth_{1}, \ldots,h_{t}h1​,…,ht​as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. Fort=4t=4t=4our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.
Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.
We study the robust local testability of tensor products of two Algebraic-Geometry (AG) codes. In particular, we prove that constant rate AG codes are robust locally testable. This significantly generalizes the seminal result of Polishchuk-Spielman (1994), which proved robust local testability of Reed-Solomon codes. We establish an algebraic-geometric framework that enables us to geometrically interpret codewords in tensor products of AG codes. Thereby, we use tools from intersection theory of algebraic surfaces to prove a divisibility criterion for AG codes, that generalizes the bivariate divisibility result of Polishchuk-Spielman.Over the years, robust local testability of tensor products has played a key role in the development of classical locally testable codes (LTCs) as well as quantum Low Density Parity Check (qLDPC) codes and quantum Locally Testable Codes (qLTCs). To the best of our knowledge, after Reed-Solomon codes, our result provides the first explicit family of robustly locally testable codes with constant rate and linear dual-distance. Moreover, our result, when combined with Golowich-Guruswami (2024), yields new explicit families of good quantum CSS codes of length N which are locally testable with locality O(N)O(\sqrt N )O(N​) and constant soundness.