Description
A quasi-cyclic Galois-qudit CSS code constructed using a generalized version of the bicycle ansatz [3] from a pair of equivalent index-two quasi-cyclic linear codes. Various instances of qubit GB codes are constructed in Ref. [2] (only codes with \(k=2\)) and in Ref. [4].
The stabilizer generator matrix of a \([[ n=2\ell,k,d]]_q\) GB\((a,b)\) code, constructed from polynomials \(a(x)\) and \(b(x)\), can be refined to the form \begin{align} H_{X}=(A|B), H_{Z}^{T}=\begin{pmatrix}A\\-B\end{pmatrix}~, \tag*{(1)}\end{align} where \(A=a(P)\) and \(B=b(P)\) are \(\ell\times\ell\) circulant matrices, and \(P\) is the permutation matrix of a one-step length-\(\ell\) cyclic shift.
With any GB\((a,b)\) code, there is an associated \(q\)-ary cyclic classical code \(C_{h(x)}^{\perp}=C_{g(x)}\) of length \(\ell\), with the check and generating polynomials \begin{align} h(x)=\text{gcd}(a(x),b(x),x^{\ell}-1) \quad\text{and}\quad g(x)=\frac{x^{\ell}-1}{h(x)}~, \tag*{(2)}\end{align} respectively. The number of qudits encoded in such a GB code is \(k=2\deg h(x)\), twice the dimension of the underlying classical code [5].
Two codes GB\((a,b)\) and GB\((a',b')\) of the same size \(n=2\ell\) are equivalent if one of the following conditions is satisfied [2]:
- (1)
\(a'(x)=a(x^{m})\) mod \(x^{\ell}-1\), \(b'(x)=b(x^{m})\) mod \(x^{\ell}-1\) for some \(m\) mutually prime with \(\ell\), gcd\((m,\ell)=1\);
- (2)
\(a'(x)=b(x), b'(x)=a(x)\);
- (3)
\(a'(x)\) and \(b'(x)\) are the reciprocal polynomials of \(a(x)\) and \(b(x)\), respectively;
- (4)
\(a'(x)=\delta a(x), b'(x)=b(x)\), for some \(0\neq\delta\in GF(q)=\mathbb{F}_q\);
- (5)
\(a'(x)=f(x)a(x), b'(x)=f(x)b(x)\), for some polynomial \(f(x)\in \mathbb{F}_q[x]\) such that gcd\((f,x^{\ell}-1)=1\).
The following modified construction yields asymmetric bicycle (AB) codes: \(\mathcal{Q}'=\text{CSS}(H'_{X},H_{Z})\) has \(H'_{X}=(A_{1}|B_{1}),A_{1}=a_{1}(P),B_{1}=b{1}(P)\), where \(a_{1}=\frac{a(x)}{\text{gcd}(a,b)},b_{1}=\frac{b(x)}{\text{gcd}(a,b)}\).
Protection
Given the parameters \([n_{0}=2\ell,k_{0},d_{0}]_q\) of the classical linear quasi-cyclic code QC\((a,b)\), the quantum CSS code GB\((a,b)\) has parameters \([[ 2\ell,2k_{0}-2\ell,d]]_q\) where \(d\geq d_{0}\).
Consider a quasi-cyclic QC\((a,b)\) in the special case \(a(x)=f(x)h(x),b(x)=h(x)\), where for some polynomial \(r(x)\), \(\text{gcd}(a(x),b(x),x^{\ell}-1)=p(x)\) is a factor of the generating polynomial, \(g(x)=p(x)q(x)\). Then the distance of the QC code satisfies the following two bounds:
- (a)
If \(r(x)=0,d_{0}\geq\text{min}\{d[q],1+d[q]\}\);
- (b)
Otherwise, if gcd\((a(x),b(x),x^{\ell}-1)=1\), then \(d_{0}\text{min}{2d[q],d[q]/\text{wgt}(r)}\).
Here, \(h(x)=\text{gcd}(a(x),b(x),x^{\ell}-1)\) and \(g(x)=\frac{x^{\ell}-1}{h(x)}\), and \(d[q]\) is the distance of the linear cyclic code generated by \(q(x)\) [2].
Let \(x^{\ell}-1=g(x)h(x)\) with \(g(x)\in \mathbb{F}_q[x]\) irreducible, and \begin{align} \label{eq:gb_gv} d_{GV}=\text{max }d:\sum_{s=1}^{d-1}(q-1)^{s}\left[\begin{pmatrix}2\ell\\ s \end{pmatrix}-\begin{pmatrix}\ell\\ s \end{pmatrix}\right]\,. \tag*{(3)}\end{align} Then, there exists \(f(x)\in \mathbb{F}_q[x]\) such that the length-\(2\ell\) quasi-cyclic code QC\((hf,h)\) has distance \(d\geq\text{min}(d[g],d_{GV})\), where \(d[g]\) is the distance of the cyclic code generated by \(g(x)\) [2].
GB codes with linear distance
Let \(\ell\) be such that \(\text{ord}_{\ell}-1=\ell-1\), where \(\text{ord}_{\ell}(q)\) is the multiplicative order function of \(q\) modulo \(\ell\). This ensures that \(x^{\ell}-1\) has only two irreducible factors in \(\mathbb{F}_q[x]\), \(h(x)=1-x\), and \(g(x)=1+x+\cdots+x^{\ell-1}\). Then, there is a GB code with parameters \([[ 2\ell,2,d\geq d_{GV}]]_q\) [2].
An incommensurate GB code with row weight \(w\) and parameters \([[ n=2\ell,k,d]]_p\) is equivalent to a CSS code local in \(D\leq w-1\) dimensions (\(D\leq w-1\) if \(\ell\) is prime). Its parameters satisfy the inequalities \(d\leq\mathcal{O}(n^{1-1/D})\) and \(kd^{2/(D-1)}\leq\mathcal{O}(n)\) [2].
A weight-four GB code of an odd distance \(d=2r+1\) must have length \(n\geq 1+d^{2}\). For an even distance \(d=2r\), the length \(n\geq d^{2}\) [2].
Rate
Decoding
Parents
- Two-block group-algebra (2BGA) codes — A code GB\((a,b)\) with circulants of size \(\ell\) is a special case of a 2BGA code over the cyclic group \(\mathbb{Z}_{\ell}\). More precisely, for the cyclic group \(\mathbb{Z}_{\ell}\equiv \langle x|x^\ell=1\rangle \), any element \(a\) of the group algebra \(\mathbb{F}_q[\mathbb{Z}_{\ell}]\) can be seen as a polynomial \(a(x)\in \mathbb{F}_q[x]\) over the group generator \(x\), where the polynomial degree \(\deg a(x)<\ell\). The 2BGA code LP\((a,b)\) is then just a generalized bicycle code GB\([a(x),b(x)]\) constructed from the polynomials \(a(x)\) and \(b(x)\) corresponding to \(a,b\in \mathbb{F}_q[\mathbb{Z}_{\ell}]\).
- Lifted-product (LP) code — A code GB\((a,b)\) with circulants of size \(\ell\) is a special (degenerate) case of a lifted-product code LP\((A,B)\) code over the Abelian group algebra \(\mathbb{F}_q[\mathbb{Z}_{\ell}]\) associated with the cyclic group \(\mathbb{Z}_{\ell}\equiv \langle x|x^\ell=1\rangle\), with \(1\times 1\) matrices \(A=a(x)\), \(B=b(x)\) given by the corresponding polynomials.
- Quasi-cyclic quantum code — An index-\(m\) quasi-cyclic (QC) code of length \(n=m\ell\) is usually defined as a linear code invariant under the \(m\)-step shift permutation \(T_{n}^{m}\).
Cousins
- Quantum spatially coupled (SC-QLDPC) code — Qubit GB stabilizer generator matrices is equivalent to a 1D SC-QLDPC code, see [6; Remark 7].
- Quantum low-density parity-check (QLDPC) code — Stabilizer generators of the code GB\((a,b)\) have weights given by the sum of weights of polynomials \(a(x)\) and \(b(x)\). The GB code ansatz is convenient for designing quantum LDPC codes.
- Single-shot code — A qubit GB code \([[n,k,d]]_2\) has \(k\) non-trivial relations between the syndrome bits, which is expected to help with operation in a fault-tolerant regime (in the presence of syndrome measurement errors). See Ref. [4] for many examples of such codes.
- Hypergraph product (HGP) code — An arbitrary GB code of length \(2\ell\) is equivalent [2] to a rotated quantum hypergraph-product code with periodicity vectors \(\vec{L}_{1}\) and \(\vec{L}_{2}\) such that \(\lvert{\vec{L}_{1}\times\vec{L}_{2}\rvert=\ell}\).
- Haah cubic code — A GB code for the group \(G=\mathbb{Z}_3^{\times 3}\) is the cubic code [7; Sec. III.A].
References
- [1]
- A. A. Kovalev and L. P. Pryadko, “Quantum Kronecker sum-product low-density parity-check codes with finite rate”, Physical Review A 88, (2013) arXiv:1212.6703 DOI
- [2]
- R. Wang and L. P. Pryadko, “Distance bounds for generalized bicycle codes”, (2022) arXiv:2203.17216
- [3]
- D. J. C. MacKay, G. Mitchison, and P. L. McFadden, “Sparse-Graph Codes for Quantum Error Correction”, IEEE Transactions on Information Theory 50, 2315 (2004) arXiv:quant-ph/0304161 DOI
- [4]
- H.-K. Lin and L. P. Pryadko, “Quantum two-block group algebra codes”, (2023) arXiv:2306.16400
- [5]
- P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
- [6]
- S. Yang and R. Calderbank, “Spatially-Coupled QDLPC Codes”, (2023) arXiv:2305.00137
- [7]
- P. Panteleev and G. Kalachev, “Quantum LDPC Codes With Almost Linear Minimum Distance”, IEEE Transactions on Information Theory 68, 213 (2022) arXiv:2012.04068 DOI
Page edit log
- Victor V. Albert (2023-10-16) — most recent
- Leonid Pryadko (2023-10-10)
- Victor V. Albert (2023-05-02)
- Leonid Pryadko (2023-05-02)
- Renyu Wang (2023-05-02)
Cite as:
“Generalized bicycle (GB) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/generalized_bicycle