Name
Title | ||
|---|---|---|
New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√n logk n) distance |
Abstract | ||
|---|---|---|
ABSTRACTIn this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed Collective-cosystolic expansion. We show that tensoring two cosystolic expanders yields a new cosystolic expander, assuming one of the complexes in the product, is not only cosystolic expander, but rather a collective cosystolic expander. We then show that the well known bounded degree cosystolic expanders, the Ramanujan complexes are, in fact, collective cosystolic expanders. This enables us to construct new bounded degree cosystolic expanders, by tensoring of Ramanujan complexes. Using our new constructed bounded degree cosystolic expanders we construct explicit quantum LDPC codes of distance √n logk n for any k, improving a recent result of Evra et. al. [FOCS, 2020], and setting a new record for distance of explicit quantum LDPC codes. The work of Evra et. al. [FOCS, 2020] took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes, and using their newly derived property, the collective cosystolic expansion. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3406325.3451029 | ACM Symposium on Theory of Computing |
DocType | Citations | PageRank |
Conference | 1 | 0.35 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tali Kaufman | 1 | 499 | 38.33 |
| Ran J. Tessler | 2 | 1 | 0.35 |