Code construction
Table of Contents
We begin with a formal definition of BB codes. Let I_{ℓ} and S_{ℓ} be the identity matrix and the cyclic shift matrix of size ℓ × ℓ respectively. The ith row of S_{ℓ} has a single nonzero entry equal to one at the column \(i\,+\,1\,({\rm{mod}}\,\,{\ell })\). For example,
$${S}_{2}=\left[\begin{array}{cc}0 & 1\\ 1 & 0\end{array}\right]\quad {\rm{and}}\quad {S}_{3}=\left[\begin{array}{ccc}0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0\end{array}\right].$$
Consider matrices
$$x={S}_{{\ell }}\otimes {I}_{m}\quad {\rm{and}}\quad y={I}_{{\ell }}\otimes {S}_{m}.$$
Note that xy = yx, x^{T}x = y^{T}y = I_{ℓm}, and x^{ℓ} = y^{m} = I_{ℓm}. A BB code is defined by a pair of matrices
$$A={A}_{1}+{A}_{2}+{A}_{3}\quad {\rm{and}}\quad B={B}_{1}+{B}_{2}+{B}_{3}$$
(1)
where each matrix A_{i} and B_{j} is a power of x or y. Here and below the addition and multiplication of binary matrices is performed modulo two, unless stated otherwise. Thus, we also assume the A_{i} are distinct and the B_{j} are distinct to avoid cancellation of terms. For example, one could choose A = x^{3} + y + y^{2} and B = y^{3} + x + x^{2}. Note that A and B have exactly three nonzero entries in each row and each column. Furthermore, AB = BA because xy = yx. The above data defines a BB quantum code denoted QC(A, B) with length n = 2ℓm and check matrices
$${H}^{X}=\left[A B\right]\quad {\rm{and}}\quad {H}^{Z}=\left[{B}^{T} {A}^{T}\right].$$
(2)
Here the vertical bar indicates stacking matrices horizontally and T stands for the matrix transposition. Both matrices H^{X} and H^{Z} have size (n/2) × n. Each row \({\bf{v}}\,\in \,{{\mathbb{F}}}_{2}^{n}\) of H^{X} defines an Xtype check operator \(X({\bf{v}})={\prod }_{j=1}^{n}{X}_{j}^{{{\bf{v}}}_{j}}\). Each row \({\bf{v}}\,\in \,{{\mathbb{F}}}_{2}^{n}\) of H^{Z} defines a Ztype check operator \(Z({\bf{v}})={\prod }_{j=1}^{n}{Z}_{j}^{{{\bf{v}}}_{j}}\). Any X and Z checks commute as they overlap on even number of qubits (note that \({H}^{X}{({H}^{Z})}^{T}=AB+BA=0\,({\rm{mod}}\,\,2)\)). By construction, the code QC(A, B) has weight6 check operators and each qubit participates in six checks (three Xtype plus three Ztype checks). Accordingly, the code QC(A, B) has a degree6 Tanner graph. One can view the matrices A and B as bivariate polynomials over the variables x and y. Specializing BB codes to the case m = 1 and B = A^{T} gives the original bicycle codes^{41} based on univariate polynomials. Likewise, BB codes are a specialization of the generalized bicycle codes^{35}, twoblock groupbased codes^{37,42} and polynomialbased codes^{59}. Given a binary matrix M, let \(\ker (M)\) be its nullspace spanned by all binary vectors v such that \(M{\bf{v}}=0\,({\rm{mod}}\,\,2)\). Let rs(M) be the row space of M spanned by rows of M.
Lemma 1
The code QC(A, B) has parameters [[n, k, d]], where
$$\begin{array}{c}n=2{\ell }m,\,k=2\times \dim (\ker (A)\cap \ker (B))\,{\rm{a}}{\rm{n}}{\rm{d}}\,d\\ \,\,=\,\min \{{\bf{v}}:{\bf{v}}\in \ker ({H}^{X}){\rm{\backslash }}{\mathsf{r}}{\mathsf{s}}({H}^{Z})\}.\end{array}$$
The code offers equal distance for Xtype and Ztype errors.
The proof, relying on elementary linear algebra, is deferred to the Supplementary Information. Extended Data Table 1 describes the polynomials A and B that give rise to examples of highrate, highdistance BB codes found by a numerical search. This includes all codes from Table 1 and two examples of higher distance codes. To the best of our knowledge, all these examples are new. The code [[360, 12, ≤24]] improves on a code [[882, 24, ≤24]] with weight6 checks found by Panteleev and Kalachev in ref. ^{36} (assuming that our distance upper bound is tight). Indeed, taking two independent copies of the 360qubit code gives parameters [[720, 24, ≤24]]. Appendix C in ref. ^{36} also describes a code [[126, 12, 10]] that has parameters similar to ours. This code has a form QC(A, B) with A = 1 + x^{43} + x^{37}, B = 1 + x^{59} + x^{31}, ℓ = 63 and m = 1. We note that the recent work by Wang, Lin and Pryadko^{37,38} described examples of groupbased codes closely related to the codes considered here. Some of the groupbased codes with weight8 checks found in ref. ^{37} outperform our BB codes with weight6 checks in terms of the parameters n, k, d. It remains to be seen whether groupbased codes can achieve a similar or better level of error suppression for the circuitbased noise model.
In the following, we partition the set of data qubits as [n] = LR, where L ≔ q(L) and R ≔ q(R) are the left and right blocks of n/2 = ℓm data qubits. Then, data qubits L and R and checks X and Z may each be labelled by integers \({{\mathbb{Z}}}_{{\ell }m}=\{0,1,\ldots ,{\ell }m1\}\), which are indices into the matrices A, B. Alternatively, qubits and checks can be labelled by monomials from \({\mathcal{M}}=\{1,y,\ldots ,{y}^{m1},x,xy,\ldots ,x{y}^{m1},\ldots ,{x}^{{\ell }1}{y}^{m1}\}\) in this order, so that \(i\in {{\mathbb{Z}}}_{{\ell }m}\) labels the same qubit or check as \({x}^{{a}_{i}}{y}^{im{a}_{i}}\) for a_{i} = floor(i/m). Using the monomial labelling, L data qubit \(\alpha \in {\mathcal{M}}\) is part of X checks \({A}_{i}^{T}\alpha \) and Z checks B_{i}α for i = 1, 2, 3. Similarly, R data qubit \(\beta \in {\mathcal{M}}\) is part of X checks \({B}_{i}^{T}\beta \) and Z checks A_{i}β. A unified notation assigns each qubit or check a label q(T, α) where T ∈ {L, R, X, Z} denotes its type and \(\alpha \in {\mathcal{M}}\) its monomial label. (The monomial notations should not be confused with the matrix notations used earlier in this section. For example, multiplication of monomials such as B_{i}α is different from multiplying a vector α by a matrix B_{i}).
One drawback of highrate LDPC codes is that their Tanner graphs may not be locally embeddable into the 2D grid^{60,61}. This poses a challenge for hardware implementation with superconducting qubits coupled by microwave resonators. A useful verylargescale integration (VLSI) design concept is graph thickness, see refs. ^{29,62} for details. A graph G = (V, E) is said to have thickness θ if one can partition its set of edges E into disjoint union of θ sets E_{1}⊔E_{2}⊔…⊔E_{θ} = E such that each subgraph (V, E_{i}) is planar. Informally, a graph with thickness θ can be viewed as a vertical stack of θ planar graphs. Qubit connectivity described by a planar graph (thickness θ = 1) is the simplest one from hardware perspective because the couplers do not cross.
Here we show that the Tanner graph of any BB code has thickness2. This result may be surprising as it is known that a general degree6 graph can have thickness θ = 3 (ref. ^{62}). Graphs with thickness θ = 2 might still be implementable with superconducting qubits because two planar layers of couplers and their control lines can be attached to the top and the bottom side of the chip hosting qubits.
Lemma 2
The Tanner graph G of the code QC(A, B) has thickness θ ≤ 2. A decomposition of G into two planar layers can be computed in time O(n). Each planar layer of G is a degree3 graph.
Proof
Let G = (V, E) be the Tanner graph. Partition G into subgraphs G_{A} = (V, E_{A}) and G_{B} = (V, E_{B}) that describe CSS codes with check matrices
$$\,\mathrm{Tanner\; graph}\,\,{G}_{{\rm{A}}}:\quad {H}_{A}^{X}=[{A}_{2}+{A}_{3} {B}_{3}]\quad {\rm{and}}\quad {H}_{A}^{Z}=[{B}_{3}^{T} {A}_{2}^{T}+{A}_{3}^{T}]$$
(3)
$$\,\mathrm{Tanner\; graph}\,\,{G}_{{\rm{B}}}:\quad {H}_{B}^{X}=[{A}_{1} {B}_{1}+{B}_{2}]\quad {\rm{and}}\quad {H}_{B}^{Z}=[{B}_{1}^{T}+{B}_{2}^{T} {A}_{1}^{T}].$$
(4)
As A = A_{1} + A_{2} + A_{3} and B = B_{1} + B_{2} + B_{3}, every edge of G appears either in G_{A} or G_{B}, in which the two subgraphs are named by whether they contain more A_{i} edges or more B_{i} edges. Then G_{A} and G_{B} are regular degree3 graphs (because A_{i} and B_{j} are permutation matrices).
Consider the graph G_{A}. Each Xcheck vertex is connected to a pair of data vertices i_{1}, i_{2} ∈ L by means of the matrices A_{2}, A_{3} and a data vertex i_{3} ∈ R by means of the matrix B_{3}. Each Zcheck vertex is connected to a pair of data vertices i_{1}, i_{2} ∈ R by means of the matrices \({A}_{2}^{T},{A}_{3}^{T}\) and a data vertex i_{3} ∈ L by means of the matrix \({B}_{3}^{T}\).
We claim that each connected component of G_{A} can be represented by a ‘wheel graph’ illustrated in Extended Data Fig. 1. A wheel graph consists of two disjoint cycles of the same length p interconnected by p radial edges. The outer cycle alternates between Xcheck and L data vertices.
Edges of the outer cycle alternate between those generated by A_{3} (as one moves from a check to a data vertex) and \({A}_{2}^{T}\) (as one moves from a data to a check vertex). The length of the outer cycle is equal to the order of the matrix \({A}_{3}{A}_{2}^{T}\), that is, the smallest integer Ord such that \({({A}_{3}{A}_{2}^{T})}^{{\rm{O}}{\rm{r}}{\rm{d}}}={I}_{{\ell }m}\). For example, consider the code [[144, 12, 12]] from Extended Data Table 1. Then A = x^{3} + y + y^{2}, A_{2} = y and A_{3} = y^{2}. Thus \({A}_{3}{A}_{2}^{T}={y}^{2}{y}^{1}=y\) that has order m = 6. The inner cycle of a wheel graph alternates between Zcheck and Rdata vertices.
Edges of the inner cycle alternate between those generated by \({A}_{3}^{T}\) (as one moves from a check to a data vertex) and A_{2} (as one moves from a data to a check vertex). The length of the inner cycle is equal to the order of the matrix \({A}_{3}^{T}{A}_{2}\) that is the transpose of \({A}_{3}{A}_{2}^{T}\) considered earlier. Thus both inner and outer cycles have the same length m. The two cycles are interconnected by m radial edges as shown in Extended Data Fig. 1a. Radial edges are generated by the matrix B_{3}, as one moves towards the centre of the wheel. The wheel graph contains four cycles generated by tuples of edges \(({B}_{3},{A}_{2},{B}_{3}^{T},{A}_{2}^{T})\) and \(({B}_{3}^{T},{A}_{3},{B}_{3},{A}_{3}^{T})\). Commutativity between A_{i} and B_{j} ensures that traversing any of these four cycles implements the identity matrix, that is, the graph is well defined. Clearly, the wheel graph is planar. As G_{A} is a disjoint union of wheel graphs, G_{A} is planar. The same argument shows that G_{B} is planar (Extended Data Fig. 1b). The visualization of the [[144, 12, 12]] code in Fig. 1b shows the edges of G_{A} and G_{B} as dashed ‘A’ edges and solid ‘B’ edges, respectively.
We leave optimization of the code layout satisfying specific hardware constraints for future work. For now, it is sufficient to note that any planar graph admits a planar embedding without edge crossings for any prescribed vertex locations, see for example theorem 1 in ref. ^{63}. Moreover, this embedding can be efficiently computed^{63}. Accordingly, both planar layers in the thickness2 decomposition of the Tanner graph can be simultaneously embedded into a plane for any fixed vertex locations such that edges do not cross within each layer.
Another example of thickness2 graphs in the literature is the bilayer architecture of ref. ^{64}. This connectivity is described by two planar graphs with additional transversal edges between them. It can be verified that bilayer graphs are thickness2 by placing transversally connected nodes next to each other in one of the two planes and placing the transversal edges in that same plane.
The definition of code QC(A, B) does not guarantee that its Tanner graph is connected. Some choices of A and B lead to a code that is actually several separable code blocks. This manifests as a Tanner graph with several connected components. For instance, although all codes in Extended Data Table 1 are connected, taking any of them with even ℓ and replacing every instance of x with x^{2} creates a code with two connected components.
Lemma 3
The Tanner graph of the code QC(A, B) is connected if and only if \(S=\{{A}_{i}{A}_{j}^{T}:i,j\in \{1,2,3\}\}\cup \{{B}_{i}{B}_{j}^{T}:i,j\in \{1,2,3\}\}\) generates the group \({\mathcal{M}}\). The number of connected components in the Tanner graph is ℓm/∣⟨S⟩∣, and all components are graph isomorphic to one another.
Proof
Extended Data Fig. 2 is helpful for following the arguments in this proof. We start by proving the reverse implication of the first statement. Note that there is a length 2 path in the Tanner graph from L qubit \(\alpha \in {\mathcal{M}}\) to L qubit \({A}_{i}{A}_{j}^{T}\alpha \) and another length 2 path to L qubit \({B}_{i}{B}_{j}^{T}\alpha \). These travel through X and Z checks, respectively. Thus, because the \({A}_{i}{A}_{j}^{T}\) and \({B}_{i}{B}_{j}^{T}\) generate \({\mathcal{M}}\), there is some path from α to any other L qubit β. A similar argument shows existence of a path connecting any pair of R qubits. As each X check and each Z check are connected to at least one L qubit and at least one R qubit, this implies that the entire Tanner graph is connected. The forward implication of the first statement follows after noticing that, for all T ∈ {L, R, X, Z}, the path from a type T node to any other T node is necessarily described as a product of elements from S. Connectivity of the Tanner graph implies the existence of all such paths, and so S must generate \({\mathcal{M}}\).
If S does not generate \({\mathcal{M}}\), it necessarily generates a subgroup ⟨S⟩ and nodes in connected components of the Tanner graph are labelled by elements of the cosets of this subgroup. This implies the theorem’s second statement.
For the next part, we establish some terminology. A spanning subgraph of a graph G is a subgraph containing all the vertices of G. Also, the undirected Cayley graph of a finite Abelian group \({\mathcal{G}}\) (with identity element 0) generated by set \(S\subset {\mathcal{G}}\) is the graph with vertex set \({\mathcal{G}}\) and undirected edges (g, g + s) for all \(g\in {\mathcal{G}}\) and all s ∈ S, s ≠ 0. We say the Cayley graph of \({{\mathbb{Z}}}_{a}\times {{\mathbb{Z}}}_{b}\) when we mean the Cayley graph of \({{\mathbb{Z}}}_{a}\times {{\mathbb{Z}}}_{b}\) generated by {(1, 0), (0, 1)}. The order ord(g) of an element g in a multiplicative group is the smallest positive integer such that g^{ord(g)} = 1.
Definition 1
Code QC(A, B) is said to have a toric layout if its Tanner graph has a spanning subgraph isomorphic to the Cayley graph of \({{\mathbb{Z}}}_{2\mu }\times {{\mathbb{Z}}}_{2\lambda }\) for some integers μ and λ.
Note that only codes with connected Tanner graphs can have a toric layout according to this definition. An example toric layout is depicted in Fig. 1b.
Lemma 4
A code QC(A, B) has a toric layout if there exist i, j, g, h ∈ {1, 2, 3} such that

1.
\(\langle {A}_{i}{A}_{j}^{T}\,,{B}_{g}{B}_{h}^{T}\rangle ={\mathcal{M}}\) and

2.
\({\rm{ord}}({A}_{i}{A}_{j}^{T}\,){\rm{ord}}({B}_{g}{B}_{h}^{T})={\ell }m\).
Proof
We let \(\mu ={\rm{ord}}({A}_{i}{A}_{j}^{T}\,)\) and \(\lambda ={\rm{ord}}({B}_{g}{B}_{h}^{T})\). We associate qubits and checks in the Tanner graph of QC(A, B) with elements of \({\mathcal{G}}={{\mathbb{Z}}}_{2\mu }\times {{\mathbb{Z}}}_{2\lambda }\). For L qubit with label \(\alpha \in {\mathcal{M}}\), because of (1), there is \((a,b)\in {{\mathbb{Z}}}_{\mu }\times {{\mathbb{Z}}}_{\lambda }\) such that \(\alpha ={({A}_{i}{A}_{j}^{T})}^{a}{({B}_{g}{B}_{h}^{T})}^{b}\). Because of (2) and the pigeonhole principle, this choice of (a, b) is unique. We associate L qubit α with \((2a,2b)\in {\mathcal{G}}\). Similarly, an R qubit with label \(\alpha {A}_{j}^{T}{B}_{g}\) is associated with \((2a+1,2b+1)\in {\mathcal{G}}\), Xcheck \(\alpha {A}_{j}^{T}\) with (2a + 1, 2b) and Zcheck αB_{g} with (2a, 2b + 1). Edges in the Tanner graph \({A}_{i}\,,{A}_{j}^{T}\,,{B}_{g}\) and \({B}_{h}^{T}\) can now be drawn as in Extended Data Fig. 2b and correspond to edges in the Cayley graph of \({\mathcal{G}}\). For instance, to get from (2a + 1, 2b + 1), an R qubit, to (2a + 2, 2b + 1), a Z check, we apply A_{i}, taking R qubit labelled \(\alpha {A}_{j}^{T}{B}_{g}\) to the Z check labelled \((\alpha {A}_{j}^{T}{B}_{g}){A}_{i}=\alpha ({A}_{i}{A}_{j}^{T}\,){B}_{g}\).
All codes in Extended Data Table 1 have a toric layout with μ = m and λ = ℓ. Most of these codes satisfy Lemma 4 with i = g = 2 and j = h = 3. The exception is the [[90, 8, 10]] code, for which we can take i = 2, g = 1 and j = h = 3.
However, we also note two interesting cases. First, there are codes with connected Tanner graphs that do not satisfy the conditions for a toric layout given in Lemma 4. One example of such a code is QC(A, B) with ℓ, m = 28, 14, A = x^{26} + y^{6} + y^{8} and B = y^{7} + x^{9} + x^{20} that has parameters [[784, 24, ≤24]]. Second, for a code satisfying the conditions of Lemma 4, it need not be the case that the set \(\{{\rm{ord}}({A}_{i}{A}_{j}^{T}\,),{\rm{ord}}({B}_{g}{B}_{h}^{T})\}\) and the set {ℓ, m} are equal. For example, the [[432, 4, ≤22]] code with ℓ, m = 18, 12 and A = x + y^{11} + y^{3}, B = y^{2} + x^{15} + x only satisfies Lemma 4 with μ, λ = 36, 6 (take i = g = 1 and j = h = 2 for instance).
Summary of other capabilities
For the remainder of this section, we summarize important details of additional capabilities of BB LDPC codes. For more details on these topics, see the Supplementary Information.
Syndrome circuit
Our syndrome measurement circuit relies on 2n physical qubits, comprising of n data qubits and n ancillary check qubits used to record the measured syndromes. It repeatedly measures the syndrome of each check operator. The single syndrome cycle is illustrated in Fig. 2. The entire syndrome measurement circuit was composed to simultaneously minimize the number of gates used, optimize depth (including parallelizing register measurement with state initialization and with gate application, whenever possible), limit the propagation of errors and comply with the qubittoqubit connectivity layout offered by the Tanner graph. We refer the interested reader to Supplementary Information for the complete circuit description and proof of its correctness.
We used a computer search to find a total of 936 lowdepth syndrome measurement circuit alternatives. For the [[144, 12, 12]] code, the circuit shown in Fig. 2 achieves circuit distance of less than or equal to ten and we conjecture it equals ten. This syndrome measurement circuit was used to compile the data for all codes reported in Fig. 3, leaving the possibility that tailoring each of the 936 alternatives to specific codes would yield better results.
Decoder
We adapt the BPOSD^{36,65,66} to the circuit noise model. This involves both an offline and online stage. In the offline stage, we take as input the syndrome measurement circuit and the error rate p. For every distinct single fault, we simulate the circuit efficiently using the stabilizer formalism, tracking the probability of the fault, the syndrome observed, and a final ideal syndrome. We also record in each case the logical syndrome, which indicates the logical operators anticommuting with the final error. In the online stage, we take a syndrome instance and determine a likely set of faults that occurred. Using the results of the offline stage, we can formulate this as an optimization problem, which is solved heuristically by BPOSD.
We also leverage BPOSD to perform two additional useful tasks that can be framed as appropriate optimization problems. First, given a code, we can find an upper bound on the code distance. Second, given a code and a syndrome measurement circuit, we can determine an upper bound on the circuit distance.
Logical memory capabilities
As depicted in Fig. 1c a BB LDPC code can be used as a data storage unit for, for example, a small surface code quantum computer. To this end we demonstrate two capabilities: joint logical XX measurements between a surface code qubit and any qubit within the BB code, and logical Z measurements on any qubit in the BB code. These measurements facilitate quantum teleportation circuits implementing loadstore operations, transporting qubits into and out of the BB code.
These measurements are facilitated by the combination of two techniques. A construction based on ref. ^{50} enables faulttolerant logical measurement of one logical X and one logical Z operator. The main idea, as illustrated in Fig. 1c, is to extend the Tanner graph of the BB code to a larger code that features the desired logical operators as stabilizers. We show that this extended Tanner graph is compatible with a thickness2 architecture while simultaneously connecting the logical X extension to an ancillary surface code.
To extend the reach of these logical measurements beyond a single X and Z operator, we leverage techniques from ref. ^{67} to derive several faulttolerant unitary operations. These operations achieve measurement of X and Z for all qubits by acting on the original measurement by conjugation, and have faulttolerant circuit implementations within the existing connectivity of the Tanner graph.