Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products

Quantum low-density parity-check (qLDPC) codes provide one of the most promising means for achieving efficient quantum fault-tolerance. Such codes are defined to support error detection and correction via sparse queries (i.e. stabilizer measurements) to code states. Each such query involves, and can therefore only propagate errors across, a small number of code components. However, this qLDPC condition has proven difficult to achieve, and asymptotically optimal qLDPC codes were only recently constructed following a line of breakthrough works [16, 28, 8, 27, 22, 11]. The latter three of these works use nearly identical techniques, and still provide the only known asymptotically good qLDPC codes, meaning that the code dimension and distance scale linearly in the block length, and the stabilizers (i.e. parity checks) have constant weight. These codes have led to many applications, including to breakthrough results in both classical and quantum complexity theory [17, 1].

The works described above construct qLDPC codes by combining a pair of classical LDPC codes respecting a group action with an operation called a balanced (or lifted) product. However, this operation is fairly rigid, as it requires large, highly symmetric classical codes as inputs. The asymptotically good constructions [27, 22, 11] also require classical codes with a certain strong property called product-expansion [18], which is difficult to obtain in practice.

It has remained an open question to find alternative constructions of qLDPC codes with good parameters. Such alternative constructions may yield better practical parameters, have properties useful for other applications to complexity theory and fault-tolerant computation, or be of independent mathematical interest.

In this paper, we develop a new construction of qLDPC codes with close-to-linear dimension and distance. Our construction is inherently iterative: starting from a constant-sized code, we repeatedly apply homological products (i.e. tensor products of chain complexes) along with the stabilizer-weight-reduction transformation of [15] to produce a sequence of successively larger qLDPC codes. In contrast, all previous constructions of (even close to) linear distance qLDPC codes were based on a one-shot (non-iterative) application of a balanced product [28, 27, 22, 11].

The homological product is a well-known operation from homological algebra that generalizes the tensor product of classical codes. Such products can be viewed as a more basic version of balanced products, that do not require a group action. Homological products have long been used to construct qLDPC codes, notably including hypergraph product codes [32], which are simply homological products of 2-term chain complexes associated to classical codes. Hypergraph products of good classical LDPC codes give length-$N$ quantum LDPC codes of dimension $\mathrm{\Theta }(N)$ and distance $\mathrm{\Theta }(\sqrt{N})$ [32]; the well-known surface and Toric codes [21], which also have distance $\mathrm{\Theta }(\sqrt{N})$, can be viewed as hypergraph products of repetition codes. However, qLDPC codes previously constructed via homological products generally had distance at most $\tilde{O}(\sqrt{N})$; more technical details regarding this “$\sqrt{N}$ barrier” can be found in Section 3 below.

We circumvent this barrier by developing a new method of taking homological products that preserves almost-linear distance. Specifically, we observe that this barrier only applies to certain logical operators (i.e. codewords) within the code space. Our key idea is to therefore remove low-weight codewords by using subsystem codes, which only encode messages into a subspace of the entire logical code space. We show that appropriate subsystem codes of homological products have good distance; our proof builds on the techniques of [20]. We emphasize that the subsystem codes we consider remain truly LDPC, in that they have constant-weight stabilizers (see Remark 4).

We iteratively apply such homological products along with a stabilizer-weight-reduction transformation of [15] to obtain our main result, stated below:

The weight-reduction step in Theorem 1 is needed to keep the stabilizer weight constant in each iteration, as in general the stabilizer weight of a homological product code grows as the sum of the stabilizer weights of the input codes.

To prove Theorem 1, we set $𝒞$ to be a constant-sized quantum locally testable code (qLTC) such as one given by [12, 19]; such a qLTC (which we emphasize is just constant-sized) is needed for our homological product distance bound described above. We apply this bound to inductively show that the distance of each $Q_i$ remains close-to-linear (i.e. $\ge N_i^{1-ϵ}$) in the block length $N_i$.

Our iterative construction in Theorem 1 is reminiscent of a line of work in classical pseudorandomness, coding theory, and complexity theory, which iteratively builds larger objects with properties of interest from smaller or weaker ones. For instace, [6, 33] constructed classical locally testable codes by iterative tensoring of a small classical code; at a high level, Theorem 1 uses a related approach to construct qLDPC codes. Other notable iterative constructions in the literature include explicit spectral expanders from the zig-zag product [30], Dinur’s proof of the PCP theorem [10], and undirected connectivity in logarithmic space [29]. Theorem 1 can therefore be viewed as an analogue of these results for qLDPC codes. However, our construction does need to start with a strong constant-sized object $𝒞$, namely, a constant-sized qLTC with sufficiently good parameters. It is an interesting open question whether there exists an iterative construction with a weaker starting object.

Our bounds on the distance of homological product codes may also be of independent interest. At a foundational level, it is a mathematically interesting question to determine when homological product codes have large distance. Indeed, as quantum codes can be equivalently viewed as chain complexes or as topological spaces (see also [13]), this question can be phrased as asking how the systolic and cosystolic distance of a topological space (see the full version [14]) behave under topological products.

Furthermore, the classical analogue of homological product codes, namely tensor codes, are widely studied and used throughout classical coding theory. Better understanding quantum homological products may yield similar benefits for quantum error correction and beyond.

As mentioned above, many quantum code constructions based on homological products had distance at most $O(\sqrt{N})$. However, a few works have surpassed this barrier, though still with suboptimal parameters. Specifically, [7] showed that a length-$N$ “single-sector” variant of a homological product of two random quantum codes has distance $\mathrm{\Theta }(N)$ and stabilizer weight $\mathrm{\Theta }(\sqrt{N})$. [20] used homological products of chain complexes from certain high-dimensional expanders [25, 24] to obtain qLDPC codes with distance $\mathrm{\Theta }(\sqrt{N}\cdot \mathrm{poly}\log N)$ and constant stabilizer weight. [9] also showed how to obtain homological product codes with stabilizer weight $w$ and distance $\mathrm{\Theta }(\sqrt{N\cdot w})$.

In the remainder of this extended abstract, we provide a more detailed technical overview of our results. After presenting some necessary preliminaries in Section 2, we describe the main challenge in obtaining homological product codes of length $N$ and distance $\gg \sqrt{N}$ in Section 3, and then we explain our main idea for circumventing this barrier in Section 4. We then present our bound on the distance of homological product codes in Section 5, and show how we apply this bound in our main iterative code construction in Section 6. We provide some concluding remarks in Section 7. For the complete proofs, the reader is referred to the full version [14].

In this section, we briefly summarize some necessary background on quantum codes; more details can be found in the full version [14].

A length-$n$ quantum CSS code consists of a pair $Q=(Q_X,Q_Z)$ of vector spaces $Q_X,Q_Z\subseteq {𝔽}_q^n$ with $Q_X^{⟂}\subseteq Q_Z$, where $Q_X^{⟂}:=\{c\in {𝔽}_q^n:c\cdot x=0\forall x\in Q_X\}$. The code $Q$ has dimension $k=dim(Q_Z)-dim(Q_X^{⟂})$ and distance $d={\min }_{c\in (Q_X\setminus Q_Z^{⟂})\cup (Q_Z\setminus Q_X^{⟂})}|c|$. We summarize these parameters by saying that $Q$ is an ${[[n,k,d]]}_q$ code.

If $H_X\in {𝔽}_q^{m_X\times n},H_Z\in {𝔽}_q^{m_Z\times n}$ are parity-check matrices for $Q_X,Q_Z$ respectively, meaning that $Q_X=\ker H_X$ and $Q_Z=\ker Q_Z$, then the locality (i.e. stabilizer weight) $w$ of $Q$ equals the maximum weight of any row of $H_X$ or $H_Z$. We say $Q$ is locally testable with locality $w$ and soundness $\rho >0$ if for $\alpha \in \{X,Z\}$, it holds for every $e\in {𝔽}_q^n$ that $|H_{\alpha }e|/m_{\alpha }\ge \rho \cdot \mathrm{dis}(e,Q_{\alpha })/n$, where $\mathrm{dis}(e,Q_{\alpha })={\min }_{c\in Q_{\alpha }}|e-c|$. Thus local testability implies that the weight of an error on a code state can be estimated by simply measuring a random stabilizer.

In this paper, we primarily work with quantum codes using the language of chain complexes:

We typically work with chain complexes $𝒞$ that have $C_i=0$ for every $i$ outside of some sequence of $t$ consecutive integers; we then call $𝒞$ a $t$-term chain complex. For every level $i$ with $C_i\ne 0$, there is a naturally associated quantum CSS code $Q$ given by $Q_X=\ker {\delta }_i^{𝒞}$ and $Q_Z=\ker {\partial }_i^{𝒞}$. Conversely, given a length-$n$ CSS code $Q=(Q_X,Q_Z)$ with parity-check matrices $H_X\in {𝔽}_q^{m_X\times n},H_Z\in {𝔽}_q^{m_Z\times n}$, we can construct a 3-term chain complex $𝒞=({𝔽}_q^{m_X}\stackrel{H_X^{\top }}{\to }{𝔽}_q^n\stackrel{H_Z}{\to }{𝔽}_q^{m_Z})$ with associated quantum code $Q$ at the middle level. By definition, the maximum stabilizer weight of $Q$ is always at most the locality of $𝒞$. The dimension (i.e. number of logical qudits) of $Q$ equals $dim(H^i(𝒞))=dim(H_i(𝒞))$, and elements of $H^i(𝒞)$ and $H_i(𝒞)$ can be viewed as equivalence classes of $X$ and $Z$ logical operators, respectively, up to stabilizers. The distance of $Q$ equals the minimum Hamming weight of any representative of a nontrivial element of $H^i(𝒞)$ or $H_i(𝒞)$.

For $𝒞=𝒜\otimes ℬ$, the well-known Künneth formula provides an isomorphism

which for $a\in \ker ({\partial }_j^{𝒜})$ and $b\in \ker ({\partial }_{i-j}^{ℬ})$ is given by

The analogous result naturally also applies to cohomology.

One goal of this paper is to characterize conditions under which homological products preserve good distance (i.e. close to linear in the code length) of the associated quantum codes. However, there is a somewhat fundamental difficulty that arises when we work with finite-length complexes. Recall that for chain complexes $𝒜,ℬ$ and integers $i,j$, the Künneth formula implies that if $a\in \ker ({\partial }_j^{𝒜})\setminus \mathrm{im}({\partial }_{j+1}^{𝒜})$ and $b\in \ker ({\partial }_{i-j}^{ℬ})\setminus \mathrm{im}({\partial }_{i-j+1}^{ℬ})$, then $a\otimes b\in \ker ({\partial }_i^{𝒞})\setminus \mathrm{im}({\partial }_{i+1}^{𝒞})$. Therefore for instance consider the least $j\in \mathbb{Z}$ with $A_j\ne 0$, so that ${\partial }_j^{𝒜}=0$, and assume that $B_{i-j}\ne 0$ (this assumption is without loss of generality if we allow ourselves to swap $𝒜$ and $ℬ$, or instead consider their cochain complexes if necessary). Then unless ${\partial }_{j+1}^{𝒜}$ is surjective (which can be difficult to enforce in many settings), we must have some $a\in \ker ({\partial }_j^{𝒜})\setminus \mathrm{im}({\partial }_{j+1}^{𝒜})$ of Hamming weight $|a|=1$. Therefore $|a\otimes b|=|b|$, which (assuming $dim(A_j)\approx dim(B_{i-j})$) will be at most roughly the square root of the length of the the quantum code at level $i$ of $𝒞$.

This phenomenon was a major reason behind the “$\sqrt{N}$ barrier,” as prior to the work of [16] it was a longstanding open question to construct length-$N$ qLDPC codes with distance greater than $\tilde{\mathrm{\Theta }}(\sqrt{N})$. This barrier is perhaps easiest to understand with the homological product of two 2-term complexes $𝒜,ℬ$ (i.e. the “hypergraph product” of [32]), which can be visualized as a $2\times 2$ grid of vector spaces with maps between them:

The diagram above represents the 3-term chain complex $𝒞=𝒜\otimes ℬ$, where level $2$ is the top left corner $A_1\otimes B_1$, level $1$ contains the diagonal elements $A_0\otimes B_1\oplus A_1\otimes B_0$, and level $0$ is the bottom right corner $A_0\otimes B_0$. The boundary maps of $𝒞$ are simply the maps shown in the diagram. We let $Q$ be the quantum code at level $1$ of $𝒞$.

Assume for simplicity that all $A_0,A_1,B_0,B_1$ all have dimension $\mathrm{\Theta }(n)$. If $Q$ is a code of positive dimension, the Künneth formula implies that either ${\partial }_1^{𝒜}$ is not surjective and ${\partial }_1^{ℬ}$ is not injective, or vice versa; assume the former, as the argument for the latter is analogous. Then as described above, there is some $a\in A_0\setminus \mathrm{im}({\partial }^{𝒜})$ of weight $|a|=1$, and there is some $b\in \ker ({\partial }_1^{ℬ})$, so $a\otimes b\in \ker ({\partial }_1^{𝒞})\setminus \mathrm{im}({\partial }_2^{𝒞})=Q_Z\setminus Q_X^{⟂}$ has Hamming weight $|a\otimes b|=|b|\le O(n)$. But $Q$ is a code of length $N=\mathrm{\Theta }(n^2)$, and thus $Q$ has distance $D\le O(\sqrt{N})$.

Thus homological products of 2-term chain complexes cannot yield codes of good distance. We could consider using complexes $𝒜,ℬ$ with $t^{𝒜},t^{ℬ}\ge 2$ terms, and letting $Q$ be the quantum code at some level $i$ of the product complex $𝒞=𝒜\otimes ℬ$. However, a similar issue will arise. Specifically, the $2\times 2$ grid in (1) would be replaced by a $t^{𝒜}\times t^{ℬ}$ grid, but if we look at vector spaces around the edge of this grid, we may again find codewords in $\ker ({\partial }_i^{𝒞})\setminus \mathrm{im}({\partial }_{i+1}^{𝒞})=Q_Z\setminus Q_X^{⟂}$ of the form $a\otimes b$ with $|a|=1$, so that $|a\otimes b|=|b|\le O(n)=O(\sqrt{N})$.

[7] circumvented this barrier using single-sector chain complexes, which can be viewed as infinitely long complexes $\mathrm{\cdots }\stackrel{\partial }{\to }C\stackrel{\partial }{\to }C\stackrel{\partial }{\to }\mathrm{\cdots }$ with the same boundary map $\partial$ at every level. These complexes therefore do not have such low-distance codewords in vector spaces on the edges of the grid described above. However, single-sector complexes are somewhat restrictive, as they only have a single boundary map, and we were not able to obtain good bounds on the distance of single-sector homological products of qLDPC codes with constant locality; the products of [7] have locality $\mathrm{\Theta }(\sqrt{N})$. Instead, we took an alternative approach to circumventing this barrier, using subsystem codes as described below.

Our key observation for circumventing the $\sqrt{N}$ distance barrier described above is that it only applies to certain subspaces of the code space. For instance, consider a homological product of 3-term chain complexes $𝒜,ℬ$ as a $3\times 3$ grid:

Let $Q$ be the quantum code at the middle level ($i=2$) of the 5-term chain complex $𝒞=𝒜\otimes ℬ$, so that $Q_X,Q_Z$ are codes within the vector space $C_2=A_0\otimes B_2\oplus A_1\otimes B_1\oplus A_2\otimes B_0$ consisting of the three spaces in the bottom-left to top-right diagonal of the grid in (2). By the Künneth formula,

where for simplicity here we restrict attention to homology (i.e. $Z$ logical operators); the analogous reasoning also applies to cohomology (i.e. $X$ logical operators). The reasoning in Section 3 suggests that elements of $H_0(𝒜)\otimes H_2(ℬ)$ and $H_2(𝒜)\otimes H_0(ℬ)$ may have low-weight representatives. However, there is no apparent obstruction to having the homology classes associated to nonzero elements of $H_1(𝒜)\otimes H_1(ℬ)$ having only high-weight representatives (and analogously for cohomology). In the language of quantum codes, while the code $Q$ at level $2$ of $𝒞$ may have low-weight logical operators, we may hope to guarantee that the subspace of logical operators associated to the middle element of the grid in (2) all have high weight. In Theorem 5 below, we realize this hope for $𝒜,ℬ$ satisfying appropriate conditions.

This idea of a code where where we restrict attention to a subspace of logical operators has been studied in the quantum error correction literature, where it is called a subsystem code, defined below.

In Theorem 5 below, we characterize conditions under which good subsystem qLDPC code distance is preserved by homological products. Following the intuition described in Section 4 above, we restrict attention to logical operators in the middle terms of homological products of complexes of length $\ge 3$. In fact, we take the product of a 3-term complex $𝒜$ with a 5-term complex $ℬ$; for both complexes, we assume that the middle level is indexed $i=0$.

Theorem 5 provides a way to obtain good larger qLDPC codes from smaller ones. For instance, if $n_{}^{\prime }{}_{}{}^{𝒜},k^{𝒜},d^{𝒜}=\mathrm{\Theta }(n^{𝒜})$, $n_{}^{\prime }{}_{}{}^{ℬ},k^{ℬ},d^{ℬ},d_{}^{\prime }{}_{}{}^{ℬ}=\mathrm{\Theta }(n^{ℬ})$, and if $w^{𝒜},w^{ℬ},{\rho }^{ℬ}$ are all bounded by constants, so that $𝒜$ and $ℬ$ have asymptotically good parameters, then Theorem 5 provides a subsystem qLDPC code of length $N=\mathrm{\Theta }(n^{𝒜}{n}^{ℬ})$ associated to the product $𝒞=𝒜\otimes ℬ$ that also has asymptotically good parameters.

Under stronger conditions on $𝒜$ and $ℬ$, we can also bound the local testability of the product $𝒞$; see the full version [14] for details. A similar result also holds for complexes with arbitrarily many terms, though for simplicity in this paper we use the minimum length complexes that suffice for our purposes. As discussed below, a proof of a similar result for longer complexes can be found in [20].

The proof of Theorem 5 goes by a diagram-chasing argument inspired by [20]. Specifically, [20] proved a related result, which they applied to show good $Z$-distance (i.e. high weight for logical $Z$ operators) for quantum codes obtained as homological products of chain complexes from high-dimensional expanders [25, 24]. However, [20] did not use subsystem codes, and the $X$-distance of their product codes was only polylogarithmic in the block length.²²2Such poor $X$-distance was in part due to the fact that the cochain complexes they considered from high-dimensional expanders have much better distance and expansion properties than the associated chain complexes. However, as [20] did not use subsystem codes, it seems difficult to obtain product codes with close-to-linear distance from their results, even when applied to products of different complexes. Thus after applying a distance-balancing procedure, [20] obtained qLDPC codes of distance $\sqrt{N}\cdot \mathrm{poly}(\log N)$, which only barely surpasses the $\sqrt{N}$ barrier.

If both $𝒜$ and $ℬ$ have associated codes with large distance, then Theorem 5 yields a large distance bound on the subsystem product code whenever $𝒜$ has good (small) locality $w^{𝒜}$ and $ℬ$ has good (large) soundness ${\rho }^{ℬ}$. At a high level, our proof of Theorem 5 (inspired by [20]) argues that by the Künneth formula, codewords of the product code can be expressed as tensor products of codewords of $𝒜$ and $ℬ$, plus elements in the image of the boundary map ${\partial }^{𝒞}$ (i.e. stabilizers). Classical tensor product codes have good distance, so we just need to argue that the distance is not significantly reduced by adding in elements in $\mathrm{im}({\partial }^{𝒞})$. This final step goes by a diagram-chasing argument that bounds the loss in distance in terms of $w^{𝒜}$ and ${\rho }^{ℬ}$; the reader is referred to the full version [14] for more details.

In Theorem 6 below, we iteratively apply Theorem 5 starting with a constant-sized chain complex from [12, 19] to obtain an infinite family of qLDPC codes with close-to-linear dimension and distance. Below, we view qLDPC codes $Q$ interchangeably with their associated 3-term chain complexes, as described previously.

The weight-reduction transformation of [15] provides a means of reducing the locality of a CSS code from a given value $w$ to an absolute constant $O(1)$, at the cost of increasing the code length and decreasing the distance by a factor of $\mathrm{poly}(w)$. We apply this transformation after every application of the homological product because the distance bound in Theorem 5 decays with the locality of $𝒜$. Therefore by maintaining constant locality, we are able to inductively maintain a good distance bound in each iteration.

The starting complex in Theorem 6 is a constant-sized instance of the construction of [12, 19], which provides chain complexes whose associated CSS codes are quantum LTCs with nearly optimal asymptotic parameters. As Theorem 6 only needs a constant-sized such starting object $𝒞$, it is an interesting question to instantiate it with alternative constructions.

In this paper, we provide a new construction of qLDPC codes of almost linear distance. Constructions of such objects were out of reach of known techniques until the breakthrough line of work [16, 28, 8, 27, 22, 11] that developed over the past few years.³³3We remark that [15] applies locality reduction to construct qLDPC codes of length $N$ and distance $\tilde{\mathrm{\Omega }}(N^{2/3})$. Therefore these codes surpass the “$\tilde{O}(\sqrt{N})$ distance barrier” (see Section 3), but do not approach linear distance. The constructions from these works are based on a sort of balanced product (also called a lifted product) that applies to only certain codes with a particular group symmetry. In contrast, our constructions are based on iterative applications of the more basic homological product, which is generically defined with no group symmetries. Indeed, the classical analogue of our construction, namely iterated tensor products of classical codes, immediately gives classical LDPC codes of close-to-linear distance, and has also been shown to yield properties such as local testability [6, 33].

It is perhaps surprising that we are able to obtain similar parameters as in the classical case with just homological/tensor products, especially given that for many years, qLDPC codes constructed with similar techniques were not able to achieve distance greater than $\tilde{O}(\sqrt{N})$ (see Section 3). We obtain our distance bounds by combining conceptual insights (e.g. the use of subsystem codes) with certain strong properties of the base code in our iterative construction. Specifically, we assume that the starting code is a constant-sized qLTC. Currently, the only known appropriate such qLTCs, given by [12, 19], are themselves based on balanced products following the line of work described above. We leave it as an interesting direction for future work to find alternative instantiations of the starting code. We also emphasize that the iterative nature of our construction may be of independent interest. Indeed, iterative constructions in the past have led to a number of breakthrough results in pseudorandomness, complexity theory, and coding theory (e.g. [30, 10, 29, 5, 31]), including some cases ([30], [10]) where algebraic constructions ([23, 26], [3, 2]) were previously known.