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

arXiv:2202.13641 · Annual Symposium on Foundations of Computer Science

Quantum Tanner codes

Anthony Leverrier, Gilles Zémor

Published Oct 1, 2022• 276 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/focs54457.2022.00117

Related papers

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•52 citations

Good Quantum Locally Testable Codes from Lossless Cubical Complexes

Itay Cohen, Itai Leigh, Assaf Reiner +2 more

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.

quant-pharXiv:2610.00525•Oct 2, 2026•1 citation

Asymptotically Good Generalized 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 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.

IEEE Journal on Selected Areas in Information Theory•Jan 1, 2025•1 citation

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•11 citations

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

Irit Dinur, Ting-Chun Lin, Thomas Vidick

We introduce a high-dimensional cubical complex, for any dimension$t \in \mathbb{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$h_{1}, \ldots,h_{t}$as 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=4$our 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.

arXiv:2402.07476•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•34 citations

When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

Kuan Cheng, Minghui Ouyang, Chong Shangguan +1 more

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 $C_0$. 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 $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ 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 $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(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 $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>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.

arXiv:2312.16087•Leibniz international proceedings in informatics•Dec 26, 2023•0 citations
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 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]][[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 introduce a high-dimensional cubical complex, for any dimensiont∈Nt \in \mathbb{N}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 (caset=2t=2t=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 codesh1,…,hth_{1}, \ldots,h_{t}h1​,…,ht​as 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. Fort=4t=4t=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 GGG together with a linear inner code C0C_0C0​. Expander codes are Tanner codes whose defining bipartite graph GGG 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 d0d_0d0​ must satisfy, so that \textit{every} bipartite expander GGG with vertex expansion ratio δδδ and \textit{every} linear inner code C0C_0C0​ with minimum distance d0d_0d0​ together define an expander code that corrects Ω(n)Ω(n)Ω(n) errors in O(n)O(n)O(n) time? For C0C_0C0​ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that δ>3/4δ>3/4δ>3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to δ>2/3−Ω(1)δ>2/3-Ω(1)δ>2/3−Ω(1) and he also showed that δ>1/2δ>1/2δ>1/2 is necessary. For general linear code C0C_0C0​, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d0=Ω(cδ−2)d_0=Ω(cδ^{-2})d0​=Ω(cδ−2) is sufficient, where ccc is the left-degree of GGG. In this paper, we give a near-optimal solution to the above question for general C0C_0C0​ by showing that δd0>3δd_0>3δd0​>3 is sufficient and δd0>1δd_0>1δ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.