Distance Bounds for Generalized Bicycle Codes

Abstract

Generalized bicycle (GB) codes is a class of quantum error-correcting codes constructed from a pair of binary circulant matrices. Unlike for other simple quantum code ansätze, unrestricted GB codes may have linear distance scaling. In addition, low-density parity-check GB codes have a naturally overcomplete set of low-weight stabilizer generators, which is expected to improve their performance in the presence of syndrome measurement errors. For such GB codes with a given maximum generator weight w, we constructed upper distance bounds by mapping them to codes local in $D\le w-1$ dimensions, and lower existence bounds which give $d\ge \mathcal{O}\left(n^{1/2}\right)$. We have also conducted an exhaustive enumeration of GB codes for certain prime circulant sizes in a family of two-qubit encoding codes with row weights 4, 6, and 8; the observed distance scaling is consistent with $A\left(w\right)n^{1/2}+B\left(w\right)$, where n is the code length and $A\left(w\right)$ is increasing with w.

1. Introduction

In the last two years, there has been enormous progress in the theory of quantum low-density parity-check (LDPC) codes [1,2,3,4,5,6]. Such code families, with bounded weights of stabilizer generators and distance scaling logarithmically or faster with the block length, generally have a finite fault-tolerant threshold to scalable error correction [7,8,9]. Unlike in the case of classical LDPC codes [10,11] where sparse random matrices can be used to define the code, due to a commutativity constraint, an algebraic ansatz is required in the case of quantum LDPC codes. For over a decade, no construction was known to give distances larger than a square root of the block size n, up to a polylogarithmic factor [1,7,12,13,14,15,16,17,18,19]. The $\mathcal{O}\left(\sqrt{n}\mathrm{polylog}n\right)$ barrier was broken by Hastings, Haah, and O’Donnell [2] who demonstrated a code family with the distance $\mathcal{O}(n^{3/5}/\mathrm{polylog}n)$. Related constructions soon followed [3,4], with Panteleev and Kalachev [5] finally proving the existence of asymptotically good bounded-stabilizer-generator-weight LDPC codes, with both the asymptotic rate and the asymptotic relative distance non-zero.

Unfortunately, the constructions in Refs. [1,2,3,4,5] do not come with an estimate for stabilizer generator weights sufficient for obtaining good quantum codes, or if they do, not one small enough to give practical codes. Further, these anzätse tend to produce rather long codes; shorter codes obtained this way may have parameters that are not as good as constructions known earlier.

In comparison, generalized bicycle (GB) codes [15,20], a generalization of the bicycle construction from Ref. [21], are particularly suited for constructing short codes, as a GB code can be constructed from a pair of linear cyclic codes which are only a factor of two shorter. Second, as we show in this work, a subset of codes from several well-studied families, most notably, quantum hypergraph-product (QHP) codes in two and higher dimensions [14,17,18], including the codes with finite asymptotic rates and power-law distance scaling, can be mapped to bicycle codes. At the same time, the distance bound $d\le n^{1/2}$ which limits the parameters of all QHP codes, does not apply to GB codes; we show in this work that this family includes codes with linear distances. Third, the regular structure of GB codes simplifies both their implementation and linear-complexity iterative decoding [20,22,23,24]. Moreover, GB codes have naturally overcomplete sets of minimum-weight stabilizer generators, which may improve their performance in the fault-tolerant (FT) setting. In spite of these advantages and the long history of GB codes, their properties have not been systematically studied.

The goal of this work is to investigate the parameters of GB codes, targeting highly-degenerate codes with distances much larger than the stabilizer generator weight which for practical codes should stay under $w_{\max }\simeq 10$. While some of the present distance bounds are an easy consequence of those obtained for related codes, or are obtained with well known methods, we believe a systematic review of available results is necessary. These results include Gilbert–Varshamov-style existence bounds for unrestricted GB codes, upper bounds for parameters of GB codes with row weight w obtained by a map to codes local in $D\le w-1$ dimensions, and several explicit constructions. Other results include an exact expression for the distance in terms of an associated asymmetric quantum code, a matching set of upper and lower distance bounds for $w=4$ bicycle codes, and a lower bound which guarantees the existence of long GB codes with the distance $\mathcal{O}\left(n^{1/2}\right)$ for any fixed $w\ge 4$. We also studied the family of GB codes known to include codes with linear distances numerically, by exhaustively enumerating the corresponding binary GB codes with row weights w = 4, 6 and 8, for circulant sizes $\ell \le 217$ with primitive root 2. Although we are not able to distinguish conclusively between a power-law distance scaling $d=\mathcal{O}\left(n^{\alpha }\right)$ with $\alpha =1/2$ and $\alpha >1/2$, the results are consistent with square root distance scaling and a prefactor an increasing function of w.

The structure of the paper is as follows. First, in Section 2 we provide a brief summary of relevant facts from the theory of classical and quantum error-correcting codes, including some information on cyclic and quasi-cyclic codes. Analytical results are collected in Section 3. Section 3.1 provides general information about GB codes, Section 3.2 collects several lower (existence) bounds on distances of unrestricted GB codes based on the CSS map, Section 3.3 gives existence bounds based on the map to hypergraph-product and related codes, Section 3.4 presents a map of a weight-w GB code to a code local in $D\le w-1$ dimensions, and Section 3.5 gives tight bounds for weight-four GB codes. Numerical results are collected in Section 4, followed by a brief Conclusion in Section 5. Some of the formal proofs are collected in the Appendix A.

2. Relevant Facts and Notations

2.1. Cyclic and Quasi-Cyclic Codes

An ${[n,k,d]}_q$ code $\mathcal{C}$ linear over a finite (Galois) field ${\mathbb{F}}_q$, with q a power of a prime, is a k-dimensional subspace of ${\mathbb{F}}_q^n$, the linear space of all q-ary strings of length n. The distance d is the minimum Hamming weight of a non-zero vector in the code, or infinity for a trivial $k=0$ code which only contains the zero vector. A code ${\mathcal{C}}_G\equiv {\mathcal{C}}_H^{\perp }$ can be specified in terms of a generating matrix G whose rows form a basis of the code, or a parity check matrix H whose rows generate the space orthogonal to the code.

A cyclic code satisfies the additional condition that for every codeword $c\equiv (c_0,c_1,\dots ,c_{n-1})\in \mathcal{C}$, its cyclic shift $T_{n}c\equiv (c_{n-1},c_0,\dots ,c_{n-2})$ also gives a codeword, $T_{n}c\in \mathcal{C}$. Such a shift is conveniently represented as multiplication in the quotient polynomial ring $\mathcal{R}\equiv {\mathcal{R}}_{n,q}={\mathbb{F}}_q\left[x\right]/(x^n-1)$, namely, $T_{n}c\left(x\right)=xc\left(x\right)mod{x}^n-1$, where $c\left(x\right)=c_0+c_{1}x+\dots +c_{n-1}{x}^{n-1}$ has coefficients in ${\mathbb{F}}_q^n$. A cyclic code is an ideal of $\mathcal{R}$. In particular, this implies that any cyclic code can be generated as the set of all multiples in $\mathcal{R}$ of the canonical generator polynomial $g\left(x\right)$, where $g\left(x\right)$ is a factor of $x^n-1$, and any such factor generates a cyclic code.

Both a generator and a parity check matrix (with some redundant rows) of a cyclic code can be written as square circulant matrices. Algebra of circulant $n\times n$ matrices with coefficients in ${\mathbb{F}}_q$ is isomorphic to that of polynomials in $\mathcal{R}$. Indeed, given a polynomial $a\left(x\right)\in \mathcal{R}$, the corresponding circulant matrix,

$$A=\left(\begin{array}{cccc}{a}_0& a_{n-1}& \dots & a_1\\ a_1& a_0& \dots & a_2\\ ⋮& \ddots & \ddots & \ddots \\ a_n& \dots & a_1& a_0,\end{array}\right),$$

(1)

is conveniently written as the polynomial $A\equiv a\left(P\right)$ of the matrix $P\equiv P_n$, the $n\times n$ cyclic permutation matrix,

$$P=\left(\begin{array}{cccc}0& \dots & 0& 1\\ 1& & & 0\\ & \ddots & & ⋮\\ & & 1& 0.\end{array}\right).$$

(2)

We will consider vectors in ${\mathbb{F}}_q^n$ as columns, so that the product $Ab$ of a circulant matrix $A=a\left(P\right)$ and a vector b with the same coefficients as in the polynomial $b\left(x\right)\in \mathcal{R}$ corresponds to the product $a\left(x\right)b\left(x\right)mod{x}^n-1$. In particular, given a canonical generating polynomial $g\left(x\right)$, the corresponding check polynomial is $h\left(x\right)=(x^n-1)/g\left(x\right)$, and the cyclic code generated by $g\left(x\right)$ can be written as:

$${\mathcal{C}}_{g\left(x\right)}=\left\{c\left(x\right)\in \mathcal{R}:h\left(x\right)c\left(x\right)=0mod{x}^n-1\right\}.$$

(3)

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$. Rearranging the positions, we consider the defining permutation as $T_{\ell }$ applied in each of m consecutive blocks. As a result, a generator matrix of such a code can be written as an $r\times n$ block matrix formed by $\ell \times \ell$ circulant matrices. Generally, such block matrices will be written as matrices formed by the corresponding polynomials in ${\mathcal{R}}_{\ell ,q}$. The same applies to vectors, which will be written as columns of polynomials, with the exception of inline equations, where, e.g., a two-block vector in an index-2 QC code may be written as $\left[u\right(x),v(x\left)\right]$.

2.2. Quantum CSS Codes

A quantum Calderbank–Shor–Steane [25,26] (CSS) code $\mathcal{Q}$ with parameters ${\left[[n,k,d]\right]}_q$ over a Galois field ${\mathbb{F}}_q$ is isomorphic to a direct sum of an X- and a Z-like code,

$$\mathrm{CSS}(H_X,H_Z)={\mathcal{Q}}_X\oplus {\mathcal{Q}}_Z={\mathcal{C}}_{H_Z}^{\perp }/{\mathcal{C}}_{H_X}\oplus {\mathcal{C}}_{H_X}^{\perp }/{\mathcal{C}}_{H_Z},$$

(4)

where each term in the right-hand side (r.h.s.) is a quotient of two linear spaces in ${\mathbb{F}}_q^n$, and rows of the matrices $H_X$ and $H_Z$ must be orthogonal,

$$H_X{H}_Z^T=0.$$

(5)

Explicitly, e.g., elements of ${\mathcal{Q}}_X$ are equivalence classes of vectors orthogonal to the rows of the matrix $H_Z$, with any two vectors whose difference is a linear combination of the rows of $H_X$ identified. Vectors in the same class are called mutually degenerate, while vectors in the class of the zero vector are called trivial. The codes ${\mathcal{Q}}_X$ and ${\mathcal{Q}}_Z$ have $q^k$ degeneracy classes each, where

$$k=n-\mathrm{rank}{H}_X-\mathrm{rank}{H}_Z$$

(6)

is the quantum code dimension. The distance of the code is $d\equiv \min (d_X,d_Z)$, where the two CSS distances,

$$d_X=\underset{c\in {\mathcal{C}}_{H_Z}^{\perp }\setminus {\mathcal{C}}_{H_X}}{\min }\mathrm{wgt}c,d_Z=\underset{c\in {\mathcal{C}}_{H_X}^{\perp }\setminus {\mathcal{C}}_{H_Z}}{\min }\mathrm{wgt}c,$$

(7)

are the minimum weights of non-trivial vectors (any representative) in ${\mathcal{C}}_{H_Z}^{\perp }$ and ${\mathcal{C}}_{H_X}^{\perp }$, respectively.

Physically, a quantum code operates in a Hilbert space ${\mathcal{H}}_q^{\otimes n}$ associated with n quantum-mechanical systems, qudits, with q states each, and a well defined basis of X and Z operators acting in ${\mathcal{H}}_q^{\otimes n}$ [27]. Elements of the codes ${\mathcal{C}}_{H_X}$ and ${\mathcal{C}}_{H_Z}$ correspond to X- and Z- operators in the stabilizer group whose generators must be measured frequently during the operation of the code; generating matrices $H_X$ and $H_Z$ with smaller row weights result in codes which are easier to implement in practice. Orthogonality condition (5) ensures that the stabilizer group is abelian. Non-trivial vectors in ${\mathcal{Q}}_X$ and ${\mathcal{Q}}_Z$ correspond to X and Z logical operators, respectively. Codes with larger distances have logical operators which involve more qudits; such codes typically provide better protection.

3. Generalized Bicycle Codes

3.1. Definition and General Properties

Generalized bicycle (GB) code [15,20] is a version of the bicycle ansatz [21], a quantum CSS code constructed from a pair of equivalent index-two quasi-cyclic linear codes. Namely, given any pair of polynomials $a\left(x\right),b\left(x\right)\in F\left[x\right]$ with coefficients in a finite field $F\equiv {\mathbb{F}}_q$ and of degrees smaller than ℓ, the generalized bicycle code $\mathrm{GB}(a,b)$ of length $n=2\ell$ has CSS generator matrices specified in the block form,

$$H_X=(A|B),H_Z^T=\left(\begin{array}{c}\hfill B\\ \hfill -A\end{array}\right).$$

(8)

Here, $A=a\left(P\right)$ and $B=b\left(P\right)$ are q-ary $\ell \times \ell$ circulant matrices. Circulant matrices necessarily commute, which guarantees the CSS orthogonality condition (5). For notational convenience, we will use $\left[u\right(x),v(x\left)\right]$ to represent a Z-codeword c, a column vector whose components in the two blocks coincide with the coefficients of the two polynomials. The corresponding equation $H_{X}c=0$ is equivalent to $a\left(x\right)u\left(x\right)+b\left(x\right)v\left(x\right)=0mod{x}^{\ell }-1$.

With any code $\mathrm{GB}(a,b)$, there is an associated q-ary cyclic code ${\mathcal{C}}_{h\left(x\right)}^{\perp }\equiv {\mathcal{C}}_{g\left(x\right)}$ of length ℓ, with the check and generating polynomials,

$$h\left(x\right)\equiv gcd(a\left(x\right),b\left(x\right),x^{\ell }-1)\mathrm{and}g\left(x\right)\equiv \frac{x^{\ell }-1}{h\left(x\right)},$$

(9)

respectively. The number of qudits encoded in such a GB code is [20]:

$$k=2\mathrm{deg}h\left(x\right),$$

(10)

twice the dimension of the code ${\mathcal{C}}_{h\left(x\right)}^{\perp }\equiv {\mathcal{C}}_{g\left(x\right)}$.

It is easy to see that column and row permutations can be used to obtain the matrix $H_Z$ from $H_X$, up to a sign of some columns. Thus, the CSS distances (7) of any GB code are equal to each other and, respectively, to the code distance d. The calculation of the distance is simplified somewhat with the help of an auxiliary asymmetric bicycle (AB) code ${\mathcal{Q}}^{\prime }\equiv \mathrm{CSS}(H_X^{\prime },H_Z)$ where:

$$H_X^{\prime }=\left(A_1\mid B_1\right),A_1\equiv a_1\left(P\right),B_1\equiv b_1\left(P\right),$$

(11)

where $a_1\left(x\right)\equiv a\left(x\right)/gcd(a,b)$, $b_1\left(x\right)\equiv b\left(x\right)/gcd(a,b)$ are obtained by dividing the two polynomials by the common factor, and the matrix $H_Z$ is the same as in the original GB code, see Equation (8). The AB code encodes half as many qudits as the original GB code, $k^{\prime }=\mathrm{deg}h\left(x\right)$. The relation between the two codes follows from an explicit expression for the Z-codewords in the original code,

$$\left(\genfrac{}{}{0pt}{}{u\left(x\right)}{v\left(x\right)}\right)=\alpha \left(x\right)g\left(x\right)\left(\genfrac{}{}{0pt}{}{r_1\left(x\right)}{s_1\left(x\right)}\right)+\beta \left(x\right)\left(\genfrac{}{}{0pt}{}{b_1\left(x\right)}{-a_1\left(x\right)}\right)mod{x}^{\ell }-1,$$

(12)

where $r_1\left(x\right)$ and $s_1\left(x\right)$ are Bézout coefficients such that $a_1\left(x\right)r_1\left(x\right)+b_1\left(x\right)s_1\left(x\right)=1$ whose existence follows from $gcd(a_1,b_1)=1$, and, for a non-trivial codeword, at least one of $\alpha \left(x\right)$ and $\beta \left(x\right)$ should not be divisible by $h\left(x\right)$. Taken separately, these two conditions yield the sets of X- and Z-codewords of the AB code, respectively. This results in the following statement, the formal proof of which is given on page 15.

Statement1.

The distance of the code $\mathrm{GB}(a,b)$ is the same as that of the associated AB code $\mathrm{CSS}(H_X^{\prime },H_Z)$, $d=d^{\prime }=\min (d_X^{\prime },d_Z^{\prime })$.

In addition, the CSS distance $d_Z^{\prime }$ (and thus the distance d of the GB code) is bounded by the distance $d_g$ of the linear cyclic code ${\mathcal{C}}_{g\left(x\right)}$.

Statement2.

Let $d_g$ denote the distance of the ${\mathbb{F}}_q$-linear cyclic code with the generating polynomial $g\left(x\right)$, see Equation (9). Then the Z-distance of the q-ary AB code $\mathrm{CSS}(H_X^{\prime },H_Z)$ satisfies $d_Z^{\prime }\le d_g$.

The formal proof on page 15 amounts to a demonstration that for any non-zero code word $e\left(x\right)\in {\mathcal{C}}_{g\left(x\right)}$, either $\left[e\right(x),0]$ or $[0,e(x\left)\right]$ is a non-trivial Z-vector in the AB code.

We end this section with a short list of polynomial transformations which generate equivalent GB codes:

Statement3.

Two codes, $\mathrm{GB}(a,b)$ and $\mathrm{GB}(a^{\prime },b^{\prime })$, of the same size $n=2\ell$ are equivalent if

(i)

$a^{\prime }\left(x\right)=a\left(x^m\right)mod{x}^{\ell }-1$, $b^{\prime }\left(x\right)=b\left(x^m\right)mod{x}^{\ell }-1$ for some m mutually prime with ℓ, $gcd(m,\ell )=1$;

(ii)

$a^{\prime }\left(x\right)=b\left(x\right)$, $b^{\prime }\left(x\right)=a\left(x\right)$;

(iii)

$a^{\prime }\left(x\right)$ and $b^{\prime }\left(x\right)$ are the reciprocal polynomials of $a\left(x\right)$ and $b\left(x\right)$, respectively.

(iv)

$a^{\prime }\left(x\right)=\delta a\left(x\right)$, $b^{\prime }\left(x\right)=b\left(x\right)$, for some $0\ne \delta \in {\mathbb{F}}_q$.

(v)

$a^{\prime }\left(x\right)=f\left(x\right)a\left(x\right)$, $b^{\prime }\left(x\right)=f\left(x\right)b\left(x\right)$, for some polynomial $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ such that$gcd(f,x^{\ell }-1)=1$.

The first four transformations correspond to permutations preserving the circulant symmetry [28], while the last one may be useful for constructing LDPC codes, since minimum row weight does not necessarily correspond to minimum polynomial degrees.

While technically not an equivalence transformation, we should also mention here the case of polynomials commensurate with the circulant size ℓ, i.e., such that $h\left(x\right)=h_0\left(x^{\Delta }\right)$, where $\Delta >1$ is a factor of ℓ. A cyclic code whose check polynomial $h\left(x\right)$ is commensurate with ℓ is merely a direct sum of $\Delta$ disconnected cyclic codes, each equivalent to the code of length ${\ell }_0\equiv \ell /\Delta$ with the check polynomial $h_0\left(x\right)$. The same is true in the case of a code $\mathrm{GB}(a,b)$ whose defining polynomials have the same commensurability factor $\Delta$:

Statement4.

(Commensurate GB code) A code $\mathrm{GB}(a,b)$ with parameters ${\left[[2\ell ,k,d]\right]}_q$ and $a\left(x\right)=a_0\left(x^{\Delta }\right)$, $b\left(x\right)=b_0\left(x^{\Delta }\right)$, where $\ell ={\ell }_0\Delta$, is equivalent to a direct sum of $\Delta$ copies of the code $\mathrm{GB}(a_0,b_0)$ with parameters ${\left[[2{\ell }_0,k_0,d_0]\right]}_q$. In particular, $d=d_0$ and $k=k_0\Delta$.

A cyclic or GB code that is not commensurate is called incommensurate.

3.2. Bounds for GB Codes of Unrestricted Weight

Here we give several existence bounds for general (non-LDPC) GB codes, using the standard map [25,26,27] relating the parameters of a CSS code to those of the associated pair of classical ${\mathbb{F}}_q$-linear mutually dual-containing codes. In the case of the code $\mathrm{GB}(a,b)$, the two codes have double-circulant parity check matrices $H_X$ and $H_Z$ given in Equation (8). To be specific, we focus on the index-two QC code with the check matrix $H=H_X$, and denote such a code QC$(a,b)$.

Statement5.

(CSS map for GB codes [25,26,27]) Given the parameters ${[n_0=2\ell ,k_0,d_0]}_q$ of the classical linear code QC$(a,b)$, the quantum CSS code $\mathrm{GB}(a,b)$ has parameters ${\left[[2\ell ,2k_0-2\ell ,d]\right]}_q$, where $d\ge d_0$.

It is a classical result [29,30] that index-two QC codes include good codes with rate $1/2$ and asymptotically finite relative distances $d_0/n_0\to {\delta }_0>0$. However, the codes used in the proof have parity-check matrices in a systematic form with $A=I$; for such a self-dual (up to a permutation) index-two QC code Statement 5 gives a quantum code which encodes no qudits. A number of other lower bounds on the distances of QC codes have been constructed, in particular, a version [31] of the BCH bound (for a recent review, see Ref. [32]). However, none of these bounds gives a family of QC codes with $k_0-\ell =\mathcal{O}(\ell )$ and $d_0=\mathcal{O}\left(n\right)$. Indeed, by Statements 1 and 2, such a family of QC codes would imply that linear cyclic codes must be asymptotically good, a question which remains unresolved [33,34].

For these reasons here we list several partial results, which demonstrate the existence of QC codes with sublinear $k_0-\ell$ and distances scaling linearly, and of finite-rate QC codes with sublinear (power law) distances. The following bound is constructed using elementary arguments similar to those used in Ref. [35]:

Statement6.

Consider the code QC$(a,b)$ in the special case $a\left(x\right)=f\left(x\right)h\left(x\right)$, $b\left(x\right)=h\left(x\right)$, where for some polynomial $r\left(x\right)$, $gcd(f\left(x\right)-r\left(x\right),x^{\ell }-1)=p\left(x\right)$ is a factor of the generating polynomial, $g\left(x\right)=p\left(x\right)q\left(x\right)$. Then the distance of the QC code satisfies the bounds:

(a)

If$r\left(x\right)=0$,    $d_0\ge \min \left\{d\left[q\right],1+d\left[p\right]\right\}$;

(b)

Otherwise, if$gcd(r\left(x\right),x^{\ell }-1)=1$,

$$d_0\ge \min \left\{2d\left[q\right],d\left[p\right]/\mathrm{wgt}\left(r\right)\right\}.$$

Here, $h\left(x\right)$ and $g\left(x\right)$ are given by Equation (9), and $d\left[q\right]$ is the distance of the linear cyclic code generated by $q\left(x\right)$.

Unfortunately, the codes generated by $p\left(x\right)$ and $q\left(x\right)=g\left(x\right)/p\left(x\right)$, respectively, form a pair of dual-containing cyclic codes; it is well known [36] that the minimum of the two distances is bounded by $\mathcal{O}\left(\sqrt{\ell }\right)$, which limits the usability of the bound in Statement 6.

The following bound obtained with the help of a counting argument is a variant of Lemma 5 from Ref. [37] in application to GB codes:

Statement7.

Let $x^{\ell }-1=g\left(x\right)h\left(x\right)$ with $g\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ irreducible, and

$$d_{\mathrm{GV}}=\max d:\sum _{s=1}^{d-1}{(q-1)}^s\left[\left(\genfrac{}{}{0pt}{}{2\ell }{s}\right)-\left(\genfrac{}{}{0pt}{}{\ell }{s}\right)\right]<q^{\ell -\mathrm{deg}h}-1.$$

(13)

Then, there exists $f\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ such that the length-$2\ell$ code QC$(hf,h)$ has distance $d\ge \min (d\left[g\right],d_{\mathrm{GV}})$, where $d\left[g\right]$ is the distance of the cyclic code generated by $g\left(x\right)$.

The counting part of this bound asymptotically approaches from above the Gilbert–Varshamov (GV) bound [38,39] for linear q-ary codes with $k=\ell +\mathrm{deg}h$, which coincides with the GV bound [25] for q-ary CSS codes with $k=2\mathrm{deg}h$. Unfortunately, the requirement for $g\left(x\right)$ to be irreducible is very restrictive. Generally, since $x^{ab}-1$ has both $x^a-1$ and $x^b-1$ as factors, codes with ℓ prime have higher lower bounds on their relative distances under Statement 7. In particular, two well-known special cases correspond to $x^{\ell }-1$ having only two and three factors, respectively:

Example 1

(GB codes with linear distance). Let ℓ be such that ${\mathrm{ord}}_{\ell }\left(q\right)=\ell -1$, where ${\mathrm{ord}}_{\ell }\left(q\right)$ is the multiplicative order function of q modulo ℓ. This ensures that $x^{\ell }-1$ has only two irreducible factors in ${\mathbb{F}}_q\left[x\right]$, $h\left(x\right)\equiv 1-x$ and $g\left(x\right)=1+x+\dots +x^{\ell -1}$. Then there is a GB code with parameters ${\left[[2\ell ,2,d\ge d_{\mathrm{GV}}]\right]}_q$, where $d_{\mathrm{GV}}$ is given by Equation (13). For $q=2$ the corresponding set is [40] $\{3,5,11,13,19,29,37,53,59,61,67,83,101,107,131,139$, $149,163,173,179,181,197,\dots \}$, and, moreover, according to Artin’s primitive root conjecture, a finite fraction of all primes satisfies this condition for any $q>0$ which is not a perfect square [41]. Asymptotically, at $\ell \to \infty$, this bound on the relative distance coincides with the GV bound for rate-$1/2$ linear q-ary codes, e.g., ${\delta }_{\mathrm{GV}}\approx 0.1100$ for $q=2$.

Example 2

(GB codes with asymptotic rate $1/4$). For an odd prime ℓ let a prime p be a quadratic residue modulo ℓ, i.e., $p\equiv m^{2}mod\ell$ for some integer m. Then, $x^{\ell }-1$ has only three irreducible factors in ${\mathbb{F}}_p\left[x\right]$, and there is a quadratic-residue cyclic code ${[\ell ,(\ell +1)/2,d]}_p$ with $d\ge \sqrt{\ell }$ and an irreducible generator polynomial [28]. According to Statement 7, a prime-field GB code with parameters ${\left[[2\ell ,(\ell -1)/2,d\ge {\ell }^{1/2}]\right]}_p$ exists.

3.3. A Map to Hypergraph-Product and Related Codes

We would now like to focus on more practical GB codes with bounded-weight stabilizer generators. First, we construct an explicit map between a quantum hypergraph-product code [14] constructed from a pair of square circulant matrices of mutually prime dimensions $n_1$ and $n_1$, and a GB code with circulant size $\ell =n_1{n}_2$, see Figure 1.

Specifically, let $H_1=h_1\left(P_{n_1}\right)$ and $H_2\equiv h_2\left(P_{n_2}\right)$ be a pair of square circulant matrices of size $n_1$ and $n_2$, corresponding to polynomials $h_1\left(x\right)$ and $h_2\left(x\right)$ in ${\mathbb{F}}_q\left[x\right]$, respectively. Given the parameters ${[n_i,k_i,d_i]}_q$ for the two cyclic codes with the check polynomials $h_i$, $i\in \{1,2\}$, consider the hypergraph-product code with CSS generators in a block form written as Kronecker products:

$$\begin{array}{c}\hfill H_X=(I_1\otimes H_2,H_1\otimes I_2),H_Z^T=\left(\begin{array}{c}{H}_1\otimes I_2\\ -I_1\otimes H_2,\end{array}\right),\end{array}$$

(14)

where $I_i$ are the identity matrices of size $n_i$, $i\in \{1,2\}$. Such a code has the parameters [14,18].

$${\left[[2n_1{n}_2,2k_1{k}_2,\min (d_1,d_2)]\right]}_q$$

(15)

and can be put on an $n_1\times n_2$ square lattice with periodic boundary conditions as illustrated in Figure 1a, with the two blocks in Equation (14) corresponding to qubits on horizontal and vertical edges, respectively.

In the special case where $n_1$ and $n_2$ are mutually prime, $gcd(n_1,n_2)=1$, an equivalent GB code with circulant size $\ell =n_1{n}_2$, can be constructed from the polynomials,

$$a\left(x\right)=h_1\left(x^{n_2}\right),b\left(x\right)=h_2\left(x^{n_1}\right),$$

(16)

where the values of the circulant index,

$$t=n_{2}i+n_{1}j,mod\ell$$

(17)

are in a one-to-one correspondence with the positions $(i,j)$ on the $n_1\times n_2$ portion of the square lattice with periodic boundary conditions introduced by identifying any pair of points connected by periodicity vectors ${\overrightarrow{L}}_1=(n_1,0)$ and ${\overrightarrow{L}}_2=(0,n_2)$.

We should emphasize that in addition to being a one-to-one map, Equation (17) has the correct translation symmetry. Different GB codes can be also obtained using skewed periodicity vectors, e.g., ${\overrightarrow{L}}_1^{\prime }=(n_1,1)$ instead of ${\overrightarrow{L}}_1$, equivalent to the index map $t=i-n_{1}jmod\ell$. This map does not give identity transformation for the translation $i\to i+n_1$. Thus, we do not expect the corresponding code $\mathrm{GB}(a^{\prime },b^{\prime })$, $a^{\prime }\left(x\right)=h_1\left(x\right)$, $b^{\prime }\left(x\right)=h_2\left(x^{n_1}\right)$ to be equivalent to the original QHP code, see Figure 1b.

Generally, a quantum code on the edges of a square lattice with stabilizer generators similar to those of a QHP code but with periodicity vectors non-collinear with the axes is called a rotated QHP code [15], a code in a more general class of lifted-product codes [3].

Statement8.

An arbitrary GB code of length $2\ell$ is equivalent to a rotated QHP code with periodicity vectors ${\overrightarrow{L}}_1$ and ${\overrightarrow{L}}_2$ such that $|{\overrightarrow{L}}_1\times {\overrightarrow{L}}_2|=\ell$.

Proof. 

Indeed, given a decomposition $\ell =n_1{n}_2+\lambda$, where $n_1$ and ℓ are mutually prime, $gcd(n_1,\ell )=1$, consider a pair of vectors,

$${\overrightarrow{L}}_1=(n_1,1)\mathrm{and}{\overrightarrow{L}}_2=(\lambda ,n_2).$$

(18)

If we use these as periodicity vectors (i.e., identify any pair of points on the square lattice connected by one of these vectors), there are exactly $\ell =|{\overrightarrow{L}}_1\times {\overrightarrow{L}}_2|$ inequivalent points with a one-to-one map $t=i-n_{1}jmod\ell$ to a cycle ${\mathbb{Z}}_{\ell }$, see Figure 1b and Figure 2. Then, given the polynomials $h_1\left(x\right)$ and $h_2\left(x\right)$ which define the lattice layout of the stabilizer generators of a rotated QHP code with the chosen periodicity vectors, the polynomials defining the corresponding GB code are $a\left(x\right)=h_1\left(x\right)$ and $b\left(x\right)=h_2\left(x^{n_1}\right)$.

Conversely, let $m_1$ be a multiplicative inverse of $n_1$ modulo ℓ, $m_1{n}_1=1mod\ell$; its existence is guaranteed by the condition $gcd(n_1,\ell )=1$. Then, given the code $\mathrm{GB}(a,b)$, we recover the polynomials for the corresponding rotated-QHP code, $h_1\left(x\right)=a\left(x\right)$ and $h_2\left(x\right)=b\left(x^{m_1}\right)mod{x}^{\ell }-1$.    □

These maps show, in particular, that GB codes can be as good as QHP codes constructed from two square circulant matrices of mutually prime sizes. Given the explicit Equation (15) relating parameters of a QHP code with those of the two cyclic codes with parity-check polynomials $h_1\left(x\right)$ and $h_2\left(x\right)$, we obtain an existence for GB codes of finite rates and a power-law distance scaling as $\mathcal{O}(n^{1/2}/\mathrm{polylog}\left(n\right))$ or better. Indeed, the question of whether long linear cyclic codes are asymptotically good is still open, with only minor progress made in recent years [34,42,43]. In reality, the question is academic, since finite-length performance of cyclic codes is excellent, and already the BCH bound gives codes [44] with rate $R>0$ and $\delta \ge (2ln{R}^{-1})/logn$, while linear cyclic codes with $\delta >(1-2R)/\sqrt{2logn}$ can also be constructed [45].

From a practical viewpoint, more interesting are the bounds on parameters of LDPC GB codes with stabilizer generators of bounded weight. We construct such (upper) bounds in the next section with the help of general results by Bravyi, Poulin, and Terhal [46,47], by mapping a linear cyclic code with check polynomial of weight $w_1$ to a code local on a D-dimensional hyper-cubic lattice, with $D\le w_1$, and a GB code with row weight w to a quantum code local on a D-dimensional lattice, with $D\le w-1$.

3.4. A Map to a Code Local in D Dimensions

Let us first consider the case of a cyclic code of length ℓ with the parity check polynomial $h\left(x\right)\in {\mathbb{F}}_q\left[x\right]$ of a fixed weight w. Here we will not require that $h\left(x\right)$ be a factor of $x^{\ell }-1$, as such factors do not necessarily have minimal weights, but a q-ary polynomial such that the canonical check polynomial $h_1\left(x\right)\equiv gcd(h,x^{\ell }-1)$ be non-trivial, $k=\mathrm{deg}{h}_1\left(x\right)>0$.

The following is a generalization of Statement 8:

Statement9.

An incommensurate linear cyclic code of length ℓ with check polynomial $h\left(x\right)$ of weight w is equivalent to a code with all checks local on a hypercubic lattice of dimension $D\le w$, and $D\le w-1$ if ℓ is prime.

Proof. 

For a polynomial $h\left(x\right)$ with monomial degrees $0=t_0<t_1<\dots <t_{w-1}$, consider a set of w integer vectors in ${\mathbb{Z}}^w$, written as the rows of the lower-triangular matrix

$$M=\left(\begin{array}{cccc}\ell & & & \\ t_1& -1& & \\ t_2& & -1& \\ ⋮& & & \ddots \\ t_{w-1}& & & & -1\end{array}\right).$$

(19)

The determinant of M equals $\pm \ell$, and by the incommensurability condition, there exists a map from the chain $0\le t<\ell$ to the region in ${\mathbb{Z}}^w$ given by the inequalities $0\le x_i<{\ell }_i$, $0\le i<w$, where ${\ell }_0=t_1$, ${\ell }_i=\lceil t_{i+1}/t_i\rceil$ for $0<i<w-1$, and ${\ell }_{w-1}=\lceil \ell /t_{w-1}\rceil$. With these notations, the check polynomial becomes $a_0+a_{t_1}{x}_1+\dots a_{t_{w-1}}{x}_{w-1}$, i.e., the checks are one-local in the bulk of the region (with the structure as in quantum fractal codes [48,49]), and at most two-local near the region’s boundary.

When ℓ is a prime (or one of the original degrees $t_i\ne 0$ is mutually prime with ℓ), there exists $m\in {\mathbb{Z}}_{\ell }$ such that $m{t}_i=1mod\ell$, and $x^i\to x^{im}mod{x}^{\ell }-1$ gives an equivalent code, see Statement 3. The modified check polynomial $h^{\prime }\left(x\right)\equiv h\left(x^m\right)mod{x}^{\ell }-1$$h^{\prime }\left(x\right)$ has a degree-one monomial, and the region defined by the periodicity vectors (19) has $x_0=x_1$, thus $D\le w-1$.

The dimension can be additionally reduced if there is a simple relation between the monomial degrees, e.g., $t_3=t_1+t_2$, in which case the third axis can be skipped and the corresponding monomial written as $a_{t_3}{x}_1{x}_2$.    □

Given such a map to a code local in D dimensions, with the help of the general result in the appendix of Ref. [47], we immediately obtain:

Corollary 1.

Parameters ${[\ell ,k_1,d_1]}_q$ of any ${\mathbb{F}}_q$-linear cyclic code of length ℓ with the check polynomial of weight $w_1$ which is equivalent to a code local in $D_1\le w_1$ dimensions, satisfy $k_1{d}_1^{1/D_1}=\mathcal{O}(\ell )$.

The case of a GB code with polynomials $a\left(x\right)$ and $b\left(x\right)$ with the total weight w is considered similarly, except that each vertex of the hypercubic lattice must now contain two qudits, one from each block, and the maximum dimension is additionally reduced by one since both polynomials have zero-degree monomials. It is also easy to check that a local map for $H_X$ to ${\mathbb{Z}}^D$ automatically implies the locality of the corresponding $H_Z$. We have, combining the results from Refs. [46,47]:

Statement10.

An incommensurate GB code with row weight w and parameters ${\left[[n=2\ell ,k,d]\right]}_q$ is equivalent to a CSS code local in $D\le w-1$ dimensions ($D\le w-2$ if ℓ is prime). Its parameters satisfy the inequalities

$$d\le \mathcal{O}\left(n^{1-1/D}\right)\mathrm{and}k{d}^{2/(D-1)}\le \mathcal{O}\left(n\right).$$

Notice that the last equation implies that any GB code family with a fixed weight w has an asymptotically zero rate, since $k/n\to 0$ when the distance d becomes infinite.

3.5. Exact Bound for GB Codes of Weight Four

Here we consider in detail the special case of codes with $w=4$. According to Statement 10, any such code is equivalent to a code local in two dimensions. The case of $D=2$ is special, since Refs. [46,47] give asymptotically exact bounds for such codes.

A non-trivial GB code of weight $w=4$ can only be constructed when both $a\left(x\right)$ and $b\left(x\right)$ have equal weights. Moreover, weight-two polynomials of equal degrees, or a polynomial of degree $\ell /2$ with ℓ even, always give an empty code or a distance-two code. Therefore, for a non-trivial incommensurate GB code with distance $d\ge 3$, with the help of Statement 3, without restricting generality, we can request that the degrees $\alpha =\mathrm{deg}a\left(x\right)$ and $\beta =\mathrm{deg}b\left(x\right)$ satisfy $\alpha <\beta <\ell /2$, with $gcd(\alpha ,\beta ,\ell )=1$.

These additional properties guarantee that any pair of rows of a generator matrix $H_X$ (or $H_Z$) in Equation (8) intersect in at most one column, and any column has exactly two non-zero elements, as in a vertex-edge incidence matrix of a simple graph. The analogy can be made exact by considering a pair of binary matrices J, F constructed from $H_X$ and $H_Z$, respectively, by replacing any non-zero element with 1. The rows of the two matrices are necessarily orthogonal, $J{F}^T=0$ (over ${\mathbb{Z}}_2$). Thus, these matrices can be readily identified as a vertex-edge and a face-edge incidence matrices of a locally planar $(4,4)$ graph $\mathcal{G}$, i.e., with each vertex of $\mathcal{G}$ and the corresponding dual graph $\tilde{\mathcal{G}}$ of equal degree 4. Finally, it is also easy to see that the graph $\mathcal{G}$ is locally (i.e., as long as the current position does not close a circle $t\to t+\ell$) isomorphic to a square lattice, with the two blocks, respectively, corresponding to horizontal and vertical edges, and oriented in the direction of increasing index. Namely, any (local) sequence of horizontal $x_i=\pm 1$ and vertical $y_j=\pm 1$ steps, where the signs indicate the direction, arrives at the same final position as long as the total displacements $\sum x_i$ and $\sum y_j$ coincide. That is, the graph $\mathcal{G}$ is covered by the infinite square lattice graph $\mathcal{H}$, with the covering function $f:\mathcal{H}\to \mathcal{G}$ such that a path between a pair of vertices on $\mathcal{H}$ with the same covering map image corresponds to a non-trivial cycle on $\mathcal{G}$, or one or more “large” displacements $t\to t\pm \ell$ of the circulant index.

With such a map, it is evident that a non-trivial GB code of weight-four and distance $d\ge 3$ is a square-lattice surface code, with Z-codewords corresponding to homologically non-trivial cycles, with the homology fixed by the covering map f (see, e.g., Ref. [50]). Then, the distance $d_Z$ is the length of a shortest path connecting a pair of distinct vertices on $\mathcal{H}$ whose covering-map images coincide on $\mathcal{G}$.

To construct an actual distance bound, start with an arbitrary vertex $i\in {\mathcal{V}}_{\mathcal{H}}$ (where ${\mathcal{V}}_{\mathcal{H}}$ is the vertex set of $\mathcal{H}$), and consider a vertex-centered ball $B_r\left(i\right)$ on $\mathcal{H}$, a set of all vertices $j\in {\mathcal{V}}_{\mathcal{H}}$ such that the graph distance $d(i,j)\le r$, see Figure 3 (left). With the circulant size ℓ, the graph $\mathcal{G}$ has exactly ℓ vertices. Thus, if the size of the ball satisfies $|B_r\left(i\right)|>\ell$, the ball must include at least two equivalent vertices, which gives for the code distance, $d_Z\le 2r$, the diameter of the ball. The size of a ball on the square lattice is computed easily by summing the arithmetic sequence,

$$|B_r\left(i\right)|-1=4+8+\dots +4r=2r(r+1),$$

which gives the upper bound $d_Z\le 2r$ for any circulant size $\ell <1+2r(r+1)$. A similar calculation for an edge-centered ball on $\mathcal{H}$ gives an odd-valued upper bound $d_Z\le 2r+1$ for any $\ell <2{(r+1)}^2$, see Figure 3 (right). We rewrite these inequalities equivalently as lower bounds on the code length $n=2\ell$ for a given value of the distance $d=d_Z$:

Statement11.

Consider a weight-four GB code of an odd distance $d=2r+1$, then its length $n\ge 1+d^2$. For an even distance $d=2r$, the length $n\ge d^2$.

The argument above is valid for $d\ge 3$. We verified by exhaustive search that these inequalities are also valid for $d\in \{1,2\}$.

We notice that the inequalities in Statement 11 are sharp for surface codes. Namely, the odd-distance bound is reached by a family [51] of square lattice surface codes with periodicity vectors $(r+1,r)$ and $(-r,r+1)$ and parameters ${\left[[{(2r+1)}^2+1,2,2r+1]\right]}_q$, while the even-distance bound is achieved by the ${45}^{\circ }$-rotated surface codes [52]. These latter codes have periodicity vectors $(\pm r,\pm r)$ and parameters ${\left[[4r^2,2,2r]\right]}_q$. However, the corresponding translation group $\langle x,y\mid xy{x}^{-1}{y}^{-1}=x^r{y}^r=x^r{y}^{-r}=1\rangle$ is not cyclic for any $r>1$, which proves that there are no corresponding GB codes except for $r=1$, with parameters ${\left[[4,2,2]\right]}_q$.

The next-shortest family of even-distance surface codes has periodicity vectors $(r\pm 1,1\pm r)$ and parameters ${\left[[4r^2+4,2,2r]\right]}_q$, $r\in \mathbb{N}$; these have GB code representations when r is even, which requires the distance $2r$ be a multiple of four.

4. Numerical Results

To summarize our results so far, we expect the highest distances for GB codes encoding $k=2$ qudits, with $b\left(x\right)=1+x$ and $a\left(x\right)$ of even weight, which ensures the corresponding check polynomial (9) to be $h\left(x\right)=1+x$ for any $\ell \ge 2$. For the qubits (quantum codes over the binary field ${\mathbb{Z}}_2$), Example 1 based on Statement 7 shows that for prime circulant sizes ℓ with a primitive root 2, GB codes in this family exist with relative distance $d/n>{\delta }_{\mathrm{GV}}\approx 0.11$. However, the upper and lower bounds for the codes of row weight w (which corresponds to $\mathrm{wgt}\left(a\right)=w-2$) differ strongly for $w>4$. Namely, Statement 6, the map to QHP codes in Section 3.3, and several explicit $w=4$ code families in Section 3.5 agree that such codes with the distances $d>\mathcal{O}\left(n^{1/2}\right)$ scaling as a square root of the block size exist. On the other hand, the upper bound in Statement 10 for such codes suggests a power-law distance scaling with the exponent that may change with w, $d<\mathcal{O}\left(n^{\gamma }\right)$, where $\gamma =1-1/D$, with the effective dimension $D\left(w\right)\le w-2$ for a prime ℓ. The two bounds give the same exponent $\gamma =1/2$ only for $w=4$, while there is an interval of possible exponent values for $w>4$. Notice that any exponent, including ${\gamma }_{\min }=1/2$, may be consistent with the linear distance scaling at large w, if the corresponding prefactor $A\left(w\right)$ in the power-law $d\propto A\left(w\right)n^{\gamma }$ diverges at $w\to \infty$.

To address this issue, we set out to find largest-distance GB codes based on qubits and row weights $w\in \{4,6,8\}$, fixing $b\left(x\right)=1+x$. Namely, for every prime $\ell \le 227$ such that 2 is a primitive root, we calculated the maximum distance of GB codes over inequivalent polynomials $a\left(x\right)$ of weights 2, 4, and 6 (also, for every prime $\ell \le 127$ in the case of $\mathrm{wgt}a=4$, which did not substantially modify the results). We used equivalence maps (iii) and (v) [with $f\left(x\right)=x^s$, $s<\ell$] in Statement 3 to define a canonical form of $a\left(x\right)\in {\mathbb{F}}_2\left[x\right]$ of degree $\Delta$, with $a_0=a_{\Delta }=1$, and smallest alphabetically. In particular, this implies a smallest-degree polynomial in each equivalence class. When enumerating polynomials, we discarded any which did not coincide with the corresponding canonical form. Actual distance calculations were performed using the GAP package QDistRnd [53], with the help of the auxiliary AB code as in Statement 1, and only for those polynomials $a\left(x\right)=f\left(x\right)(1+x)$ with a sufficiently large $1+\mathrm{wgt}f$ (such an upper bound on the distance is a trivial consequence of Statement 3). The resulting data and the actual codes are available for download at the GitHub repository QEC-pages/GB-codes [54].

The computed distances d are plotted in Figure 4 as a function of the square root of the code length n, with different symbols and colors for GB codes of row weight 4, 6, and 8, as indicated in the figure caption. For clarity, for each w, only the codes with the smallest n giving the particular distance are shown on the plots. As expected, for each value of n, optimal codes with larger w show larger distances, with the $w=8$ codes giving approximately a factor of two distance improvement compared to codes with $w=4$ (equivalent to square lattice surface codes), e.g., $d_4=13$, $d_6=21$, and $d_8=23$ for $n=202$; the actual improvement factors are different for different values of n. We also notice that codes with n≳${10}^2$ are highly degenerate: their distances d are factor of two or larger than the corresponding stabilizer generator weights w.

Visually, the data in Figure 4 do not show much curvature, indicating distance scaling close to a square root. This is confirmed by fitting the data to a general three-parameter power-law form $d=a{n}^b+c$ (thick long dashes), and a similar two-parameter fit with a fixed power $b=1/2$ (thin lines): the corresponding lines lie more or less on top of each other, even though there is some upward curvature as indicated by the fitted exponents b whose values exceed $1/2$ for all three sets of data.

We should also notice that, in an attempt to capture the large-n features, only the data in the range $n>100$ were used in the fits. In fact, the three fitted values of the exponent b remain the same to three decimal places when the distance data for codes with $n\ge 25$ are included, while the square-root slope coefficients f show a minor reduction by around 5%.

5. Conclusions

To summarize, we have constructed several bounds on distances of generalized bicycle codes. Without a weight restriction, GB codes with linear in the block length n distances and encoding a sublinear number of qubits, GB codes of rate $1/4$ with the distance scaling as a square root of n, as well as codes with other rates and the distances $\mathcal{O}{(n/logn)}^{1/2}$, are known to exist.

More important practically are LDPC GB codes with a finite row weight w. Technically, these are zero-rate codes, since any such code is equivalent to a code local in a finite dimension D, see Statement 10. On the other hand, compared to the QHP and conventional toric codes, GB codes with row weights $w\le 8$ may have a factor-of-two larger distances with the same block sizes. While any power-law distance scaling is sufficient to maximize the lower bound on the fault-tolerant threshold for Pauli channel errors [9] and saturate the upper (percolation threshold) bound for erasure errors on graph-based codes [50], higher distances allow for better error-correction performance in the practically important regime of low block error rates. It remains to be seen whether the improved distances would be sufficient to offset the increased measurement complexity (compared to the surface codes) due to higher stabilizer generator weights and their non-locality.

The questions remaining for future studies include further numerical and analytical studies of GB codes encoding $k>2$ qubits. In addition to studying their parameters, of interest is the analysis of their performance in the fault-tolerant setting, as larger k values also increase the redundancy for minimum-weight stabilizer generators.

Second, the question of the distance scaling for GB codes with a bounded generator weight remains open. More generally, while quantum LDPC codes with power-law distance scaling higher than a square root of the block length have been constructed, it remains unknown whether local-in-a-finite-dimension $D>2$ codes can beat the square root distance bound (ignoring any logarithmic corrections).

Finally, it is the regular structure of finite-weight GB codes that makes it possible to represent them as codes that are local in a D-dimensional space. Perhaps other classes of matrices in the same CSS ansatz (8) based on two commuting square matrices would produce LDPC codes with better parameters.