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
Decoding
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
- Victor V. Albert (2023-05-02) — most recent
- 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