Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Journal on Selected Areas in Information Theory

Asymptotically Good Generalized Quantum Tanner Codes

Olai Å. Mostad, Eirik Rosnes, Hsuan-Yin Lin

Published Jan 1, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1109/jsait.2025.3594310

Related papers

Generalizing Quantum Tanner Codes

Olai Å. Mostad, Eirik Rosnes, Hsuan-Yin Lin

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.

arXiv:2405.07980•Jul 7, 2024•3 citations

Small quantum Tanner codes from left--right Cayley complexes

Anthony Leverrier, Wouter Rozendaal, Gilles Zémor

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,\leq 22]]$ and $[[576,28,\leq 24]]$ for generators of weight 9.

quant-pharXiv:2512.20532•Dec 24, 2025•0 citations

Improved Construction of Generalized Quantum Tanner Codes

Olai Å. Mostad, Eirik Rosnes, Hsuan-Yin Lin

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.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•1 citation

Quantum Tanner codes

Anthony Leverrier, Gilles Zémor

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.

arXiv:2202.13641•Annual Symposium on Foundations of Computer Science•Oct 1, 2022•137 citations

Quantum Tanner Codes at Moderate Blocklength

Feroz Ahmed Mian, Vaishnavi L. Addala, Arman Meraj +2 more

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 $\mathcal{G}$. Through an extensive search over non-abelian groups from GAP's SmallGrp library, we investigate the moderate-blocklength regime ($n \in [500,1000]$) and identify several new code instances with distance upper bounds exceeding $20$. These include $[[480,8,(\leq 21,\leq 21)]]$, $[[504,4,(\leq 36,\leq 27)]]$, $[[672,4,(\leq 48,\leq 28)]]$, $[[720,6,(\leq 30,\leq 30)]]$, and $[[864,8,(\leq 39,\leq 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.

quant-pharXiv:2608.12509•Aug 14, 2026•0 citations

Decoding Quantum Tanner Codes

Anthony Leverrier, Gilles Zémor

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.

arXiv:2208.05537•IEEE Transactions on Information Theory•Apr 17, 2023•29 citations
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.
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.
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]][[144,12,11]][[144,12,11]], [[432,20,≤22]][[432,20,\leq 22]][[432,20,≤22]] and [[576,28,≤24]][[576,28,\leq 24]][[576,28,≤24]] for generators of weight 9.
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.
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 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\mathcal{G}G. Through an extensive search over non-abelian groups from GAP's SmallGrp library, we investigate the moderate-blocklength regime (n∈[500,1000]n \in [500,1000]n∈[500,1000]) and identify several new code instances with distance upper bounds exceeding 202020. These include [[480,8,(≤21,≤21)]][[480,8,(\leq 21,\leq 21)]][[480,8,(≤21,≤21)]], [[504,4,(≤36,≤27)]][[504,4,(\leq 36,\leq 27)]][[504,4,(≤36,≤27)]], [[672,4,(≤48,≤28)]][[672,4,(\leq 48,\leq 28)]][[672,4,(≤48,≤28)]], [[720,6,(≤30,≤30)]][[720,6,(\leq 30,\leq 30)]][[720,6,(≤30,≤30)]], and [[864,8,(≤39,≤31)]][[864,8,(\leq 39,\leq 31)]][[864,8,(≤39,≤31)]], with these bounds obtained using up to 350350350 million trials of sQetch, a randomized distance estimator. The code instances presented have check weights ranging from 999 to 202020. Using the Tesseract decoder, we estimate pseudo-thresholds of 3.6%3.6\%3.6%-4.6%4.6\%4.6% under phenomenological noise and 0.14%0.14\%0.14%-0.27%0.27\%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 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.