Generalized bicycle (GB) code[13] 

Description

A quasi-cyclic Galois-qudit CSS code constructed using a generalized version of the bicycle ansatz [4] from a pair of equivalent index-two quasi-cyclic linear codes. Various instances of qubit GB codes are constructed in Ref. [3] (for \(k=2\)) and in Ref. [5].

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 [6].

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 [3]:

(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)\) [3].

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)\) [3].

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\) [3].

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)\) [3].

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}\) [3].

Rate

GB codes can achieve an asymptotic rate of 1/4 [3]. 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 [6].

Code Capacity Threshold

Depolarizing noise: \(15\%\) for a family of 6-limited \([[2^{m+1}-2,2m]]\) GB codes with BP-OSD decoder [6; Appx. C].

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 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 [7; 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 QLDPC codes and several extensions exist [8].
  • 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. [5] for many examples of such codes.
  • Hypergraph product (HGP) code — An arbitrary GB code of length \(2\ell\) is equivalent [3] 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 (CC) — A GB code for the group \(G=\mathbb{Z}_3^{\times 3}\) is a cubic code [9; 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]
M. B. Hastings, LR codes, private communication, 2014.
[3]
R. Wang and L. P. Pryadko, “Distance bounds for generalized bicycle codes”, (2022) arXiv:2203.17216
[4]
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
[5]
H.-K. Lin and L. P. Pryadko, “Quantum two-block group algebra codes”, (2023) arXiv:2306.16400
[6]
P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
[7]
S. Yang and R. Calderbank, “Spatially-Coupled QDLPC Codes”, (2023) arXiv:2305.00137
[8]
N. Koukoulekidis et al., “Small Quantum Codes from Algebraic Extensions of Generalized Bicycle Codes”, (2024) arXiv:2401.07583
[9]
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)— see instructions

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/edit/main/codes/quantum/qudits_galois/stabilizer/qldpc/algebraic/generalized_bicycle.yml.