Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes
We introduce a high-dimensional cubical complex, for any dimension 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 (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,…,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.
2024-10-27
379
385
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
FOCS 2024 | Chicago, United States | 2024-10-27 - 2024-10-30 | |
| Funder | Grant Number |
ERC | 772839 |