We propose a generalization of the recently proposed quantum Tanner codes by Leverrier and Zemor. These codes can be constructed equivalently from groups, Cayley graphs, or square complexes constructed from groups. In a recent work, we enlarged this to group actions on finite sets, Schreier graphs, and a family of square complexes. We extend the class of quantum Tanner codes further by replacing the tensor product code in the construction with a Tanner code on any bipartite graph. A stricter property on the other underlying graphs is required, and we show that a common variation of the construction can always be taken to satisfy this condition. This results in improved codes compared to the ones constructed based on Schreier graphs.
We propose a generalization of the recently proposed quantum Tanner codes by Leverrier and Zemor. These codes can be constructed equivalently from groups, Cayley graphs, or square complexes constructed from groups. In a recent work, we enlarged this to group actions on finite sets, Schreier graphs, and a family of square complexes. We extend the class of quantum Tanner codes further by replacing the tensor product code in the construction with a Tanner code on any bipartite graph. A stricter property on the other underlying graphs is required, and we show that a common variation of the construction can always be taken to satisfy this condition. This results in improved codes compared to the ones constructed based on Schreier graphs.
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 group actions on finite sets, Schreier graphs, and a family of square complexes, which is the largest possible in a certain sense. Furthermore, we discuss how the proposed generalization opens up the possibility of finding other families of asymptotically good quantum codes.
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.
We present explicit constructions of quantum Tanner (QT) codes with good rate and distance, obtained through two complementary approaches: the left-right Cayley complex (LRCC) description and the "lifting" perspective, in which a seed Calderbank-Shor-Steane (CSS) code is lifted by commuting left-right regular actions of a finite group G. Through an extensive search over non-abelian groups from GAP's SmallGrp library, we investigate the moderate-blocklength regime (n∈[500,1000]) and identify several new code instances with distance upper bounds exceeding 20. These include [[480,8,(≤21,≤21)]], [[504,4,(≤36,≤27)]], [[672,4,(≤48,≤28)]], [[720,6,(≤30,≤30)]], and [[864,8,(≤39,≤31)]], with these bounds obtained using up to 350 million trials of sQetch, a randomized distance estimator. The code instances presented have check weights ranging from 9 to 20. Using the Tesseract decoder, we estimate pseudo-thresholds of 3.6%-4.6% under phenomenological noise and 0.14%-0.27% under circuit-level noise, comparable to prior results at shorter code lengths. We also provide QuantumExpanders.jl, an open-source Julia library for constructing QT codes and explicit constructions of Ramanujan graphs.
We introduce new families of quantum Tanner codes, a class of quantum codes that first appeared in the work of Leverrier and Zémor (FOCS 2022). These codes are built from two classical Tanner codes, for which the underlying graphs are extracted from coverings of 2D geometrical complexes, and the local linear codes are tensor-products of cyclic or double-circulant linear codes. The advantage of code lifting is that, for any lift of odd index t of an [[n,k,d]]-code, we can adapt the study of the transfer homomorphism arising in cellular homology to describe symmetries of its logical operators and to establish that its dimension is lower bounded by k, and its distance is upper bounded by t⋅d. Moreover, when the dimension of the lifted code is equal to k, its distance is lower bounded by d. These parameter bounds also apply to the previous methods of code lifting of Guémard (IEEE Trans. Inf. Theory, 2025). Finally, We present several explicit families, and identify instances of moderate length quantum codes which are degenerate, have low check weight, and whose distance surpasses the square root of the code length. Among them, we report the existence of a [[96,2,12]]-code whose distance growth saturates our bound, and for which half of the checks are of weight 8 and the other half of weight 4.
Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser and Spielman, which are asymptotically good classical LDPC codes. In this work we apply this prescription to the left-right Cayley complex that lies at the heart of the recent construction of a c3locally testable code by Dinur et at. Specifically, we view this complex as two graphs that share the same set of edges. By defining a Tanner code on each of those graphs we obtain two classical codes that together define a quantum code. This construction can be seen as a simplified variant of the Panteleev and Kalachev asymptotically good quantum LDPC code, with improved estimates for its minimum distance. This quantum code is closely related to the Dinur et at. code in more than one sense: indeed, we prove a theorem that simultaneously gives a linearly growing minimum distance for the quantum code and recovers the local testability of the Dinur et at. code.
We study the decoding problem for quantum Tanner codes and propose to exploit the underlying local code structure by grouping check nodes into more powerful generalized check nodes for enhanced iterative belief propagation (BP) decoding by decoding the generalized checks using a maximum a posteriori (MAP) decoder as part of the check node processing of each decoding iteration. We mainly study the finite-length setting and show that the proposed enhanced generalized BP decoder for quantum Tanner codes significantly outperforms the standard quaternary BP decoder with memory effects, as well as the recently proposed Relay-BP decoder, even outperforming generalized bicycle (GB) codes with comparable parameters in some cases. For other classes of quantum low-density parity-check (qLDPC) codes, we propose a greedy algorithm to combine checks for generalized BP decoding. However, for GB codes, bivariate bicycle codes, hypergraph product codes, and lifted-product codes, there seems to be limited gain by combining simple checks into more powerful ones. To back up our findings, we also provide a theoretical cycle analysis for the considered qLDPC codes. This leads us to a construction criterion for quantum Tanner codes that produces codes particularly well-suited for BP decoding.