arXiv:0903.0566 · IEEE Transactions on Information Theory

Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength

Jean–Pierre Tillich, Gilles Zémor

Published Jan 24, 2014• 345 citations

Abstract

The current best asymptotic lower bound on the minimum distance of quantum LDPC codes with a fixed non-zero rate is logarithmic in the blocklength. We propose a construction of quantum LDPC codes with fixed non-zero rate and prove that the minimum distance grows proportionally to the square root of the blocklength.

DOI: 10.1109/tit.2013.2292061

Related papers

Quantum LDPC codes with positive rate and minimum distance proportional to n½

Jean–Pierre Tillich, Gilles Zémor

The current best asymptotic lower bound on the minimum distance of quantum LDPC codes with fixed non-zero rate is logarithmic in the block length. We build quantum LDPC codes with fixed non-zero rate and prove that their minimum distance grows proportionally to the square root of the block length.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 200946 citations

Quantum LDPC codes obtained by non-binary constructions

Iryna Andriyanova, Denise Maurice, Jean–Pierre Tillich

We generalize a construction of non-binary quantum LDPC codes over F2mdue to [KHIK11] and apply it in particular to toric codes. We obtain in this way not only codes with better rates than toric codes but also improve dramatically the performance of standard iterative decoding. Moreover, the new codes obtained in this fashion inherit the distance properties of the underlying toric codes and have therefore a minimum distance which grows as the square root of the length of the code for fixed m.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20127 citations

Quantum LDPC Codes With Almost Linear Minimum Distance

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

arXiv:2012.04068IEEE Transactions on Information TheoryOct 11, 2021170 citations

Decodable quantum LDPC codes beyond the √n distance barrier using high dimensional expanders.

Shai Evra, Tali Kaufman, Gilles Zémor

Apr 16, 20205 citations

Quantum LDPC Codes Constructed from Point-Line Subsets of the Finite Projective Plane

Jacob Farinholt

arXiv:1207.0732Jul 3, 20122 citations

A Construction of Quantum LDPC Codes From Cayley Graphs

Alain Couvreur, Nicolas Delfosse, Gilles Zémor

IEEE Transactions on Information TheoryMay 21, 201330 citations

arXiv:0903.0566 · IEEE Transactions on Information Theory

Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength

Jean–Pierre Tillich, Gilles Zémor

Published Jan 24, 2014• 345 citations

arXiv HTML PDF

Abstract

DOI: 10.1109/tit.2013.2292061

Related papers

Quantum LDPC codes with positive rate and minimum distance proportional to n½

Jean–Pierre Tillich, Gilles Zémor

IEEE International Symposium on Information Theory (ISIT)Jun 1, 200946 citations

Quantum LDPC codes obtained by non-binary constructions

Iryna Andriyanova, Denise Maurice, Jean–Pierre Tillich

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20127 citations

Quantum LDPC Codes With Almost Linear Minimum Distance

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

We give a construction of quantum LDPC codes of dimension $\Theta (\log N)$ and distance $\Theta (N/\log N)$ as the code length$N\to \infty $. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance$ \Omega (N^{1-\alpha /2}/\log N) $and dimension$ \Omega (N^\alpha \log N)$, where $0 \le \alpha < 1$ . We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed $R < 1$ there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least $R$ with, in some sense, optimal circulant size $\Omega (N/\log N)$ as the code length$N\to \infty $.We give a construction of quantum LDPC codes of dimension$\Theta (\log N)$and distance$\Theta (N/\log N)$as the code length$N\to \infty $. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance$\Omega (N^{1-\alpha /2}/\log N)$and dimension$\Omega (N^\alpha \log N)$, where$0 \le \alpha < 1$. We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed$R < 1$there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least$R$with, in some sense, optimal circulant size$\Omega (N/\log N)$as the code length$N\to \infty $.

arXiv:2012.04068IEEE Transactions on Information TheoryOct 11, 2021170 citations

Decodable quantum LDPC codes beyond the √n 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 $n^{1/2}\log n$ , 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 $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.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 $n^{1/2}\log n$, 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 $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.

Apr 16, 20205 citations

Quantum LDPC Codes Constructed from Point-Line Subsets of the Finite Projective Plane

Jacob Farinholt

Due to their fast decoding algorithms, quantum generalizations of low-density parity check, or LDPC, codes have been investigated as a solution to the problem of decoherence in fragile quantum states. However, the additional twisted inner product requirements of quantum stabilizer codes force four-cycles and eliminate the possibility of randomly generated quantum LDPC codes. Moreover, the classes of quantum LDPC codes discovered thus far generally have unknown or small minimum distance, or a fixed rate. This paper presents several new classes of quantum LDPC codes constructed from finite projective planes. These codes have rates that increase with the block length $n$ and minimum weights proportional to $n^{1/2}$ .Due to their fast decoding algorithms, quantum generalizations of low-density parity check, or LDPC, codes have been investigated as a solution to the problem of decoherence in fragile quantum states. However, the additional twisted inner product requirements of quantum stabilizer codes force four-cycles and eliminate the possibility of randomly generated quantum LDPC codes. Moreover, the classes of quantum LDPC codes discovered thus far generally have unknown or small minimum distance, or a fixed rate. This paper presents several new classes of quantum LDPC codes constructed from finite projective planes. These codes have rates that increase with the block length $n$ and minimum weights proportional to $n^{1/2}$.

arXiv:1207.0732Jul 3, 20122 citations

A Construction of Quantum LDPC Codes From Cayley Graphs

Alain Couvreur, Nicolas Delfosse, Gilles Zémor

We study a construction of quantum LDPC codes proposed by MacKay, Mitchison, and Shokrollahi. It is based on the Cayley graph of \BBF2ntogether with a set of generators regarded as the columns of the parity-check matrix of a classical code. We give a general lower bound on the minimum distance of the quantum code in O(dn2) where d is the minimum distance of the classical code. This bound is logarithmic in the blocklength 2nof the quantum code. When the classical code is the [n,1,n] repetition code, we are able to compute the exact parameters of the associated quantum code which are [[2n, 2[(n+1)/2], 2[(n-1)/2]]].We study a construction of quantum LDPC codes proposed by MacKay, Mitchison, and Shokrollahi. It is based on the Cayley graph of \BBF2ntogether with a set of generators regarded as the columns of the parity-check matrix of a classical code. We give a general lower bound on the minimum distance of the quantum code in O(dn2) where d is the minimum distance of the classical code. This bound is logarithmic in the blocklength 2nof the quantum code. When the classical code is the [n,1,n] repetition code, we are able to compute the exact parameters of the associated quantum code which are [[2n, 2[(n+1)/2], 2[(n-1)/2]]].

IEEE Transactions on Information TheoryMay 21, 201330 citations

We give a construction of quantum LDPC codes of dimension

\Theta (\log N)

and distance

\Theta (N/\log N)

as the code length$N\to \infty

. Using a product of chain complexes this construction also provides a family of quantum LDPC codes of distance

\Omega (N^{1-\alpha /2}/\log N)

and dimension

\Omega (N^\alpha \log N)$, where

0 \le \alpha < 1

. We also introduce and study a new operation called lifted product, which naturally generalizes the product operations for quantum codes and chain complexes. Moreover, as a simple byproduct of our results on quantum codes, we obtain a new result on classical codes. We show that for any fixed

R < 1

there exists an asymptotically good family of classical quasi-cyclic LDPC codes of rate at least

R

with, in some sense, optimal circulant size

\Omega (N/\log N)

as the code length$N\to \infty $.

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

n^{1/2}\log n

, 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

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.

n

and minimum weights proportional to

n^{1/2}