Define the codewords of the Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;r_2,m_2;\dots;r_t,m_t)$ to be the evaluation vectors of all multivariate polynomials in the variables $\left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_i}$ with degree at most $r_i$ in the variables $x_{i1},x_{i2},\dots,x_{im_i}$ . The generator matrix of $\mathsf{TRM}(r_1,m_1;\dots;r_t,m_t)$ is thus the tensor product of the generator matrices of the Reed-Muller codes $\mathsf{RM}(r_1,m_1),\dots, \mathsf{RM}(r_t,m_t)$ . We show that for any constant rate $R$ below capacity, one can construct a Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;\dotsc;r_t,m_t)$ of rate $R$ that is decodable in quasilinear time. For any blocklength $n$ , we provide two constructions of such codes: 1) Our first construction (with $t=3$ ) has error probability $n^{-ω(\log n)}$ and decoding time $O(n\log\log n)$ . 2) Our second construction, for any $t\geq 4$ , has error probability $2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}}$ and decoding time $O(n\log n)$ . One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code $C=C_1\otimes\dotsc\otimes C_t$ from $\frac{d_{\min}(C)}{2\max\{d_{\min}(C_1),\dotsc,d_{\min}(C_t) \}}-1$ adversarial errors. Crucially, this algorithm does not require the codes $C_1,\dotsc,C_t$ to themselves be decodable in polynomial time.Define the codewords of the Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;r_2,m_2;\dots;r_t,m_t)$ to be the evaluation vectors of all multivariate polynomials in the variables $\left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_i}$ with degree at most $r_i$ in the variables $x_{i1},x_{i2},\dots,x_{im_i}$. The generator matrix of $\mathsf{TRM}(r_1,m_1;\dots;r_t,m_t)$ is thus the tensor product of the generator matrices of the Reed-Muller codes $\mathsf{RM}(r_1,m_1),\dots, \mathsf{RM}(r_t,m_t)$. We show that for any constant rate $R$ below capacity, one can construct a Tensor Reed-Muller code $\mathsf{TRM}(r_1,m_1;\dotsc;r_t,m_t)$ of rate $R$ that is decodable in quasilinear time. For any blocklength $n$, we provide two constructions of such codes: 1) Our first construction (with $t=3$) has error probability $n^{-ω(\log n)}$ and decoding time $O(n\log\log n)$. 2) Our second construction, for any $t\geq 4$, has error probability $2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}}$ and decoding time $O(n\log n)$. One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code $C=C_1\otimes\dotsc\otimes C_t$ from $\frac{d_{\min}(C)}{2\max\{d_{\min}(C_1),\dotsc,d_{\min}(C_t) \}}-1$ adversarial errors. Crucially, this algorithm does not require the codes $C_1,\dotsc,C_t$ to themselves be decodable in polynomial time.

arXiv:2601.16164IEEE International Symposium on Information Theory (ISIT)Jun 1, 20261 citation

Quantum codes from linear codes over finite chain rings

Xiusheng Liu, Hualu Liu

arXiv:1704.06375Quantum Information ProcessingAug 20, 201737 citations

New quantum codes from constacyclic codes over a general non-chain ring

Swati Bhardwaj, Mokshi Goyal, Madhu Raka

Let [Formula: see text] be a prime power and let [Formula: see text] be a finite non-chain ring, where [Formula: see text], are polynomials, not all linear, which split into distinct linear factors over [Formula: see text]. We characterize constacyclic codes over the ring [Formula: see text] and study quantum codes from these. As an application, some new and better quantum codes, as compared to the best known codes, are obtained. We also prove that the choice of the polynomials [Formula: see text], [Formula: see text], is irrelevant while constructing quantum codes from constacyclic codes over [Formula: see text], it depends only on their degrees.Let [Formula: see text] be a prime power and let [Formula: see text] be a finite non-chain ring, where [Formula: see text], are polynomials, not all linear, which split into distinct linear factors over [Formula: see text]. We characterize constacyclic codes over the ring [Formula: see text] and study quantum codes from these. As an application, some new and better quantum codes, as compared to the best known codes, are obtained. We also prove that the choice of the polynomials [Formula: see text], [Formula: see text], is irrelevant while constructing quantum codes from constacyclic codes over [Formula: see text], it depends only on their degrees.

arXiv:2212.02821Discrete Mathematics Algorithms and ApplicationsAug 18, 202311 citations

About on the obtaining of some quantum code parameters from ( − 2 v m −1 + 1)-constacyclic codes over the ring R = 𝔽 q + v 𝔽 q + · · · + v m −1 𝔽 q

Gökhan Gökgöz, Figen Öke

Abstract In this study, the hull dimensions of ( − 2 v m −1 +1)-constacyclic codes over the ring R = 𝔽 q + v 𝔽 q + · · · + v m −1 𝔽 q with v m = v are determined. In addition, by using a special Gray map, a necessary condition is given under which the generator polynomial of a ( − 2 v m −1 + 1)-constacyclic code over R yields, through the polynomial representation of the Gray map, the generator polynomial of the corresponding cyclic code over F q . Later, an example is presented showing that the parameters of a quantum error-correcting code over F q can be obtained from a ( − 2 v m −1 +1)-constacyclic code over R by means of the X-construction method. Furthermore, the case in which the number of ( − 2 v m −1 + 1)-constacyclic codes of length n over R equals the number of cyclic codes of length 2 n over F q is examined, and an example is provided in which the parameters of the quantum error-correcting codes arising from those cyclic codes—which are Gray images of ( − 2 v m −1 + 1)-constacyclic codes over R —are presented.Abstract In this study, the hull dimensions of ( − 2 v m −1 +1)-constacyclic codes over the ring R = 𝔽 q + v 𝔽 q + · · · + v m −1 𝔽 q with v m = v are determined. In addition, by using a special Gray map, a necessary condition is given under which the generator polynomial of a ( − 2 v m −1 + 1)-constacyclic code over R yields, through the polynomial representation of the Gray map, the generator polynomial of the corresponding cyclic code over F q . Later, an example is presented showing that the parameters of a quantum error-correcting code over F q can be obtained from a ( − 2 v m −1 +1)-constacyclic code over R by means of the X-construction method. Furthermore, the case in which the number of ( − 2 v m −1 + 1)-constacyclic codes of length n over R equals the number of cyclic codes of length 2 n over F q is examined, and an example is provided in which the parameters of the quantum error-correcting codes arising from those cyclic codes—which are Gray images of ( − 2 v m −1 + 1)-constacyclic codes over R —are presented.

Analele Universităţii "Ovidius" Constanţa. Seria MatematicăJul 1, 20260 citations

Define the codewords of the Tensor Reed-Muller code

\mathsf{TRM}(r_1,m_1;r_2,m_2;\dots;r_t,m_t)

to be the evaluation vectors of all multivariate polynomials in the variables

\left\{x_{ij}\right\}_{i=1,\dots,t}^{j=1,\dots m_i}

with degree at most

r_i

in the variables

x_{i1},x_{i2},\dots,x_{im_i}

. The generator matrix of

\mathsf{TRM}(r_1,m_1;\dots;r_t,m_t)

is thus the tensor product of the generator matrices of the Reed-Muller codes

\mathsf{RM}(r_1,m_1),\dots, \mathsf{RM}(r_t,m_t)

. We show that for any constant rate

R

below capacity, one can construct a Tensor Reed-Muller code

\mathsf{TRM}(r_1,m_1;\dotsc;r_t,m_t)

of rate

R

that is decodable in quasilinear time. For any blocklength

n

, we provide two constructions of such codes: 1) Our first construction (with

t=3

) has error probability

n^{-ω(\log n)}

and decoding time

O(n\log\log n)

. 2) Our second construction, for any

t\geq 4

, has error probability

2^{-n^{\frac{1}{2}-\frac{1}{2(t-2)}-o(1)}}

and decoding time

O(n\log n)

. One of our main tools is a polynomial-time algorithm for decoding an arbitrary tensor code

C=C_1\otimes\dotsc\otimes C_t

from

\frac{d_{\min}(C)}{2\max\{d_{\min}(C_1),\dotsc,d_{\min}(C_t) \}}-1

adversarial errors. Crucially, this algorithm does not require the codes

C_1,\dotsc,C_t

to themselves be decodable in polynomial time.