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

Annual Symposium on Foundations of Computer Science

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

Irit Dinur, Ting-Chun Lin, Thomas Vidick

Published Oct 27, 2024• 4 citations
Publisher

Abstract

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.

DOI
10.1109/focs61266.2024.00031

Related papers

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•0 citations

Expansion of higher-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>0, 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•Feb 12, 2024•1 citation

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•0 citations

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

Yeyuan Chen, Miryam Mi-Ying Huang, Yinchen Liu +1 more

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.

cs.ITCross-listedarXiv:2609.28028•Sep 24, 2026•0 citations

Quantum LDPC Codes of Almost Linear Distance via Homological Products

Louis Golowich, Venkatesan Guruswami

The first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry. We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes). Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N).

arXiv:2411.03646•Leibniz international proceedings in informatics•Nov 6, 2024•1 citation

Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products

Golowich, Louis, Venkatesan Guruswami

The first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry. We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes). Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N).

•Jan 1, 2025•0 citations
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 introduce a high-dimensional cubical complex, for any dimension t>0, 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 h1,…,hth_1,\ldots,h_th1​,…,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. 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.
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≥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 first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry. We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes). Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N).
The first linear-distance quantum LDPC codes were recently constructed by a line of breakthrough works (culminating in the result of Panteleev & Kalachev, 2021). All such constructions, even when allowing for almost-linear distance, are based on an operation called a balanced (or lifted) product, which is used in a one-shot manner to combine a pair of large classical codes possessing a group symmetry. We present a new construction of almost-linear distance quantum LDPC codes that is iterative in nature. Our construction is based on a more basic and widely used product, namely the homological product (i.e. the tensor product of chain complexes). Specifically, for every ε > 0, we obtain a family of [[N,N^{1-ε},N^{1-ε}]] (subsystem) quantum LDPC codes via repeated homological products of a constant-sized quantum locally testable code. Our key idea is to remove certain low-weight codewords using subsystem codes (while still maintaining constant stabilizer weight), in order to circumvent a particular obstruction that limited the distance of many prior homological product code constructions to at most Õ(√N).