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:2004.07935 · SIAM Journal on Computing

Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders

Shai Evra, Tali Kaufman, Gilles Zémor

Published Jun 14, 2022• 56 citations
arXivHTMLPDF

Abstract

Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large $X$-distance but a much smaller $Z$-distance. However, together with a classical expander LDPC code and a tensoring method that generalizes a construction of Hastings and also the Tillich–Zémor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance $n^{1/2}\log^{1/2}n$. We then exploit the expansion properties of the complex to devise the first polynomial-time algorithm that decodes above the square root barrier for quantum LDPC codes. Using a 3-dimensional Ramanujan complex, we also obtain an overall quantum code of minimum distance $n^{1/2}\log n$, which sets a new record for quantum LDPC codes.

DOI
10.1137/20m1383689

Related papers

Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders

Shai Evra, Tali Kaufman, Gilles Zémor

Constructing quantum LDPC codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large X-distance but a much smaller Z-distance. However, together with a classical expander LDPC code and a tensoring method that generalises a construction of Hastings and also the Tillich-Zemor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 3-dimensional Ramanujan complex, we show that its 2-systole behaves like a square of the log of the complex size, which results in an overall quantum code of minimum distance n1/2logn, and sets a new record for quantum LDPC codes. When we use a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance n1/2log1/2n. We then exploit the expansion properties of the complex to devise the first polynomial time algorithm that decodes above the square root barrier for quantum LDPC codes.

Annual Symposium on Foundations of Computer Science•Nov 1, 2020•44 citations

New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with $Ω(\sqrt{n}\log^kn)$ Distance

Tali Kaufman, Ran J. Tessler

In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed {\em Collective-cosystolic expansion}. We show that tensoring two cosystolic expanders yields a new cosystolic expander, assuming one of the complexes in the product, is not only cosystolic expander, but rather a collective cosystolic expander. We then show that the well known bounded degree cosystolic expanders, the Ramanujan complexes are, in fact, collective cosystolic expanders. This enables us to construct new bounded degree cosystolic expanders, by tensoring of Ramanujan complexes. Using our new constructed bounded degree cosystolic expanders we construct {\em explicit} quantum LDPC codes of distance $\sqrt{n} \log^k n$ for any $k$, improving a recent result of Evra et. al. \cite{EKZ}, and setting a new record for distance of explicit quantum LDPC codes. The work of \cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes, and using their newly derived property, the collective cosystolic expansion.

arXiv:2008.09495•Aug 21, 2020•13 citations

Quantum Expander Codes

Anthony Leverrier, Jean–Pierre Tillich, Gilles Zémor

We present an efficient decoding algorithm for constant rate quantum hyper graph-product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the block length. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

arXiv:1504.00822•Annual Symposium on Foundations of Computer Science•Oct 1, 2015•117 citations

Quantum LDPC codes with $Ω(\sqrt{n}\log^kn)$ distance, for any $k$

Tali Kaufman, Ran J. Tessler

In this work we construct quantum LDPC codes of distance $\sqrt{n} \log^k n$ for any $k$, improving a recent result of Evra et. al. \cite{EKZ}. The work of \cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes. The main conceptual contribution of our work is the following: a tensor product of a cosystolic expander with a complex with a linear cosystole has a linear cosystole.

•Aug 21, 2020•3 citations

Efficient decoding of random errors for quantum expander codes

Omar Fawzi, Antoine Grospellier, Anthony Leverrier

We show that quantum expander codes, a constant-rate family of quantum low-density parity check (LDPC) codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Zémor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman’s construction of fault tolerant schemes with constant space overhead.

arXiv:1711.08351•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2018•3 citations

Breaking the Orthogonality Barrier in Quantum LDPC Codes

Kenta Kasai

Classical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular $[[9216,4612, \leq 48]]$ quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as $10^{-8}$ on the depolarizing channel with error probability $4 \%$.

quant-pharXiv:2601.08824•Quantum•Jan 14, 2026•31 citations
Decodable Quantum LDPC Codes beyond the n\sqrt{n}n​ Distance Barrier Using High-Dimensional Expanders
Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large XXX-distance but a much smaller ZZZ-distance. However, together with a classical expander LDPC code and a tensoring method that generalizes a construction of Hastings and also the Tillich–Zémor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance n1/2log⁡1/2nn^{1/2}\log^{1/2}nn1/2log1/2n. We then exploit the expansion properties of the complex to devise the first polynomial-time algorithm that decodes above the square root barrier for quantum LDPC codes. Using a 3-dimensional Ramanujan complex, we also obtain an overall quantum code of minimum distance n1/2log⁡nn^{1/2}\log nn1/2logn, which sets a new record for quantum LDPC codes.
Constructing quantum LDPC codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large X-distance but a much smaller Z-distance. However, together with a classical expander LDPC code and a tensoring method that generalises a construction of Hastings and also the Tillich-Zemor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 3-dimensional Ramanujan complex, we show that its 2-systole behaves like a square of the log of the complex size, which results in an overall quantum code of minimum distance n1/2logn, and sets a new record for quantum LDPC codes. When we use a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance n1/2log1/2n. We then exploit the expansion properties of the complex to devise the first polynomial time algorithm that decodes above the square root barrier for quantum LDPC codes.
New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with Ω(nlog⁡kn)Ω(\sqrt{n}\log^kn)Ω(n​logkn) Distance
In this work we introduce a new notion of expansion in higher dimensions that is stronger than the well studied cosystolic expansion notion, and is termed {\em Collective-cosystolic expansion}. We show that tensoring two cosystolic expanders yields a new cosystolic expander, assuming one of the complexes in the product, is not only cosystolic expander, but rather a collective cosystolic expander. We then show that the well known bounded degree cosystolic expanders, the Ramanujan complexes are, in fact, collective cosystolic expanders. This enables us to construct new bounded degree cosystolic expanders, by tensoring of Ramanujan complexes. Using our new constructed bounded degree cosystolic expanders we construct {\em explicit} quantum LDPC codes of distance nlog⁡kn\sqrt{n} \log^k nn​logkn for any kkk, improving a recent result of Evra et. al. \cite{EKZ}, and setting a new record for distance of explicit quantum LDPC codes. The work of \cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes, and using their newly derived property, the collective cosystolic expansion.
We present an efficient decoding algorithm for constant rate quantum hyper graph-product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the block length. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.
Quantum LDPC codes with Ω(nlog⁡kn)Ω(\sqrt{n}\log^kn)Ω(n​logkn) distance, for any kkk
In this work we construct quantum LDPC codes of distance nlog⁡kn\sqrt{n} \log^k nn​logkn for any kkk, improving a recent result of Evra et. al. \cite{EKZ}. The work of \cite{EKZ} took advantage of the high dimensional expansion notion known as cosystolic expansion, that occurs in Ramanujan complexes. Our improvement is achieved by considering tensor product of Ramanujan complexes. The main conceptual contribution of our work is the following: a tensor product of a cosystolic expander with a complex with a linear cosystole has a linear cosystole.
We show that quantum expander codes, a constant-rate family of quantum low-density parity check (LDPC) codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Zémor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman’s construction of fault tolerant schemes with constant space overhead.
Classical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular [[9216,4612,≤48]][[9216,4612, \leq 48]][[9216,4612,≤48]] quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as 10−810^{-8}10−8 on the depolarizing channel with error probability 4%4 \%4%.