We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.
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.
In this work, we present a generalization of the recently proposed quantum Tanner codes by Leverrier and Zémor, which contains a construction of asymptotically good quantum low-density parity-check codes. Quantum Tanner codes have so far been constructed equivalently from groups, Cayley graphs, or square complexes constructed from groups. We show how to enlarge this to graphs with labeled local views and a family of square complexes, which is the largest possible in a certain sense. We show that the proposed generalization contains a family of asymptotically good quantum codes that are based on non-Cayley Schreier graphs, i.e., a new family of (generalized) quantum Tanner codes is provided. Moreover, we evaluate the performance of the generalized codes and compare with those based on Cayley graphs both in terms of minimum distance and logical error rate on the depolarizing channel, demonstrating that the proposed generalized codes based on Schreier graphs outperform those based on Cayley graphs.
Quantum Tanner codes are a class of quantum low-density parity-check codes that provably display a linear minimum distance and a constant encoding rate in the asymptotic limit. When built from left--right Cayley complexes, they can be described through a lifting procedure and a base code, which we characterize. We also compute the dimension of quantum Tanner codes when the right degree of the complex is 2. Finally, we perform an extensive search over small groups and identify instances of quantum Tanner codes with parameters
[[144,12,11]],
[[432,20,≤22]] and
[[576,28,≤24]] for generators of weight 9.
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,…,htas 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=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.
Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph
G together with a linear inner code
C0. Expander codes are Tanner codes whose defining bipartite graph
G has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that
δ and
d0 must satisfy, so that \textit{every} bipartite expander
G with vertex expansion ratio
δ and \textit{every} linear inner code
C0 with minimum distance
d0 together define an expander code that corrects
Ω(n) errors in
O(n) time? For
C0 being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that
δ>3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to
δ>2/3−Ω(1) and he also showed that
δ>1/2 is necessary. For general linear code
C0, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that
d0=Ω(cδ−2) is sufficient, where
c is the left-degree of
G. In this paper, we give a near-optimal solution to the above question for general
C0 by showing that
δd0>3 is sufficient and
δd0>1 is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.