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.

The stabilizer generator matrix of a \([[ n=2\ell,k,d]]\) GB\((a,b)\) code over \(GF(q)\), 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\(\ell\times\ell\) are circulant matrices \(A=a(P)\) and \(B=b(P)\), 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) \text{and} 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\text{deg}h(x)\), twice the dimension of the underlying classical code [4].

Two codes GB\((a,b)\) and GB\((a',b')\) of the same size \(n=2\ell\) are equivalent if the following five conditions are 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)\); (5) \(a'(x)=f(x)a(x), b'(x)=f(x)b(x)\), for some polynomial \(f(x)\in GF(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 GF(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 GF(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 \(GF(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 \(GF(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 CITE BibID: 2487773. 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 [4].

Parents

  • Galois-qudit CSS code — A GB code is a Galois-qudit CSS code constructed from a pair of equivalent index-two quasi-cyclic linear codes.
  • Quantum quasi-cyclic 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 can be used as sub-matrices to define a 1D SC-QLDPC code [5].
  • Quantum low-density parity-check (QLDPC) code — A code GB\((a,b)\) is 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 — In some GB error-correcting schemes, localized syndrome measurement errors only give rise to localized errors in the correction stage. Then, a single round of measurements is enough, and fault-tolerant error correction is quantum-local [6].
  • Cyclic quantum code — Given a canonical generating polynomial \(g(x)\) of a cyclic quantum code \([[n,k,d]]\), its generator matrix is a cyclic matrix \(G=g(P)\). Here \(P\) is the permutation matrix of one-step length-\(n\) cyclic shift.
  • Hypergraph product (HGP) code — An arbitrary GB code of length \(2\ell\) is equivalent 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}=\ell}\rvert\).

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]
P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
[5]
S. Yang and R. Calderbank, “Quantum Spatially-Coupled Codes”, (2023) arXiv:2305.00137
[6]
H. Bombín, “Single-Shot Fault-Tolerant Quantum Error Correction”, Physical Review X 5, (2015) arXiv:1404.5504 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/generalized_bicycle.yml.