ИСТИНА

Classical LDPC codes are essential components in the current data storage and transmission systems. Their quantum counterparts (qLDPC codes) promise significant savings of resources in future fault-tolerant protocols for quantum computations. Starting from the foundational work of Robert Gallager in the early 1960s, it has been known that there are asymptotically good families of classical LDPC codes, i.e., codes of non-vanishing rate and relative minimal distance. Moreover, 35 years later, Sipser and Spielman introduced an explicit construction of such codes called expander codes and showed that they can be decoded in linear time. At the same time, the existence of asymptotically good quantum LDPC codes (qLDPC conjecture) has been an open question for more than two decades. For example, 2D topological codes such as surface codes have the distance growing only as the square root of the code length. In fact, qLDPC codes that significantly surpass this square root barrier were first shown to exist only in 2020 in the breakthrough work of Hastings-Haah-O'Donnell, which gave a great impetus to the field. In the current work, we combine classical expander codes into a chain complex using a (homological) tensor product over a group algebra, an idea proposed in arXiv:2012.04068 and in a more general form in arXiv:2012.09271, to give a construction of asymptotically good qLDPC codes, which proves the qLDPC conjecture. Quite surprisingly, by looking at the second homology groups of the obtained chain complexes we also show, as a byproduct of our proof, the existence of classical locally testable codes of constant rate, relative distance, and locality. This answers another important open problem called the c^3-conjecture, which was also independently claimed by Dinur et al. in arXiv:2111.04808. In this talk, I am going to give an overview of the construction and show some essential ideas used in the proof such as the notion of local minimality, borrowed from the theory of high-dimensional expanders. The talk is based on the joint work with Gleb Kalachev available at arXiv:2111.03654.