## 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. Equivalently, the codes can constructed via the lifted-product construction for \(G\) being a cyclic group [4; Sec. III.E].

Various instances of qubit GB codes are constructed in Ref. [2] (for \(k=2\)) and in Refs. [5–7].

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}B\\-A\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. This refinement is a special case of symplectic doubling.

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

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

## Code Capacity Threshold

## 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}]\).
- Abelian 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 a cyclic group, with \(1\times 1\) matrices \(A=a(x)\), \(B=b(x)\) given by the corresponding polynomials. Quasi-cyclic LP codes, i.e., LP codes constructed from cyclic groups, are equivalent to GB codes [4; Sec. III.E].

## Child

- Bicycle code — A GB code with whose circulants satistfy \(B = A^T\) reduces to a bicycle code.

## Cousins

- Quantum spatially coupled (SC-QLDPC) code — Qubit GB codes can be categorized as 1D SC-QLDPC codes, see [9; Remark 7].
- Quantum LDPC (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 [10].
- 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. There is numerical evidence that a particular family is single shot [7].
- Hypergraph product (HGP) code — An arbitrary qubit 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 (CC) — A GB code for the group \(G=\mathbb{Z}_3^{\times 3}\) is a cubic code [4; 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]
- 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
- [5]
- H.-K. Lin and L. P. Pryadko, “Quantum two-block group algebra codes”, (2023) arXiv:2306.16400
- [6]
- J. Viszlai et al., “Matching Generalized-Bicycle Codes to Neutral Atoms for Low-Overhead Fault-Tolerance”, (2024) arXiv:2311.16980
- [7]
- T. R. Scruby, T. Hillmann, and J. Roffe, “High-threshold, low-overhead and single-shot decodable fault-tolerant quantum memory”, (2024) arXiv:2406.14445
- [8]
- P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021) arXiv:1904.02703 DOI
- [9]
- S. Yang and R. Calderbank, “Spatially-Coupled QDLPC Codes”, (2023) arXiv:2305.00137
- [10]
- N. Koukoulekidis et al., “Small Quantum Codes from Algebraic Extensions of Generalized Bicycle Codes”, (2024) arXiv:2401.07583

## 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