Mathematical Problems of Cybernetics

Asymptotically good families of quantum and locally testable classical LDPC codes

Gleb Vyacheslavovich Kalachev, Pavel Panteleev

Published Jan 1, 2023• 0 citations

Abstract

In this paper we study classical and quantum LDPC codes with constant rate obtained using tensor product operation over noncommutative group algebra for chain complexes. It is shown that these families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. The existence of asymptotically good families of locally testable codes with constant parameters of locality and soundness is also shown, which gives the solution of the known conjecture in the field of classical locally testable codes.

DOI: 10.20948/mvk-2023-111

Related papers

Asymptotically good Quantum and locally testable classical LDPC codes

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.

ACM Symposium on Theory of Computing (STOC)Jun 9, 2022222 citations

Asymptotically Good Quantum Locally Testable Codes

William Gay, Fernando Granha Jeronimo

We construct explicit families of asymptotically good quantum locally testable codes over qubits. More precseily, we construct explicit quantum LDPC CSS codes over qubits having constant rate, constant relative distance and constant weight local testers with constant soundness.

quant-pharXiv:2609.20780Sep 18, 20260 citations

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

arXiv:2111.03654Nov 5, 20219 citations

Quantum LDPC Codes With Almost Linear Minimum Distance

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

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

Good Quantum Locally Testable Codes from Product Expansion

Mitali Bafna, Anqi Li, Quynh T. Nguyen

quant-pharXiv:2609.26735Sep 23, 20260 citations

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes

Irit Dinur, Ting-Chun Lin, Thomas Vidick

arXiv:2402.07476Feb 12, 20241 citation

Mathematical Problems of Cybernetics

Asymptotically good families of quantum and locally testable classical LDPC codes

Gleb Vyacheslavovich Kalachev, Pavel Panteleev

Published Jan 1, 2023• 0 citations

Publisher

Abstract

DOI: 10.20948/mvk-2023-111

Related papers

Asymptotically good Quantum and locally testable classical LDPC codes

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

ACM Symposium on Theory of Computing (STOC)Jun 9, 2022222 citations

Asymptotically Good Quantum Locally Testable Codes

William Gay, Fernando Granha Jeronimo

quant-pharXiv:2609.20780Sep 18, 20260 citations

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

arXiv:2111.03654Nov 5, 20219 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

Good Quantum Locally Testable Codes from Product Expansion

Mitali Bafna, Anqi Li, Quynh T. Nguyen

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.

quant-pharXiv:2609.26735Sep 23, 20260 citations

Expansion of higher-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>0, 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.We introduce a high-dimensional cubical complex, for any dimension t>0, 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.07476Feb 12, 20241 citation

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 $.

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.