Generalized bicycle (GB) code[1,2] 

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

GB codes can achieve an asymptotic rate of 1/4 [2]. For an odd prime \(\ell\), let a prime \(p\) be a quadratic residue modulo \(\ell\), i.e. \(p=m^{2}\text{mod}\ell\) for some integer \(m\). Then, \(x^{\ell}-1\) has only three irreducible factors in \(\mathbb{F}_q(x)\), and there is a quadratic-residue cyclic code \([\ell,(\ell+1)/2, d]_p\) with \(d\geq\sqrt{\ell}\) and an irreducible generator polynomial. Using the GV distance \(d_{GV}\), a prime-field GB code with parameters \([[ 2\ell,(\ell-1)/2,d\geq \ell^{1/2}]]_p\) exists.

Decoding

BP-OSD decoder [5].

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

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: generalized_bicycle

Cite as:
“Generalized bicycle (GB) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/generalized_bicycle
BibTeX:
@incollection{eczoo_generalized_bicycle, title={Generalized bicycle (GB) code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/generalized_bicycle} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/generalized_bicycle

Cite as:

“Generalized bicycle (GB) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/generalized_bicycle

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/quantum/qudits_galois/qldpc/algebraic/generalized_bicycle.yml.