High-threshold and low-overhead fault-tolerant quantum memory

Unknown, arXiv:2308.07915 (2023) 的机器可读全文页。

文献信息

Unknown, arXiv:2308.07915 (2023)，“High-threshold and low-overhead fault-tolerant quantum memory”. arXiv:2308.07915 原文为 arXiv 预印本版本的机器可读转换，公式与图注以原文为准；本页仅作站内索引与全文查阅，引用请以正式出版物为准。

全文

High-threshold and low-overhead fault-tolerant quantum memory

Sergey Bravyi¹, Andrew W. Cross¹, Jay M. Gambetta¹, Dmitri Maslov¹, Patrick Rall², and Theodore J. Yoder¹

¹IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598 (USA) ²IBM Quantum, MIT-IBM Watson AI Lab, Cambridge, MA 02142 (USA)

February 22, 2024

Abstract

Quantum error correction becomes a practical possibility only if the physical error rate is below a threshold value that depends on a particular quantum code, syndrome measurement circuit, and decoding algorithm. Here we present an end-to-end quantum error correction protocol that implements fault-tolerant memory based on a family of LDPC codes with a high encoding rate that achieves an error threshold of 0.8% for the standard circuitbased noise model. This is on par with the surface code which has remained an uncontested leader in terms of its high error threshold for nearly 20 years. The full syndrome measurement cycle for a length-n code in our family requires n ancillary qubits and a depth-7 circuit composed of nearest-neighbor CNOT gates. The required qubit connectivity is a degree-6 graph that consists of two edge-disjoint planar subgraphs. As a concrete example, we show that 12 logical qubits can be preserved for nearly one million syndrome cycles using 288 physical qubits in total, assuming the physical error rate of 0.1%. We argue that achieving the same level of error suppression on 12 logical qubits with the surface code would require nearly 3000 physical qubits. Our findings bring demonstrations of a low-overhead fault-tolerant quantum memory within the reach of near-term quantum processors.

1 Introduction

Quantum computing attracted attention due to its ability to ofer asymptotically faster solutions to a set of com putational problems compared to the best known classical algorithms [1]. It is believed that a scalable functioning quantum computer may help solve computational problems in such areas as scientific discovery, materials research, chemistry, and drug design, to name a few [2, 3, 4, 5].

The main obstacle to building a quantum computer is the fragility of quantum information, owing to various sources of noise afecting it. Since isolating a quantum computer from external efects and controlling it to induce a desired computation are in conflict with each other, noise appears to be inevitable. The sources of noise include imperfections in qubits, materials used, controlling apparatus, State Preparation and Measurement (SPAM) errors, and a variety of external factors ranging from local man-made, such as stray electromagnetic fields, to those inherent to the Universe, such as cosmic rays. See Ref. [6] for a summary. While some sources of noise can be eliminated with better control [7], materials [8], and shielding [9, 10, 11], a number of other sources appear to be dificult if at all possible to remove. The latter kind can include spontaneous and stimulated emission in trapped ions [12, 13], and the interaction with the bath (Purcell Efect) [14] in superconducting circuits—covering both leading quantum technologies. Thus, error correction becomes a key requirement for building a functioning scalable quantum computer.

The possibility of quantum fault tolerance was established earlier [15]. Encoding a logical qubit redundantly into many physical qubits enables one to diagnose and correct errors by repeatedly measuring syndromes of parity check operators. However, error correction is only beneficial if the hardware error rate is below a certain threshold value that depends on a particular error correction protocol. The first proposals for quantum error correction, such as concatenated codes [16, 17, 18], focused on demonstrating the theoretical possibility of error suppression. As understanding of quantum error correction and the capabilities of quantum technologies matured, the focus shifted to finding practical quantum error correction protocols. This resulted in the development of the surface code [19, 20 21, 22] that ofers a high error threshold close to 1%, fast decoding algorithms, and compatibility with the existing quantum processors relying on 2-dimensional (2D) square lattice qubit connectivity. Small examples of the surface code with a single logical qubit have been already demonstrated experimentally by several groups [23, 24, 25, 26, 27] However, scaling up the surface code to a hundred or more logical qubits would be prohibitively expensive due to its poor encoding eficiency. This spurred interest in more general quantum codes known as Low-Density Parity-Check (LDPC) codes [28]. Recent progress in the study of LDPC codes suggests that they can achieve quantum faulttolerance with a much higher encoding eficiency [29]. Here, we focus on the study of LDPC codes, as our goal is to find quantum error correction codes and protocols that are both eficient and possible to demonstrate in practice, given the limitations of quantum computing technologies.

A quantum error correcting code is of LDPC type if each check operator of the code acts only on a few qubits and each qubit participates only in a few checks. Multiple variants of the LDPC codes have been proposed recently including hyperbolic surface codes [30, 31, 32], hypergraph product [33], balanced product codes [34], two-block codes based on finite groups [35, 36, 37, 38], and quantum Tanner codes [39, 40]. The latter were shown [39, 40] to be asymptotically “good” in the sense of ofering a constant encoding rate and linear distance – a parameter quantifying the number of correctable errors. In contrast, the surface code has an asymptotically zero encoding rate and only square-root distance. Replacing the surface code with a high-rate, high-distance LDPC code could have major practica implications. First, fault-tolerance overhead (the ratio between the number of physical and logical qubits) could be reduced dramatically. Secondly, high-distance codes exhibit a very sharp decrease in the logical error rate: as the physical error probability crosses the threshold value, the amount of error suppression achieved by the code can increase by orders of magnitude even with a small reduction of the physical error rate. This feature makes high-distance LDPC codes attractive for near-term demonstrations which are likely to operate in the near-threshold regime. However, it was previously believed that outperforming the surface code for realistic noise models including memory, gate, and SPAM errors may require very large LDPC codes with more than 10,000 physical qubits [31].

Here we present several concrete examples of high-rate LDPC codes with a few hundred physical qubits equipped with a low-depth syndrome measurement circuit, an eficient decoding algorithm, and a fault-tolerant protocol for addressing individual logical qubits. These codes exhibit an error threshold close to 1%, show excellent performance in the near-threshold regime, and ofer more than 10X reduction of the encoding overhead compared with the surface code. Hardware requirements for realizing our error correction protocols are relatively mild, as each physical qubit is coupled by two-qubit gates with only six other qubits. Although the qubit connectivity graph is not locally embeddable into a 2D grid, it can be decomposed into two planar degree-3 subgraphs. As we argue below, such qubit connectivity is well-suited for architectures based on superconducting qubits. Before stating our results, let us describe several must-have features for a quantum error-correcting code to be suitable for near-term experimental demonstrations and formally pose the problem addressed in this work.

2 Code selection criteria

In this work, we study the problem of realizing a fault-tolerant quantum memory with a small qubit overhead and a large code distance. Our goal is to construct a combination of the LDPC code, syndrome measurement circuitry, and the decoding (error correction) algorithms, suitable for a near-term demonstration, but also ofering long-term utility, while taking into account the capabilities and limitations of the superconducting circuits quantum hardware. In other words, we seek to develop a practical error correction protocol. Our selection criteria reflect this goal.

We focus on encoding $k\gg 1$ logical qubits into n data qubits and use c ancillary check qubits to measure the error syndrome. In total, the code relies on $n+c$ physical qubits. The net encoding rate is therefore

$$r=\frac{k}{n+c}.$$

For example, the standard surface code architecture encodes $k=1$ logical qubit into $n=d^2$ data qubits for a distance-d code and uses $c=n-1$ check qubits for syndrome measurements. The net encoding rate is $r\approx 1/(2d^2)$ , which quickly becomes impractical as one is forced to choose a large code distance, due to, for instance, the physical errors being close to the threshold value. In contrast, we seek a high-rate LDPC code with $r\gg 1/d^2$

To prevent the accumulation of errors one must be able to measure the error syndrome frequently enough. This is accomplished by a syndrome measurement (SM) circuit that couples data qubits in the support of each check operator with the respective ancillary qubit by a sequence of CNOT gates. Check qubits are then measured revealing the value of the error syndrome. The time it takes to implement the SM circuit is proportional to its depth — the number of gate layers composed of non-overlapping CNOTs. Since new errors continue to occur while the SM circuit is executed its depth should be minimized. Thus we seek an LDPC code with a high rate r and low-depth SM circuit.

A noisy version of the SM circuit may include several types of faulty operations such as memory errors on data or check qubits, faulty CNOT gates, qubit initializations and measurements. We consider the circuit-based noise model [22] where each operation fails with the probability $p.$ . Faults on diferent operations are independent. A logical error occurs when the final error-corrected state of k logical qubits difers from the initial encoded state. The probability of a logical error $p_L$ depends on the error rate $p,$ details of the SM circuits, and a decoding algorithm. A pseudo-threshold $p_0$ of an error correction protocol is defined as a solution of the break-even equation $p_L(p)=kp$ Here $kp$ is an estimate of the probability that at least one of k unencoded qubits sufers from an error. To achieve a significant error suppression in the regime $p\sim 10^{-3}$ , which is relevant for near-term demonstrations, it is desirable to have pseudo-threshold close to $1\%$ or higher. For example, the surface code architecture achieves pseudo-threshold $p_0\approx 1\%$ for a large enough code distance [22]. We seek a high-rate LDPC code with a low-depth SM circuit and a high pseudo-threshold.

A logical error is undetectable if it can be generated without triggering any syndromes. Such errors span at least d data qubits for a distance-d code. Let us say that a SM circuit has distance $d_{\mathsf{circ}}$ if it takes at least $d_{\mathsf{circ}}$ faulty operations in the circuit to generate an undetectable logical error. By definition, $d_{\mathsf{circ}}\le d$ for any distance-d code and typically $d_{\mathsf{circ}}<d$ since a few faulty operations in the SM circuit may create a high-weight error on the data qubits. We say that a SM circuit is distance-preserving if $d_{\mathsf{circ}}=d$ meaning the circuit is designed so as to avoid accumulating high-weigh errors, which is the best one can hope for. It is preferred (but not required) that the SM circuit is distance-preserving.

Another criterion is dictated by the limited qubit connectivity of near-term quantum devices. Each quantum code can be described by a Tanner graph G such that each vertex of G represents either a data qubit or a check operator A check vertex i and a data vertex j are connected by an edge if the i-th check operator acts non-trivially on the j-th data qubit (by applying Pauli X or $Z)$ . Figure 1 A) shows the Tanner graph describing a distance-3 surface code. To keep the SM circuit depth small, it is desirable that two-qubit gates such as CNOT can be applied along every edge of the Tanner graph. By construction, the Tanner graph of any LDPC code has a small degree. One drawback of high-rate LDPC codes is that their Tanner graphs may not be locally embeddable into the 2D grid [41, 42]. This poses a challenge for hardware implementation with superconducting qubits coupled by microwave resonators. A useful VLSI design concept is graph thickness, see [43, 29] 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\bigsqcup E_2\bigsqcup ...\bigsqcup E_{\theta }=E$ such that each subgraph $(V,E_i)$ is planar. Informally, a graph with thickness θ can be viewed as a vertical stack of $\theta$ planar graphs. Qubit connectivity described by a planar graph (thickness θ = 1) is the simplest one from hardware perspective since the couplers do not cross. Graphs with thickness $\theta =2$ might still be implementable since two planar layers of couplers and their control lines can be attached to the top and the bottom side of the chip hosting qubits, and the two sides mated (see Section 10 for a detailed discussion). Graphs with thickness $\theta \ge 3$ are much harder to implement. Thus we seek a high-rate LDPC code with a low-depth SM circuit, high pseudo-threshold, and a low-degree Tanner graph with thickness $\theta \le 2$

Finally, the code must perform a useful function within a larger architecture for quantum computation, the simplest of which is a quantum memory. In a quantum memory it must be possible to measure every logical qubit in at least one Pauli basis, permitting initialization and readout of individual qubits. Furthermore it should be possible to connect the code to another error correction code and facilitate Pauli product measurements between their logical qubits. This enables load-store operations that transfer quantum data out of and into the code via quantum teleportation. For the purpose of the shorter-term goal of demonstrating the code in practice, the code should also feature enough logical operations to facilitate experiments to verify correct operation.

Our code selection criteria are summarized below.

1. We desire a code with a large distance d and a high encoding rate $r\gg 1/d^2$

2. that is complemented by a short-depth syndrome measurement circuit,

3. ofers a pseudo-threshold close to 1% (or higher) for the circuit-based noise model,

4. is constructed over thickness-2 or less Tanner graph,

5. and possesses fault-tolerant load-store operations as well as readout and initialization of individual qubits.

3 Main results

Here we give concrete examples of LDPC codes equipped with syndrome measurement circuits and eficient decoding algorithms that meet all above conditions. Our examples fall into the family of tensor product generalized bicycle codes proposed by Kovalev and Pryadko [35]. We named our codes Bivariate Bicycle (BB) since they are based on bivariate polynomials, as detailed below. These are stabilizer codes of CSS-type [44, 45] that can be described by a collection of few-qubit check (stabilizer) operators composed of Pauli X and Z. At a high level, a BB code is similar to the two-dimensional toric code [19]. In particular, physical qubits of a BB code can be laid out on a two-dimensional grid with periodic boundary conditions such that all check operators are obtained from a single pair of X- and Z-checks by applying horizontal and vertical shifts of the grid. However, in contrast to the plaquette and vertex stabilizers describing the toric code, check operators of a BB code are not geometrically local. Furthermore, each check acts on six qubits rather than four qubits. See Figure 1 B) an example Tanner graph of a BB code. We give a formal definition of BB codes in Section 4. The Tanner graph of any BB code has vertex degree six. Although this graph may not be locally embeddable into a 2D grid, we show that it has thickness $\theta =2.$ , as desired. This result may be surprising since it is known that a general degree-6 graph can have thickness $\theta =3,$ see [43].

Tanner Graphs of Surface and Bivariate Bicycle Codes

Figure 1: A) Tanner graph of a surface code, for comparison. C) Tanner graph of a Bivariate Bicycle code with parameters [[144, 12, 12]] embedded into a torus. Any edge of the Tanner graph connects a data and a check vertex Data qubits associated with the registers $q(L)$ and $q(R)$ are shown by bLue and oRange circles. Each vertex has six incident edges including four short-range edges (pointing north, south, east, and west) and two long-range edges. There are also several long-range edges, of which we only show a few to to avoid clutter. Dashed and solid edge indicate two planar subgraphs spanning the Tanner graph, see Section 4. B) Sketch of a Tanner graph extension fo measuring $\bar{Z}$ and $\bar{X}$ following [46]. The ancilla corresponding to the $\bar{X}$ measurement can be connected to a surface code, enabling load-store operations for all logical qubits via quantum teleportation and some logical unitaries. This extended Tanner graph has a thickness-2 implementation, see Section 9.

Below we use the standard notation $[[n,k,d]]$ for code parameters. Here n is the code length (the number of data qubits), k is the number of logical qubits, and d is the code distance. Table 1 shows small examples of BB codes along with several metrics of the error suppression achieved by each codes. The distance-12 code [[144, 12, 12]] may be the most promising for near-term demonstrations, as it combines large distance and high net encoding rate $r=1/24$ . For comparison, the distance-13 surface code has net encoding rate $r=1/338$ . Below we show that the distance-12 BB code outperforms the distance-13 surface code for the experimentally relevant range of error rates, see Figure 2 B) To the best of our knowledge, all codes shown in Table 1 are new.

[[n,k,d]]	Net Encoding Rate r	Circuit-level distance $d_{\text{circ}}$	Pseudo-threshold $p_0$	$p_L(0.001)$	$p_L(0.0001)$
[[72,12,6]]	1/12	≤ 6	0.0048	$7\times 10^{-5}$	$7\times 10^{-8}$
[[90,8,10]]	1/23	≤ 8	0.0053	$5\times 10^{-6}$	$4\times 10^{-10}$
[[108,8,10]]	1/27	≤ 8	0.0058	$3\times 10^{-6}$	$1\times 10^{-10}$
[[144,12,12]]	1/24	≤ 10	0.0065	$2\times 10^{-7}$	$8\times 10^{-13}$
[[288,12,18]]	1/48	≤ 18	0.0069	$2\times 10^{-12}$	$1\times 10^{-22}$

Table 1: Small examples of Bivariate Bicycle LDPC codes and their performance for the circuit-based noise model All codes have weight-6 checks, thickness-2 Tanner graph, and a depth-7 syndrome measurement circuit. A code with parameters $[[n,k,\bar{d}]]$ requires 2n physical qubits in total and achieves the net encoding rate $r=k/2n$ (we round r down to the nearest inverse integer). Circuit-level distance $d_{\mathsf{circ}}$ is the minimum number of faulty operations in the syndrome measurement circuit required to generate an undetectable logical error. The pseudo-threshold $p_0$ is a solution of the break-even equation $p_L(p)=kp$ , where p and $p_L$ are the physical and logical error rates respectively. The logical error rate $p_L$ was computed numerically for $p\ge 10^{-3}$ and extrapolated to lower error rates.

To quantify the level of error suppression achieved by a code we introduce SM circuits that repeatedly measure the syndrome of each check operator. The full cycle of syndrome measurement for a length-n BB code requires n ancillary check qubits to store the measured syndromes. According, the net encoding rate is $r=k/(2n)$ . Check qubits are coupled with the data qubits by applying a sequence of CNOT gates. The full cycle of syndrome measurement requires only 7 layers of CNOTs regardless of the code length. The check qubits are initialized and measured at the beginning and at the end of the syndrome cycle respectively, see Section 5 for details. We emphasize that our SM circuit applies to any BB code beyond those listed in Table 1. The circuit respects the cyclic shift symmetry of the underlying code. Assuming that the physical qubits (data or check) are located at vertices of the Tanner graph, all CNOT gates in the SM circuit act on nearest-neighbor qubits. Thus the required qubit connectivity is described by a degree-6 thickness-2 graph, as desired. We conjecture, based on the numerical simulations, that our SM circuit is distance-preserving for the code [[72, 12, 6]], see Table 1 for the upper bounds on $d_{\mathsf{circ}}$ (the upper bound $d_{\mathsf{circ}}\le 18$ for the 288-qubit code is unlikely to be tight and this afects the fit and extrapolations).

The full error correction protocol performs $N_c\gg 1$ syndrome measurement cycles and calls a decoder — a classical algorithm that takes as input the measured syndromes and outputs a guess of the final error on the data qubits. Error correction succeeds if the guessed and the actual error coincide modulo a product of check operators. In this case the two errors have the same action on any encoded (logical) state. Thus applying the inverse of the guessed error would return data qubits to the initial logical sate. Otherwise, if the guessed and the actual error difer by a non-trivial logical operator, error correction fails resulting in a logical error. Our numerical experiments are based on the Belief Propagation with an Ordered Statistics Decoder (BP-OSD) proposed by Panteleev and Kalachev [36]. The original work [36] described BP-OSD in the context of a toy noise model with memory errors only. Here we show how to extend BP-OSD to the circuit-based noise model. Our approach closely follows Refs. [47, 48, 49, 50]. We also show that BP-OSD can be applied to other problems in quantum fault-tolerance such as estimating the distance of a quantum LDPC code, see Section 6 for details. These tasks can be accomplished with a relatively minor extension of the publicly available BP-OSD software developed by Rofe et al. [51]

Let $P_L(N_c)$ be the logical error probability after performing $N_c$ syndrome cycles. Define the logical error rate as $p_L=1-(1-P_L(N_c){)}^{1/N_c}\approx P_L(N_c)/N_c$ . Informally, $p_L$ can be viewed as the logical error probability per syndrome cycle. Following common practice, we choose $N_c=d$ for a distance-d code. Figure 2 A) shows the logical error rate achieved by codes from Table 1. The logical error rate was computed numerically for $p\ge 10^{-3}$ and extrapolated to lower error rates using a fitting formula ${\stackrel{⌣}{p}}_L=p^{d_{\mathrm{circ}}^{\prime }/2}{e}^{c_0+c_{1}p+c_2{p}^2}$ , where $c_0,c_1,c_2$ are fitting parameters and $d_{\mathsf{circ}}^{\prime }$ is an upper bound on $d_{\mathsf{circ}}$ from Table 1. The observed pseudo-threshold for the 144-qubit and 288-qubit codes is close to 0.007, which is nearly the same as the error threshold of the surface code [52]. To the best of our knowledge, this provides the first example of high-rate, large-distance LDPC codes achieving the pseudo-threshold close to 1% under the circuit-based noise model.

(a) A subfigure

(b) A subfigure
Figure 2: A) Logical vs physical error rate for small examples of Bivariate Bicycle LDPC codes. A numerical estimate of $p_L$ (diamonds) was obtained by simulating d syndrome cycles for a distance-d code. Most of the data points have error bars $\approx p_L/10$ due to sampling errors. B) Comparison between the Bivariate Bicycle LDPC code [[144, 12, 12]] and surface codes with 12 logical qubits and distance $d\in \{9,11,13,15\}$ . The distance-d surface code with 12 logical qubits has length $n=12d^2$ since each logical qubit is encoded into a separate d×d patch of the surface code lattice.

For example, suppose that the physical error rate is $p=10^{-3}$ , which is a realistic goal for near-term demonstrations. Encoding 12 logical qubits using the distance-12 code from Table 1 would ofer the logical error rate $2\times 10^{-7}$ which is enough to preserve 12 logical qubits for nearly one million syndrome cycles. The total number of physical qubits required for this encoding is 288. The distance-18 code from Table 1 would require 576 physical qubits while suppressing the error rate from $10^{-3}$ to $2\times 10^{-12}$ enabling roughly hundred billion syndrome cycles. For comparison, encoding 12 logical qubits into separate patches of the surface code would require nearly 3000 physical qubits to suppress the error rate from $10^{-3}$ to $10^{-6}$ , see Figure 2 B). In this example the distance-12 BB code ofers more than 10X saving in the number of physical qubits compared with the surface code.

We also find that BB LDPC codes admit extensions that allow them to function as a logical memory with loadstore operations. In Section 9 we show how to use methods from [46] to attach two ancilla systems to the code tha permit logical measurement of all logical qubits in the X and Z bases. Which logical qubit is being measured can be controlled via a set of fault tolerant unitary operations. The extended Tanner graph is not only thickness-2, but the extension from the X ancilla system is “efectively planar” (in a sense we define later) facilitating interconnection with other codes on the same chip.

Our findings bring experimental demonstration of high-rate LDPC codes within the reach of near-term quantum processors which are expected to ofer a few hundred physical qubits, gate error rates close to $10^{-3}$ , and long range qubit connectivity [53].

The rest of this paper is organized as follows. Section 4 formally defines BB LDPC codes and proves their basic properties. The construction of the syndrome measurement circuit is detailed in Section 5. The circuit-based noise model and BP-OSD decoder for this noise model are discussed in Section 6 with some implementation details deferred to Section 8. We describe fault tolerant memory capabilities in Section 9. A summary of our findings and some open questions can be found in Section 10.

Notation	Name	Definition
rs(H)	row space	Linear span of rows of H
cs(H)	column space	Linear span of columns of H
ker(H)	nullspace	Vectors orthogonal to each row of H
rk(H)	rank	rk(H) = dim(rs(H)) = dim(cs(H))

Table 2: Notations for linear spaces associated with a binary matrix H. Here the linear span, orthogonality, and dimension are computed over the binary field ${\mathbb{F}}_2=\{0,1\}$ . If H has size $s\times n$ then $\mathsf{rs}(H)\subseteq {\mathbb{F}}_2^n,\mathsf{cs}(H)\subseteq {\mathbb{F}}_2^s$ , and ker $(H)\subseteq {\mathbb{F}}_2^n$

4 Bivariate Bicycle quantum LDPC codes

Let $I_{\ell }$ and $S_{\ell }$ be the identity matrix and the cyclic shift matrix of size $\ell \times \ell$ respectively. The i-th row of $S_{\ell }$ has a single nonzero entry equal to one at the column $i+1$ (mod ℓ). For example,

$$S_2=\left[\begin{array}{ll}0& 1\\ 1& 0\end{array}\right]\text{and}{S}_3=\left[\begin{array}{lll}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right].$$

Consider matrices

$$x=S_{\ell }\otimes I_m\mathrm{and}y=I_{\ell }\otimes S_m.$$

Note that $xy=yx$ and $x^{\ell }=y^m=I_{\ell m}$ . A BB code is defined by a pair of matrices

$$A=A_1+A_2+A_3\text{ and }B=B_1+B_2+B_3\text{\hspace{1em}(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 non-zero entries in each row and each column. Furthermore, $AB=BA$ since $xy=yx$ . The above data defines a BB LDPC code denoted $\mathsf{QC}(A,B)$ with length $n=2\ell m$ and check matrices

$$H^X=[A|B]\mathrm{and}{H}^Z=\left[B^T|A^T\right].\text{\hspace{1em}(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)\times n$ . Each row $v\in {\mathbb{F}}_2^n$ of $H^X$ defines an X-type check operator $\begin{array}{r}\bar{X}(v)={\prod }_{j=1}^n{X}_j^{v_j}\end{array}$ . Each row $v\in {\mathbb{F}}_2^n$ of $H^Z$ defines a $Z-\mathrm{type}$ check operator $\begin{array}{r}Z(v)={\prod }_{j=1}^n{Z}_j^{v_j}\end{array}$ . Any X-check and Z-check commute since they overlap on even number of qubits (note that $H^X(H^Z{)}^T=A\bar{B}+\overline{B^A}=0$ (mod 2)). To describe the code parameters we use certain linear subspaces associated with the check matrices, see Table 1 for our notations. Then the code $\mathsf{QC}(A,B)$ has parameters $[[n,k,d]]$ with

$$n=2\ell m,k=2\cdot \dim (\ker (A)\cap \ker (B))\text{ and }d=\min \{|v|:v\in \ker (H^X)\backslash \mathsf{rs}(H^Z)\},\text{\hspace{1em}(3)}$$

see Lemma 1. Here $|v|={\sum }_{i=1}^n{v}_i$ is the Hamming weight of a vector $v\in {\mathbb{F}}_2^n$ . We note that the code $\mathsf{QC}(A,B)$ can be viewed as a special case of the Lifted Product construction [54] based on the abelian group ${\mathbb{Z}}_{\ell }\times {\mathbb{Z}}_m$ . Here ${\mathbb{Z}}_j$ denotes the cyclic group of order j.

Table 3 describes the polynomials A and B that give rise to examples of high-rate, high-distance 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,\le 24]]$ improves upon a code $[[882,24,\le 24]]$ with weight-6 checks found by Panteleev and Kalachev in [36] (assuming that our distance upper bound is tight). Indeed, taking two independent copies of the 360-qubit code gives parameters $[[720,24,\le 24]]$

By construction, the code $\mathsf{QC}(A,B)$ has weight-6 check operators and each qubit participates in six checks (three X-type plus three Z-type checks). Accordingly, the code $\mathsf{QC}(A,B)$ has a degree-6 Tanner graph. Below we show that the Tanner graph has thickness $\theta \le 2.$ as desired, see Lemma 2.

[[n,k,d]]	Net Encoding Rate r	$\ell ,m$	A	B
[[72,12,6]]	1/12	6,6	$x^3+y+y^2$	$y^3+x+x^2$
[[90,8,10]]	1/23	15,3	$x^9+y+y^2$	$1+x^2+x^7$
[[108,8,10]]	1/27	9,6	$x^3+y+y^2$	$y^3+x+x^2$
[[144,12,12]]	1/24	12,6	$x^3+y+y^2$	$y^3+x+x^2$
[[288,12,18]]	1/48	12,12	$x^3+y^2+y^7$	$y^3+x+x^2$
[[360,12, $\le$ 24]]	1/60	30,6	$x^9+y+y^2$	$y^3+x^{25}+x^{26}$
[[756,16, $\le$ 34]]	1/95	21,18	$x^3+y^{10}+y^{17}$	$y^5+x^3+x^{19}$

Table 3: Small examples of Bivariate Bicycle LDPC codes and their parameters. All codes have weight-6 checks, thickness-2 Tanner graph, and a depth-7 syndrome measurement circuit. Code distance was computed by the mixed integer programming approach of Ref. [55]. Notation $\le d$ indicates that only an upper bound on the code distance is known at the time of this writing. We round r down to the nearest inverse integer. The codes have check matrices $H^X=[A|B]$ and $H^Z=[B^T|A^T]$ with A and B defined in the last two columns. The matrices x, y obey $x^{\ell }=y^m=1$ and $xy=yx$

We note that the recent work by Wang, Lin, and Pryadko [38, 37] described examples of group-based codes closely related to the codes considered here. Some of the group-based codes with weight-8 checks found in [37] outperform our BB codes with weight-6 checks in terms of the parameters $n,k,d.$ It remains to be seen whether group-based codes can achieve a similar or better level of error suppression for the circuit-based noise model.

In the rest of this section we establish some properties of BB LDPC codes.

Lemma 1. The code $\mathsf{QC}(A,B)$ has parameters $[[n,k,d]]$ , where

$$n=2\ell m,k=2\cdot \dim (\ker (A)\cap \ker (B)),andd=\min \left\{|v|:v\in \ker \left(H^X\right)\backslash \mathrm{rs}\left(H^Z\right)\right\}.$$

The code ofers equal distance for X-type and Z-type errors.

Proof. It is known [44, 45] that

$$k=n-\mathsf{rk}(H^X)-\mathsf{rk}(H^Z).$$

We claim that $\mathsf{rk}(H^X)=\mathsf{rk}(H^Z)$ . Indeed, define a self-inverse permutation matrix $C_{\ell }$ of size $\ell \times \ell$ such that the ${}_{i-}$ th column of $C_{\ell }$ has a single nonzero entry equal to one at the row $j=-i$ (mod ℓ). Define $C_m$ similarly and let $\mathcal{C}={\mathcal{C}}_{\ell }\otimes {\mathcal{C}}_m$ . Since $C_{\ell }{S}_{\ell }{C}_{\ell }=S_{\ell }^T$ and $C_m{S}_m{C}_m=S_m^T$ , one gets

$$A^T=CAC\mathrm{and}{B}^T=CBC.\text{\hspace{1em}(4)}$$

Therefore one can write

$$H^Z=[B^T|A^T]=[CBC|CAC]=C[A|B]\left[\begin{array}{cc}0& C\\ C& 0\end{array}\right]=C{H}^X\left[\begin{array}{cc}0& C\\ C& 0\end{array}\right].$$

Thus $H^Z$ is obtained from $H^X$ by multiplying on the left and on the right by invertible matrices. This implies $\mathsf{rk}(H^X)=\mathsf{rk}(H^Z)$ . Therefore

$$\begin{array}{l}k=n-2\cdot \mathsf{rk}(H^Z)=n-2(\frac{n}{2}-\dim \left(\ker ((H^Z{)}^T))\right))=n-2(\frac{n}{2}-\dim \left(\ker (A)\cap \ker (B)\right))\\ =2\cdot \dim \left(\ker (A)\cap \ker (B)\right).\end{array}$$

Here we noted that $H^Z$ has size $(n/2)\times n$ and ker $((H^Z{)}^T))=\mathsf{ker}(A)\cap \mathsf{ker}(B)$ since $H^Z=\lceil B^T|A^T|$ It is known [44, 45] that a CSS code with check matrices $H^X$ and $H^Z$ has distance d = min $({\bar{d}}^X,d^Z)$ , where $d^X$ and $d^Z$ are the code distances for X-type and Z-type errors defined as

$$d^X=\min \left\{|v|:v\in \ker (H^Z)\backslash \mathrm{rs}(H^X)\right\}\text{ and }{d}^Z=\min \left\{|v|:v\in \ker (H^X)\backslash \mathrm{rs}(H^Z)\right\}.$$

We claim that $d^Z\le d^X$ . Indeed, let $\begin{array}{r}X(f)={\prod }_{j=1}^n{X}_j^{f_j}\end{array}$ be a minimum weight logical X-type Pauli operator such that $|f|=d^X$ . Then $H^{Z}f=0$ and $f\notin \mathsf{rs}(H^X)$ . Thus there exists a logical Z-type operator $\begin{array}{r}Z(g)={\prod }_{j=1}^n{Z}_j^{g_j}\end{array}$ anti-commuting with $X(f)$ . In other words, $H^{X}g=0$ and $f^{T}g=1$ . Here, $f$ and g are length-n binary vectors. Write $f=(\alpha ,\beta )$ and $g=\left(\gamma ,\delta \right)$ , where $\alpha ,\beta ,\gamma ,\delta$ are length-(n/2) vectors. Conditions $H^{Z}f=0$ and $H^{X}g=\dot{0}$ are equivalent to

$$B^T\alpha =A^T\beta \text{ and }A\gamma =B\delta .\text{\hspace{1em}(5)}$$

Here and below all arithmetics is modulo two. Define length-n vectors

$$e=(C\delta ,C\gamma )\text{ and }h=(C\beta ,C\alpha ).\text{\hspace{1em}(6)}$$

From Eqs. (13,14) one gets

$$H^{X}h=[A|B]\left[\begin{array}{l}C\beta \\ C\alpha \end{array}\right]=AC\beta +BC\alpha =C(A^T\beta +B^T\alpha )=0.$$

Likewise,

$$H^{Z}e=[B^T|A^T]\left[\begin{array}{l}C\delta \\ C\gamma \end{array}\right]=B^{T}C\delta +A^{T}C\gamma =C(B\delta +A\gamma )=0.$$

Furthermore,

$$h^{T}e={\beta }^{T}CC\delta +{\alpha }^{T}CC\gamma ={\beta }^T\delta +{\alpha }^T\gamma =f^{T}g=1.$$

Thus $X(e)$ and $Z(h)$ are non-identity logical operators. It follows that $d^Z\le |h|$ . We get

$$d^Z\le |h|=|C\beta |+|C\alpha |=|\beta |+|\alpha |=|f|=d^X.$$

Thus $d^Z\le d^X$ . Similar argument shows that $d^X\le d^Z$ , that is, $d^X=d^Z$

We note that the equality $d^X=d^Z$ can also be established using the machinery of Ref. [54] by viewing $\mathsf{QC}(A,B)$ as a Lifted Product code.

In the following, we partition the set of data qubits as $[n]=LR$ , where L and R are the left and right blocks of $n/2=\ell m$ data qubits. Then, data qubits L and R and checks X and $Z$ may each be labeled by integers ${\mathbb{Z}}_{\ell m}=$ $\{0,1,\dots ,\ell m-1\}$ which are indices into the matrices $A,B$ . Alternatively, qubits and checks can be labeled by monomials from $\mathcal{M}=\{1,y,\dots ,y^{m-1},x,xy,\dots ,x{y}^{m-1},\dots ,x^{\ell -1}{y}^{m-1}\}$ in this order, so that $i\in {\mathbb{Z}}_{\ell m}$ labels the same qubit or check as $x^{a_i}{y}^{i-m{a}_i}$ for $a_i=\mathrm{floor}(i/m)$ . Using the monomial labeling, L data qubit $\alpha \in \mathcal{M}$ is part of X checks ${\bar{A}}_i^T\mathrm{o}$ and $Z$ checks $B_i\alpha$ 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 β. A unified notation assigns each qubit or check a label $q(T,\alpha )$ where $T\in \{L,R,X,Z\}$ denotes its type and $\alpha \in \mathcal{M}$ its monomial label¹.

Lemma 2. The Tanner graph G of the code QC(A, B) has thickness $\theta \le 2$ . A decomposition of G into two planar layers can be computed in time $O(n)$ . Each planar layer of G is a degree-3 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

$$\text{ Tanner graph }{G}_A:H_A^X=[A_2+A_3|B_3]\text{ and }{H}_A^Z=[B_3^T|A_2^T+A_3^T]\text{\hspace{1em}(7)}$$ $$\mathrm{Tannergraph}{G}_B:H_B^X=[A_1|B_1+B_2]\mathrm{and}{H}_B^Z=[B_1^T+B_2^T|A_1^T].\text{\hspace{1em}(8)}$$

Since $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$ , where 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 degree-3 graphs (since $A_i$ and $B_j$ are permutation matrices).

Consider the graph $G_A$ . Each X-check vertex is connected to a pair of data vertices $i_1,i_2\in L$ via the matrices $A_2,A_3$ and a data vertex $i_3\in R$ via the matrix $B_3$ . Each Z-check vertex is connected to a pair of data vertices $i_1,i_2\in R$ via the matrices $A_2^T,A_3^T$ and a data vertex $i_3\in L$ via the matrix $B_3^T$

B) Extraction of ‘B’ wheels in $G_{\mathrm{B}}$

$$G_{\mathrm{A}}$$

Figure 3: A). B) Two diferent grids over a torus defined using diferent subsets of $A_1,A_2,A_3,B_1,B_2,B_3$ . Edge labels indicate adjacency matrices that generate the respective edges. By extracting either horizontal or vertical strips from these grids, we obtain planar ‘wheel graphs’ whose union contains all edges in the Tanner graph. The ${\Omega }^{⟨}{\mathrm{A}}^{⟩}$ wheels (dashed lines) cover $A_2,A_3,B_3$ and the ${\cdot }_{\mathrm{B}},$ wheels (solid lines) cover $B_1,B_2,A_1$ . To avoid clutter, each grid shows only a subset of edges present in the Tanner graph.

Figure 4: A) “Compass” diagram that shows the direction in which matrices A, B are applied to travel between diferent nodes. B) The unit cell of the construction of a toric layout in the proof of Lemma 4.

We claim that each connected component of $G_A$ can be represented by a “wheel ${\mathrm{graph}}^{\prime \prime }$ illustrated in Figure 3. A wheel graph consists of two disjoint cycles of the same length p interconnected by p radial edges. The outer cycle alternates between X-check 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^{\check{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 p such that $(A_3{A}_2^T{)}^p=I_{\ell m}$ . For example, consider the code [[144, 12, 12]] from Table 3. Then $A=x^3+y+y^2,A_2=y$ , and $A_3=y^2$ . Thus $A_3{A}_2^T=y^2{y}^{-\bar{1}}=y$ which has order $m=6$ . The inner cycle of a wheel graph alternates between Z-check and R-data 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$ which is just the transpose of $A_3{A}_3^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 Figure 3 A). Radial edges are generated by the matrix $B_3,$ , as one moves towards the center of the wheel. The wheel graph contains 4-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 4-cycles implements the identity matrix, that is, the graph is well defined. Clearly, the wheel graph is planar. Since

$G_A$ is a disjoint union of wheel graphs, $G_A$ is planar. The same argument shows that $G_B$ is planar: see Figure 3 B). □

We empirically observed that BB codes reported in Table 3 have no weight-4 stabilizers. The presence of such stabilizers is known to have a negative impact on the performance of belief propagation decoders [36], which we use here.

The definition of code $\mathsf{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 Table 3 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 $\mathsf{QC}(A,B)$ is connected if and only $ifS=\{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 M. The number of connected components in the Tanner graph is $\ell m/|⟨S⟩|$ , and all components are graph isomorphic to one another.

Proof. Figure 4 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($ α 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 $\beta .$ A similar argument shows the existence of a path connecting any pair of R qubits. Since 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\in \{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 labeled 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 sub-graph of a graph G is a sub-graph 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\in S,s\ne 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^{\mathrm{ord}(g)}=1$

Definition 1. Code $\mathsf{QC}(A,B)$ is said to have a toric layout if its Tanner graph has a spanning sub-graph 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 Figure 1 B).

Lemma 4. A code $\mathsf{QC}(A,B)$ has a toric layout if there exist $i,j,g,h\in \{1,2,3\}$ such that

(i) $⟨A_i{A}_j^T,B_g{B}_h^T⟩=\mathcal{M}$ and

(ii) $\mathrm{ord}(A_i{A}_j^T)\mathrm{ord}(B_g{B}_h^T)=\ell m.$

Proof. We let $\mu =\mathrm{ord}(A_i{A}_i^T)$ and $\lambda =\mathrm{ord}(B_g{B}_h^T)$ . We associate qubits and checks in the Tanner graph of $\mathsf{QC}(A,B)$ with elements of $\mathcal{G}={\mathbb{Z}}_{2\mu }\breve{\times }{\mathbb{Z}}_{2\lambda }$ . For L qubit with label $\alpha \in \mathcal{M}$ , because of (i), 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 (ii) 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}$ , X-check $\alpha A_j^T$ with $(2a+1,2b)$ , and Z-check ${}_{\mathcal{X}{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 Figure 4 (B) and correspond to edges in the Cayley graph of 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 labeled $\alpha A_j^T{B}_g$ to the $Z$ check labeled $(\alpha A_j^T{B}_g)A_i=\alpha (A_i{A}_j^T)B_g$ □

Notation	Operation
CNOT c t	CNOT with control qubit c and target qubit t
InitX q	Initialize qubit q in the state |+⟩ = (|0⟩ + |1⟩)/ $\sqrt{2}$
InitZ q	Initialize qubit q in the state |0⟩
MeasX q	Measure qubit q in the X-basis |+⟩, |−⟩
MeasZ q	Measure qubit q in the Z-basis |0⟩, |1⟩
Idle q	Identity gate on qubit q

Table 4: Elementary operations used for syndrome measurements.

All codes in Table 3 have a toric layout with $\mu =m$ and $\lambda =\ell .$ . 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 $\mathsf{QC}(A,B)$ with $\ell ,m=28$ , 14, $A=\overline{x^{26}+y^6+y^8}$ , and $B=y^7+x^9+x^{20}$ which has parameters $[[784,24,\le 24]]$ . Second, for a code satisfying the conditions of Lemma 4, it need not be the case that the set $\{\mathrm{ord}({\stackrel{\cdot \cdot }{A}}_i{A}_j^T),\mathrm{ord}(B_g{\stackrel{\cdot \cdot }{B}}_h^T)\}$ and the set $\{\ell ,m\}$ are equal. For example, the $[[432,4,\le 22]]$ code with $\ell ,m=18,12$ and $A=x+y^{11^{\circ }}+y^3,B=y^2+x^{15}+x$ only satisfies Lemma 4 with $\mu ,\lambda =36,6$ (take $i=g=1$ and $j=h=2$ for instance).

5 Syndrome measurement circuit

The next step is to furnish the code $\mathsf{QC}(A,B)$ with a syndrome measurement (SM) circuit that repeatedly measures the syndrome of each check operator. Here we describe a SM circuit that requires 2n physical qubits in total: n data qubits and n ancillary check qubits used to record the measured syndromes. The circuit only applies CNOTs to pairs of qubits that are connected in the Tanner graph.

The SM circuit is defined as a periodically repeated sequence of syndrome cycles (SC). A single SC is responsible for measuring syndromes of all n check operators of the code. Let $N_c$ be the number of syndrome cycles. We envision that $N_c>1$ . The circuit begins and ends with a special initialization and measurement cycle responsible for initializing logical qubits in a suitable initial state and measuring logical qubits in a suitable basis. Here we focus on the optimization of the SC circuit. Logical initialization and measurements are discussed in Section 9.

The SC circuit is divided into $N_r$ rounds such that each round is a depth-1 circuit composed of CNOTs and singlequbit operations. The latter include initializing a qubit in the X or $Z$ basis and measuring a qubit in the X or Z basis. CNOTs can be applied only to pairs of qubits which are nearest neighbors in the Tanner graph. Some qubits remain idle during some rounds, although we try to minimize such occurrences by squeezing more useful computations in as little time as possible. Our notations are summarized in Table 4.

Below we describe a SC circuit with efectively $N_r=8{\mathrm{rounds}}^2$ . Ignoring single-qubit initialization and measurement operations, the SC circuit is a depth-7 CNOT circuit. By designing the circuit for an explicit family of LDPC codes we are able to leverage the symmetries and reduce computational depth to 7 from what otherwise would be $14=2\cdot 6+2,$ as shown by previous authors [29, Theorem 1]. Our notations are as follows. We divide n data qubits into the left and the right registers $q(L)$ and $q(R)$ of size $n/2$ each. Each check operator acts on three data qubits from $q(L)$ and three data qubits from $q(R)$ . The SM circuit uses 2n physical qubits in total: n data qubits and n ancillary check qubits that record the syndrome of each check operator. Let $q(X)$ and $q(Z)$ be the ancillary registers of size $n/2$ that span X-check and Z-check qubits respectively. Thus the physical qubits are partitioned into four registers, $q(X),q(L)$ $q(R)$ , and $q(Z)$ , of size $n/2$ each. Label qubits in each register by integers $i=1,2,\dots ,n/2$ . We write $q(X,i)$ for the i-th qubit of the register $q(X)$ with similar notations for $q(L),q(R)$ , and $q(Z)$ . Each permutation matrix $A_p$ and $B_q$ from Eq. (1) defines a one-to-one map from the set $\{1,2,\dots ,n/2\}$ onto itself.

Round	Circuit	Round	Circuit
1	for i = 1 to n/2 doInitX q(X,i)CNOT q(R, $A_1^T(i)$ ) q(Z,i)Idle q(L,i)end for	5	for i = 1 to n/2 doCNOT q(X,i) q(R, $B_3(i)$ )CNOT q(L, $B_3^T(i)$ ) q(Z,i)end for
2	for i = 1 to n/2 doCNOT q(X,i) q(L, $A_2(i)$ )CNOT q(R, $A_3^T(i)$ ) q(Z,i)end for	6	for i = 1 to n/2 doCNOT q(X,i) q(L, $A_1(i)$ )CNOT q(R, $A_2^T(i)$ ) q(Z,i)end for
3	for i = 1 to n/2 doCNOT q(X,i) q(R, $B_2(i)$ )CNOT q(L, $B_1^T(i)$ ) q(Z,i)end for	7	for i = 1 to n/2 doCNOT q(X,i) q(L, $A_3(i)$ )MeasZ q(Z,i)Idle q(R,i)end for
4	for i = 1 to n/2 doCNOT q(X,i) q(R, $B_1(i)$ )CNOT q(L, $B_2^T(i)$ ) q(Z,i)end for	8	for i = 1 to n/2 doMeasX q(X,i)InitZ q(Z,i)Idle q(L,i)Idle q(R,i)end for

Table 5: Depth-8 syndrome measurement cycle circuit.

We identify a permutation matrix and the corresponding one-to-one map. For example, we write $j=A_1(i)$ if the matrix $A_1$ has a one at row i and column $j$ (this is well defined since $A_1$ is a permutation matrix). Likewise, we write $j=A_1^T(i)$ if the transposed matrix $A_1^T$ has a one at the row i and column $j.$ In this notation, the i-th X-check operator acts on data qubits $q(L,A_p(i))$ and $q(R,B_p(i))$ with $p=1,2,3$ . The i-th Z-check operator acts on data qubits $q(L,B_p^T(i))$ and $q(R,A_p^T(i))$ with $p=1,2,3$

Our depth-8 SC circuit is described in Table 5 and illustrated in Figure 5. Note that within each round all operations act over non-overlapping sets of qubits. In particular, each round applies at most one layer of CNOT gates between $q(X)$ and $q(L)$ registers (Rounds 2, 6, and 7), at most one layer of CNOTs between $q(X)$ and $q(R)$ registers (Rounds 3, 4, and 5), at most one layer of CNOTs between $q(Z)$ and $q(L)$ registers (Rounds 3, 4, and 5), and at most one layer of CNOTs between $q(Z)$ and $q(R)$ registers (Rounds 1, 2, and 6). Qubits from $q(Z)$ are always targets for CNOTs. Accordingly, X-type errors propagate from data qubits to check qubits in $q(Z)$ . The latter are measured in the Z-basis in Round 7 revealing the syndrome of X-type errors. Qubits from $q(X)$ are always controls for CNOTs. Accordingly, Z-type errors propagate from data qubits to check qubits in $q(X)$ . The latter are measured in the X-basis in Round 8 revealing the syndrome of Z-type errors. We envision that the syndrome cycles are repeated periodically. This justifies applying CNOTs to $q(Z)$ at Round 1 even though $q(Z)$ is initialized only at Round 8. Indeed, Round 8 of the previous syndrome cycle goes immediately before Round 1 of the current cycle. Thus $q(Z)$ has been already initialized at the beginning of Round 1. We were not able to find a depth-8 (or smaller depth) syndrome cycle in which X-check and Z-check qubits are initialized and measured synchronously.

Let us now prove that the above SC circuit has the desired functionality. Since the circuit involves only Cliford operations, its action can be compactly described using stabilizer tableau [56]. We track how the tableau changes as each layer of CNOTs in the circuit is applied. Since the CNOT gates do not mix Pauli X and Z operators, one may consider tableau describing the action of the circuit on X-type and Z-type Pauli operators separately.

Let us begin with X-type Pauli. The corresponding tableau T is a binary matrix of size $n\times$ 2n such that each row of T defines an X-type stabilizer of the underlying quantum state. We partition columns of $T$ into four blocks that represent qubit registers $q(X),q(L),q(R)$ , and $q(Z)$ . We partition rows of $T$ into two blocks such that initially the top $n/2$ rows represent weight-1 check operators on qubits of the register $q(X)$ initialized in the state $|+⟩$ while the bottom $n/2$ rows represent weight-6 check operators on data qubits associated with the chosen code $\mathsf{QC}(A,B)$ . Thus, at the beginning of Round 1, when all check qubits in the register $q(X)$ have been initialized in the state |+⟩, while data qubits are in some logical state of the code $\mathsf{QC}(A,B)$ , the binary matrix is

Figure 5: Depth-8 syndrome measurement cycle circuit.

$$\left(\begin{array}{cccc}I& 0& 0& 0\\ 0& A& B& 0\end{array}\right).$$

Here $I\equiv I_{n/2}$ is the identity matrix. The SC circuit (ignoring qubit initialization and measurements) enacts the transformation

$$\left(\begin{array}{cccc}I& 0& 0& 0\\ 0& A& B& 0\end{array}\right)\stackrel{\text{ SC circuit }}{\to }\left(\begin{array}{cccc}I& A& B& 0\\ 0& A& B& 0\end{array}\right).$$

Indeed, the circuit must map a single-qubit X stabilizer $X_j$ on a check qubit $j\in q(X)$ to a product of $X_j$ and the j-th X-type check operator on the data qubits determined by the j-th row of $H^X=[A|B]$ . The eigenvalue measurement of $X_j$ at the final round then reveals the syndrome of the j-th check operator. The bottom $n/2$ rows must be unchanged since the check operators of the code must be the same before and after the syndrome measurement.

Let us verify that the circuit defined in Table 5 enacts the desired transformation. To accomplish this, we rewrite the SC circuit by removing notations irrelevant to showing the correctness of X-checks. Specifically, we write each CNOT in Table 5 as ${\mathsf{CNOT}}_M(a,b)$ , where $\begin{array}{r}a,b\in \{1,2,3,4\}=\{q(X),q(L),q(R),q(Z)\}\end{array}$ , and $M\in \{A_1,A_2,A_3,B_1,B_2,B_3\}$ . Note that the CNOT instructions where the matrix $M^T$ is used instead of M can be written using matrix M by performing the variable renaming $i\leftarrow M(i)$ in the corresponding for loop in Table 5.

Using the above compact notation, the unitary part of the SC circuit becomes:

$$\begin{array}{ll}\text{Round 1:}& {\mathsf{CNOT}}_{A_1}(3,4)\\ \text{Round 2:}& {\mathsf{CNOT}}_{A_2}(1,2),{\mathsf{CNOT}}_{A_3}(3,4)\\ \text{Round 3:}& {\mathsf{CNOT}}_{B_2}(1,3),{\mathsf{CNOT}}_{B_1}(2,4)\\ \text{Round 4:}& {\mathsf{CNOT}}_{B_1}(1,3),{\mathsf{CNOT}}_{B_2}(2,4)\\ \text{Round 5:}& {\mathsf{CNOT}}_{B_3}(1,3),{\mathsf{CNOT}}_{B_3}(2,4)\\ \text{Round 6:}& {\mathsf{CNOT}}_{A_1}(1,2),{\mathsf{CNOT}}_{A_2}(3,4)\\ \text{Round 7:}& {\mathsf{CNOT}}_{A_3}(1,2)\end{array}\text{\hspace{1em}(9)}$$

In the following we apply all seven unitary rounds to verify the correctness of the performed transformation:

$$\text{ Round 1: }\left(\begin{array}{cccc}I& 0& 0& 0\\ 0& A& B& 0\end{array}\right)\stackrel{{\mathsf{CNOT}}_{A_1}(3,4)}{\to }\left(\begin{array}{cccc}I& 0& 0& 0\\ 0& A& B& A_{1}B\end{array}\right)$$ $$\begin{array}{c}\text{Round 2:}\stackrel{{\mathsf{CNOT}}_{A_2}(1,2)}{\to }\left(\begin{array}{cccc}I& A_2& 0& 0\\ 0& A& B& A_{1}B\end{array}\right)\stackrel{{\mathsf{CNOT}}_{A_3}(3,4)}{\to }\left(\begin{array}{cccc}I& A_2& 0& 0\\ 0& A& B& (A_1+A_3)B\end{array}\right)\\ \text{Round 3:}\stackrel{{\mathsf{CNOT}}_{B_2}(1,3)}{\to }\left(\begin{array}{cccc}I& A_2& B_2& 0\\ 0& A& B& (A_1+A_3)B\end{array}\right)\stackrel{{\mathsf{CNOT}}_{B_1}(2,4)}{\to }\left(\begin{array}{cccc}I& A_2& B_2& A_2{B}_1\\ 0& A& B& (A_1+A_3)B+A{B}_1\end{array}\right)\\ \text{Round 4:}\stackrel{{\mathsf{CNOT}}_{B_1}(1,3)}{\to }\left(\begin{array}{cccc}I& A_2& B_1+B_2& A_2{B}_1\\ 0& A& B& (A_1+A_3)B+A{B}_1\end{array}\right)\\ \stackrel{{\mathsf{CNOT}}_{B_2}(2,4)}{\to }\left(\begin{array}{cccc}I& A_2& B_1+B_2& A_2(B_1+B_2)\\ 0& A& B& (A_1+A_3)B+A(B_1+B_2)\end{array}\right)=\left(\begin{array}{cccc}I& A_2& B_1+B_2& A_2(B_1+B_2)\\ 0& A& B& A_{2}B+A{B}_3\end{array}\right)\end{array}$$

Here, we use the identity $(A_1+A_3)B+A(B_1+B_2)=A_{2}B+A{B}_3,$ , which holds since the sum of first summands and second summands on both sides of the equation gives AB, and $AB+AB=0$

$$\begin{array}{c}\text{Round 5:}\stackrel{{\mathsf{CNOT}}_{B_3}(1,3)}{\to }\left(\begin{array}{cccc}I& A_2& B& A_2(B_1+B_2)\\ 0& A& B& A_{2}B+A{B}_3\end{array}\right)\stackrel{{\mathsf{CNOT}}_{B_3}(2,4)}{\to }\left(\begin{array}{cccc}I& A_2& B& A_{2}B\\ 0& A& B& A_{2}B\end{array}\right)\\ \text{Round 6:}\stackrel{{\mathsf{CNOT}}_{A_1}(1,2)}{\to }\left(\begin{array}{cccc}I& A_1+A_2& B& A_{2}B\\ 0& A& B& A_{2}B\end{array}\right)\stackrel{{\mathsf{CNOT}}_{A_2}(3,4)}{\to }\left(\begin{array}{cccc}I& A_1+A_2& B& 0\\ 0& A& B& 0\end{array}\right)\\ \text{Round 7:}\stackrel{{\mathsf{CNOT}}_{A_3}(1,2)}{\to }\left(\begin{array}{cccc}I& A& B& 0\\ 0& A& B& 0\end{array}\right).\end{array}$$

This is the desired transformation.

So far, we have not considered the action of the SC circuit on the logical qubits of the code. Let us show that this action is trivial. Indeed, consider some X-type logical operator $X(v)$ , where $v\in {\mathbb{F}}_2^n$ . Write $\mathbf{v}=\left(\mathbf{u},\mathbf{w}\right)$ where u and w are restrictions of v onto the registers 2 and 3 respectively. Commutativity between $X(v)$ and any Z-type check operator implies

$$uB+wA=0.$$

Here we consider u and w as row vectors. Extending v by zeroes on registers 1 and 4 gives the row vector $(0uw0)$ where 0 stands for the all-zero row vector of length $n/2.$ . Let us follow the same chain of transformations as above starting from the initial vector (0 u w 0). All CNOTs controlled by the register 1, such as ${\mathsf{CNOT}}_{A_2}(1,2)\mathrm{or}{\mathsf{CNOT}}_{B_2}(1,3)$ in Eq. (9), have trivial action on the vector (0 u w 0) since all qubits of the control register are zeroes. Such CNOTs can be omitted. The remaining CNOTs in Eq. (9) such as ${\mathsf{CNOT}}_{A_1}(3,4)$ or ${\mathsf{CNOT}}_{B_1}(2,4)$ map the initial vector $(0uw0)$ to $(0uwt)$ for some vector t since the registers 2 and 3 always serve as the controls and the register 4 always serves as the target. Rounds 1, 2, and 6 in Eq. (9) are equivalent to XORing vectors $w{A}_1,w{A}_3$ , and $w{A}_2$ respectively to the register 4. Rounds 3, 4, and 5 in Eq. (9) are equivalent to XORing vectors $u{B}_1,u{B}_2$ , and $u{B}_3$ respectively to the register 4. Thus

$$t=w(A_1+A_2+A_3)+u(B_1+B_2+B_3)=wA+uB=0.$$

We have shown that the SC circuit maps the vector $(0uw0)$ to itself. Hence the circuit acts trivially on logical X-type operators.

To prove the correctness of Z-checks, observe that Z-checks can be mapped into X-checks by conjugation with Hadamards. When the unitary circuit in Figure 5 is conjugated with Hadamards, this flips controls and targets of all CNOT gates. Thus, to verify Z-checks, it sufices to perform a very similar calculation to the one already shown for X-checks. We omit this calculation here.

The SC circuit shown in Table 5 is not unique in the following sense: we found 935 depth-7 alternatives to the unitary part of the SC circuit via a computer search. These alternatives are obtained from the circuit defined in Eq. (9) by applying the gate layers ${\mathsf{CNOT}}_{A_i}$ and ${\mathsf{CNOT}}_{B_j}$ in a diferent order. In the special case of the [[144, 12, 12]] code, numerical simulations show that all 936 variants of the syndrome cycle give rise to syndrome measuremen circuits with distance $d_{\mathsf{circ}}\le 10$ explaining our focus on a specific circuit Eq. (9) which we conjecture to have distance $d_{\mathsf{circ}}=10$ . The short depth of the single cycle, relying on only seven computational stages, helps to keep the spread of errors under control. Details of calculating upper bounds on the circuit-level distance are provided in Section 6.

6 Decoder for the circuit-based noise model

So far we assumed that the SM circuit is noiseless. As shown in Section 5, in this case all measured syndromes are zero and the circuit implements the logical identity gate. Consider now what happens when each operation in the circuit including CNOT gates, qubit initializations, measurements, and idle qubits is subject to noise. To enable eficient decoding and numerical simulations, we use the standard circuit-based depolarizing noise model [22]. It assumes that each operation in the circuit is ideal or faulty with the probability 1 − p or p respectively. Here p is a model parameter called the error rate. Faults on diferent operations occur independently. We define faulty operations as follows. A faulty CNOT is an ideal CNOT followed by one of 15 non-identity Pauli errors on the control and the target qubits picked uniformly at random. A faulty initialization prepares a single-qubit state orthogonal to the correct one. A faulty measurement is an ideal measurement followed by a classical bit-flip error applied to the measurement outcome. A faulty idle qubit sufers from a Pauli error X or Y or Z picked uniformly at random.

To perform error correction one needs a decoder — a classical algorithm that takes as input the measured error syndrome and outputs a guess of the final Pauli error on the data qubits resulting from all faults in the SM circuit The error syndrome may itself be faulty due to measurement errors. The decoder succeeds if the guessed Pauli error coincides with the actual error up to a product of check operators. In this case the guessed and the actual error have the same action on any logical state.

Let us show how to adapt Belief Propagation with an Ordered Statistics postprocessing step Decoder (BP-OSD) proposed in [36, 51] to the circuit-based noise model. The decoder consists of two stages. The first stage takes as input a BB code $\mathsf{QC}(A,B)$ equipped with a SM circuit U and an error rate p. It outputs a certain linearized noise model that ignores possible cancellations between errors generated by two or more faulty operations in U. This stage is analogous to computing the decoding graph in error correction algorithms based on the surface code [57, 58]. The second (online) stage of the decoder takes as input an error syndrome measured in the experiment and outputs a guess of the final error on the data qubits. This stage decodes the linearized noise model using BP-OSD method [36, 51]. Our linearized noise model is conceptually similar to spacetime codes studied by Delfosse and Paetznick [47] and detector-based noise model proposed by McEwen, Bacon, and Gidney [48]. The online stage of our decoder closely follows Refs. [49, 50]. In particular, Geh´er, Crawford, and Campbell [50] applied BP-OSD to study tangled syndrome measurement circuits capable of measuring certain non-local check operators on a hardware with short-range qubit connectivity. Higgott et al [49] showed that the performance of the standard minimum-weight matching decoder ca be enhanced by computing prior error probabilities using BP-decoder as a preprocessing step.

We begin by describing the ofline stage. Consider a BB code with parameters $[[n,k,d]]$ and let U be the SM circuit constructed in Section 5 with $N_c$ syndrome cycles. The circuit U contains 6n $N_{c}C\mathsf{NOTs},n{N}_c$ initializations and measurements, and 2n $N_c$ idle qubit locations. Let ${\mathcal{U}}_1,{\mathcal{U}}_2,\dots ,{\mathcal{U}}_M$ be the list of all possible faulty realizations of U with exactly one faulty operation. If the faulty operation happens to be CNOT or an idle qubit, one of the admissible Pauli errors for this operation is specified. A simple counting shows that $M=98n{N}_c$ , where $98=15\cdot 6+1+1+3\cdot 2$ accounts for 15 noisy realizations of each CNOT, 3 realizations of memory errors on idle qubits, noisy initializations and measurements. By definition, the list ${\mathcal{U}}_1,{\mathcal{U}}_2,\dots ,{\mathcal{U}}_M$ includes all realizations of U that can occur with the probability $O(p)$ in the limit $p0$ . We simulate each circuit $u_j$ by propagating the chosen Pauli error towards the final time step taking into account qubit initialization and measurement errors (if any). This simulation can be performed eficiently using the stabilizer formalism. Let $s_j^U\in \{0,1{\}}^{n{N}_c}$ be the full measured syndrome of ${\mathcal{U}}_j$ and $E_j$ be the final n-qubit Pauli error on the data qubits generated by ${\mathcal{U}}_j$ . Let $s_j^F\in \{0,1{\}}^r$ be the syndrome of the final error $E_j$ . In other words, if we write $E_j=X({\alpha }_j)Z({\beta }_j)$ for some vector $\overline{{\alpha }_j},{\beta }_j\in \{0,1{\}}^n$ , then

$$s_j^F=\left[\begin{array}{l}{H}^Z{\alpha }_j\\ H^X{\beta }_j\end{array}\right].$$

Here $H^X$ and $H^Z$ are the check matrices of the chosen code. Finally, let $s_j^L\in \{0,1{\}}^{2k}$ be a logical syndrome of the final error $E_j$ defined as follows. Fix some basis set of logical Pauli operators ${\overline{P}}_1,{\overline{P}}_2,\dots ,{\overline{P}}_{2k}$ for the chosen code. For example, ${\overline{P}}_1,{\overline{P}}_2,\dots ,{\overline{P}}_k$ could be logical X-type operators and ${\overline{P}}_{k+1},{\overline{P}}_{k+2},\dots ,{\overline{P}}_{2k}$ could be logical Z-type operators. The i-th bit of $s_j^L$ is defined as

$$(s_j^L{)}_i=\{\begin{array}{ll}1& \text{if}{E}_j{\overline{P}}_i=-{\overline{P}}_i{E}_j,\\ 0& \text{if}{E}_j{\overline{P}}_i={\overline{P}}_i{E}_j,\end{array}$$

for $i=1,\dots ,2k$ . Note that the pair of syndromes $s_j^F,s_j^L$ uniquely determines the final error $E_j$ modulo check operators. Define a pair of decoding matrices $D$ and $D^L$ of size $(n{N}_c+n)\times M$ and $2k\times M$ respectively such that the j-th column of D is

$$\left[\begin{array}{l}{s}_j^U\\ s_j^F\end{array}\right]$$

and the j-th column of $D^L$ is $s_j^L$ . Let $p_j$ be the probability of a Pauli error that occurred in the circuit ${\mathcal{U}}_j$ . We have $p_j=p/15$ if ${\mathcal{U}}_j$ contains a faulty CNOT, $p_j=p/3$ if ${\mathcal{U}}_j$ contains a faulty idle qubit, and $p_j=p$ if ${\mathcal{U}}_j$ contains a faulty qubit initialization or measurement. Suppose $I\subseteq \{1,2,\dots ,M\}$ is a subset of columns of $D$ such that triples of syndromes $(s_j^U,s_j^F,s_j^L)$ ) are the same for all $j\in I$ . We merge all columns in I to a single column and assign the value ${\sum }_{j\in I}{p}_j$ to the bit-flip error probability associated with the merged column. Let M be the number of columns of D after the merging step and $p_1,p_2,\dots ,p_M$ be the respective error probabilities.

Next, the decoding matrix D is converted to a sparse form. To this end consider a faulty circuit ${\mathcal{U}}_j$ and a sequence of syndromes measured by ${\mathcal{U}}_j$ on some check operator. Let this sequence be $m=(m_1,m_2,\dots ,{\bar{m}}_{N_c})\in \{0,1{\}}^{N_c}$ Since ${\mathcal{U}}_j$ contains a single fault, the sequence m has only a few locations where the measured syndromes difer at two consecutive cycles. For example, if ${\mathcal{U}}_j$ contains a Pauli error on some idle data qubit between two syndrome cycles, the m-sequence may look as $(0,0,\dots ,0,1,1,\dots ,1)$ . Such sequence can be made sparse if we represent it by a binary vector

$$m^{\prime }=\left(m_1,m_2\oplus m_1,m_3\oplus m_2,\dots ,m_{N_c}\oplus m_{N_c-1}\right)\in \{0,1{\}}^{N_c}.$$

In other words, $m^{\prime }$ stores changes in the measured syndrome at a given check operators at each cycle. We convert the matrix D to a sparse form by applying the map $m{m}^{\prime }$ to the syndromes measured by each check operator for each faulty circuit ${\mathcal{U}}_j$

Let ${\xi }_1,{\xi }_2,\dots ,{\xi }_M\in \{0,1\}$ be independent random variables such that ${\xi }_j$ takes values 0 and 1 with the probability $1-p_j$ and $p_j$ respectively. Define a linearized noise model that outputs a random triple $(s^U,s^F,E)$ , where

$$E=\prod _{j=1}^M(E_j{)}^{{\xi }_j}$$

is an n-qubit Pauli error and

$$\left[\begin{array}{c}{s}^U\\ s^F\end{array}\right]=\sum _{j=1}^M{\xi }_j\left[\begin{array}{c}{s}_j^U\\ s_j^F\end{array}\right](\mathrm{mod}2)$$

is a binary vector that represents the error syndrome. The linearized model is a simplified version of the circuit-based noise that ignores possible cancellations among errors generated by two or more faulty operations in U. Note that such errors occur with the probability only $O(p^{\bar{2}})$ . The decoder attempts to guess the final error E acting on the data qubits based on the syndrome $s^U$ measured in the experiment making a simplifying assumption that that the pair $(s^U,E)$ was generated using the linearized noise model. We additionally assume that the decoder knows the syndrome $s^F$ of the final error E. This syndrome can be acquired by adding one noiseless cycle at the end of the syndrome measurement circuit, which is a common practice in numerical simulations of error correction. By definition, we have

$$D\xi =\left[\begin{array}{c}{s}^U\\ s^F\end{array}\right].$$

Here $\mathbf{\xi }=({\xi }_1,{\xi }_2,\dots ,{\xi }_M)$ is a column vector and matrix-vector multiplication is modulo two. Define a minimum weight error ${\xi }^{\ast }={\xi }^{\ast }(s)\in \{0,1{\}}^M$ as a solution of an optimization problem

$${\xi }^{\ast }=\arg \underset{\xi \in \{0,1{\}}^M}{\min }\sum _{j=1}^M\log (1/p_j){\xi }_j\text{subject to}D\xi =\left[\begin{array}{c}{s}^U\\ s^F\end{array}\right].\text{\hspace{1em}(10)}$$

This problem is equivalent to the minimum weight decoding for a length-M linear code with the check matrix $D,$ bit-flip error probabilities $p_1,p_2,\dots ,p_M$ , and noiseless syndromes. Our guess of the unknown logical syndrome is

$$s^L=D^L{\xi }^{\ast }.$$

Let $E^{\ast }$ be any n-qubit Pauli operator with the syndrome $s^F$ and the logical syndrome $s^L$ . Note that $E^{\ast }$ is defined uniquely modulo multiplication by check operators. The Pauli $E^{\ast }$ is our guess of the final error on the data qubits. Let $E$ be the actual final error on the data qubits generated by a noisy realization of U without making any simplifications of the noise model. By definition, Pauli operators $E$ and $E^{\ast }$ have the same syndrome but they may difer by a logical Pauli operator. We declare a logical error if E and $E^{\ast }$ difer by any non-identity logical operator (there are $4^k-1$ choices of this logical operator). Otherwise the decoding is deemed successful.

It remains to explain how to solve the optimization problem Eq. (10). Since the minimum weight decoding for a linear code is known to be NP-hard problem [59], finding the exact solution of Eq. (10) might be practically impossible for problem instances with several thousand variables that we have to deal with. Furthermore, estimation of the logical error probability $p_L$ by the Monte Carlo method requires solving $O(1/p_L)$ instances of the problem Eq. (10) This number can be quite large since $p_L$ is a small parameter. To address these challenges, we employ the BP-OSD algorithm [36, 51]. Recall that belief propagation (BP) is a heuristic message passing algorithm aimed at computing single-bit marginals of a probability distribution

$$P(\xi |\sigma )=\{\begin{array}{cc}\frac{1}{\mathcal{Z}}{\prod }_{j=1}^M(1-p_j{)}^{1-{\xi }_j}{p}_j^{{\xi }_j}& \text{if}D\xi =\sigma ,\\ 0& \text{otherwise}.\end{array}$$

Here $\xi \in \{0,1{\}}^M$ and $\mathcal{Z}$ is a normalization factor chosen such that $\begin{array}{r}{\sum }_{\xi \in \{0,1{\}}^M}P(\xi |\sigma )=1\end{array}$ . In our case $\xi$ represents an unknown error in the linearized noise model, D is the decoding matrix constructed above, and $\mathbf{\sigma }=\lceil \begin{array}{l}{s}^U\\ s^F\end{array}\rceil$ is the measured error syndrome. Let $q_j\in [0,1]$ be an estimate of the marginal probability $\mathrm{Pr}[{\xi }_j=1]$ obtained by the belief propagation method with some fixed number of message passing iterations. The ordered statistics post-processing step examines information sets which are subsets of bits $I\subseteq [M]$ such that the linear system $D\xi =\sigma$ has a unique solution ξ supported on I, that is, ${\xi }_j=0$ for all $j\notin I.$ Information sets are ranked according to their reliability which is defined as

$$\rho (I)=\prod _{j\in I}\max \left(q_j,1-q_j\right).$$

BP-OSD finds an information set I with the largest reliability using a greedy algorithm [36]. The final output of BP-OSD is a solution of the system $D\xi =\sigma$ supported on the most reliable information set I. We replace the minimum weight error ${\xi }^{\ast }$ in Eq. (10) by the solution $\xi$ proposed by BP-OSD.

Since BB LDPC codes are of CSS-type, it is natural to decode X-type and Z-type errors independently. Accordingly, we solve the minimum weight decoding problem Eq. (10) twice with a pair of decoding matrices $D_X$ and $D_Z$ constructed as above but including only the syndromes of $X-\mathrm{type}$ and $Z-\mathrm{type}$ check operators respectively. This results in guessed $X-\mathrm{type}$ and $Z-\mathrm{type}$ errors $E_X^{\ast }$ and $E_Z^{\ast }$ . The guessed final error is $E^{\ast }=E_X^{\ast }{E}_Z^{\ast }$ . We empirically observed that the resulting decoding matrices $D_X$ and $D_Z$ are (6, 35)-sparse for any BB code, meaning that there are at most 6 nonzeros in each column and at most 35 nonzeros in each row of $D_X$ and $D_Z$ . The number of columns scales as $O(n{N}_c)$ where the constant coeficient depends on a particular code. For example, decoding matrices $D_X$ and $D_Z$ describing the code [[144, 12, 12]] with $N_c=12$ syndrome cycles have 8857 and 8785 columns respectively.

We also employed BP-OSD to compute an upper bound on the code distance $d.$ Consider a CSS-type LDPC code $[[n,k,d]]$ with check matrices $H^X$ and $H^Z$ . Assume for simplicity that this code has the same distance for Xand Z-type errors (this assumption is satisfied for BB LDPC codes due to Lemma 1). Suppose $Z(\xi )$ is a minimum weight logical Z-type operator. Then $\xi \in \mathsf{ker}(H^X)$ and $\xi \notin \mathsf{rs}(H^Z)$ . Let $X(\eta )$ be any logical X-type operator. Here $\eta \in \mathsf{ker}(\overline{H^Z})\setminus \mathsf{rs}(\overline{H^X})$ . Consider the following optimization problem:

$$d(\eta )=\underset{\xi \in \ker (H^X)}{\min }\sum _{j=1}^n{\xi }_j\text{ subject to }{\eta }^T\xi =1.\text{\hspace{1em}(11)}$$

Then $d(\eta )\ge d$ for any logical operator $X(\eta )$ and $d(\eta )=d\mathrm{if}X(\eta )$ anti-commutes with some minimum-weight logical operator $Z(\xi )$ . The latter event occurs with the probability $1/2$ if one picks $\eta \in \mathsf{ker}(H^Z)$ uniformly at random. In this case $d(\eta )=d$ with the probability at least $1/2$ and $d(\eta )\ge d$ with certainty. Let $d^{\mathsf{BP}}(\eta )$ be an upper bound on $d(\eta )$ obtained by solving the optimization problem Eq. (11) using BP-OSD method with a parity check matrix $\left[\begin{array}{c}{H}^X\\ {\eta }^T\end{array}\right]$ and a syndrome $(0,0,\dots ,0,1{)}^T$ . We have $d^{\mathsf{BP}}(\eta )\ge d$ with certainty and $d^{\mathsf{BP}}(\eta )=d$ with the probability $1/2$ whenever BP-OSD finds the optimal solution. Choose the number trials $T\gg 1$ and pick vectors ${\eta }^1,{\eta }^2,\dots ,{\eta }^T\in \ker (H^Z)\setminus \mathfrak{rs}(H^X)$ uniformly at random. Then

$$d^{\mathsf{BP}}:=\underset{a=1,2,\dots ,T}{\min }{d}^{\mathsf{BP}}({\eta }^a)$$

is an upper bound on the distance d that can be systematically improved by increasing the number of trials $T.$

Using the quantity $d^{\mathsf{BP}}$ as an eficiently computable proxy for the code distance enabled us to search over a large number of candidate BB codes with $n=O(100)$ qubits. The vast majority of these candidates was discarded due to an insuficiently large upper bound $d^{\mathsf{BP}}$ . This left only a few viable candidates with a suficiently large value of $d^{\mathsf{BP}}$ The actual distance of each candidate code was computed using the integer linear programming method [55].

We similarly computed an upper bound on the circuit-level distance $d_{\mathsf{circ}}$ . Since the SM circuit can break the symmetry between X- and Z-type errors, the circuit-level distance has to be computed for both types of errors. For concreteness, let us discuss the circuit-level distance $d_{\mathsf{circ}}^Z$ for Z-type errors. The latter is defined as the minimum number of faulty operations in the SM circuit that can generate an undetectable Z-type logical error. The optimization problem Eq. (11) is replaced by

$$d_{\mathsf{circ}}^Z(\eta )=\underset{\xi \in \ker (D_X)}{\min }\sum _{j=1}^M{\xi }_j\text{ subject to }{\eta }^T\xi =1,\text{\hspace{1em}(12)}$$

where $D_X$ is the decoding matrix constructed above and $\eta \in \{0,1{\}}^M$ is a random linear combination of rows of $D_X$ and rows of $D_L$ that represent logical X-type operators. Then $d_{\mathsf{circ}}(\eta )\ge d_{\mathsf{circ}}^Z$ with certainty and $d_{\mathsf{circ}}(\eta )=d_{\mathsf{circ}}^Z$ with the probability at least $1/2$ . Solving the optimization problem Eq. (12) using BP-OSD method for many random choices of the vector η and taking the minimum value of $d_{\mathsf{circ}}^Z(\eta )$ provides an upper bound on $d_{\mathsf{circ}}^Z$ . One can similarly compute an upper bound on the circuit-level distance $d_{\mathsf{circ}}^X$ for X-type errors. This provides an upper bound on $d_{\mathsf{circ}}=\min \left(d_{\mathsf{circ}}^X,d_{\mathsf{circ}}^Z\right)$

7 Proof of Lemma 1

For convenience of the reader we restate the lemma below.

Lemma 1. The code $\mathsf{QC}(A,B)$ has parameters $[[n,k,d]]$ , where

$$n=2\ell m,k=2\cdot \dim (\ker (A)\cap \ker (B)),andd=\min \left\{|v|:v\in \ker \left(H^X\right)\backslash \mathrm{rs}\left(H^Z\right)\right\}.$$

The code ofers equal distance for X-type and Z-type errors.

Proof. It is known [44, 45] that

$$k=n-\mathsf{rk}(H^X)-\mathsf{rk}(H^Z).$$

We claim that rk $(H^X)=\mathsf{rk}(H^Z)$ . Indeed, define a self-inverse permutation matrix $C_{\ell }$ of size $\ell \times \ell$ such that the ith column of $C_{\ell }$ has a single nonzero entry equal to one at the row $j=-i$ (mod ℓ). Define $C_m$ similarly and let $\mathcal{C}={\mathcal{C}}_{\ell }\otimes {\mathcal{C}}_m$ . Since $C_{\ell }{S}_{\ell }{C}_{\ell }=S_{\ell }^T$ and $C_m{S}_m{C}_m=S_m^T$ , one gets

$$A^T=CAC\text{ and }{B}^T=CBC.\text{\hspace{1em}(13)}$$

Therefore one can write

$$H^Z=[B^T|A^T]=[CBC|CAC]=C[A|B]\left[\begin{array}{ll}0& C\\ C& 0\end{array}\right]=C{H}^X\left[\begin{array}{ll}0& C\\ C& 0\end{array}\right].$$

Thus $H^Z$ is obtained from $H^X$ by multiplying on the left and on the right by invertible matrices. This implies $\mathsf{rk}(H^X)=\mathsf{rk}(H^Z)$ . Therefore

$$\begin{array}{l}k=n-2\cdot \mathrm{rk}(H^Z)=n-2(\frac{n}{2}-\dim \left(\ker ((H^Z{)}^T))\right))=n-2(\frac{n}{2}-\dim \left(\ker (A)\cap \ker (B)\right))\\ =2\cdot \dim \left(\ker (A)\cap \ker (B)\right).\end{array}$$

Here we noted that $H^Z$ has size $(n/2)\times n$ and ke $\cdot ((H^Z{)}^T))=\mathsf{ker}(A)\cap \mathsf{ker}(B)$ since $H^Z=\lceil B^T|A^T|$

It is known [44, 45] that a CSS code with check matrices $H^X$ and $H^Z$ has distance $d=$ min $({\bar{d}}^X,d^Z)$ , where $d^X$ and $d^Z$ are the code distances for X-type and Z-type errors defined as

$$d^X=\min \left\{|v|:v\in \ker (H^Z)\backslash \mathrm{rs}(H^X)\right\}\text{ and }{d}^Z=\min \left\{|v|:v\in \ker (H^X)\backslash \mathrm{rs}(H^Z)\right\}.$$

We claim that $d^Z\le d^X$ . Indeed, let $\begin{array}{r}X(f)={\prod }_{j=1}^n{X}_j^{f_j}\end{array}$ be a minimum weight logical X-type Pauli operator such that $|f|=d^X$ . Then $H^{Z}f=0$ and $f\notin \mathsf{rs}(H^X)$ . Thus there exists a logical Z-type operator $\begin{array}{r}Z(g)={\prod }_{j=1}^n{Z}_j^{g_j}\end{array}$ anti-commuting with $X(f)$ . In other words, $H^{X}g=0$ and $f^{T}g=1$ . Here, f and g are length-n binary vectors. Write $f=(\alpha ,\beta )$ and $g=\left(\gamma ,\delta \right)$ , where $\alpha ,\beta ,\gamma ,\delta$ are length-(n/2) vectors. Conditions $H^{Z}f=0$ and $H^{X}g=0$ are equivalent to

$$B^T\alpha =A^T\beta \mathrm{and}A\gamma =B\delta .\text{\hspace{1em}(14)}$$

Here and below all arithmetics is modulo two. Define length-n vectors

$$e=(C\delta ,C\gamma )\text{ and }h=(C\beta ,C\alpha ).\text{\hspace{1em}(15)}$$

From Eqs. (13,14) one gets

$$H^{X}h=[A|B]\left[\begin{array}{l}C\beta \\ C\alpha \end{array}\right]=AC\beta +BC\alpha =C(A^T\beta +B^T\alpha )=0.$$

Likewise,

$$H^{Z}e=[B^T|A^T]\left[\begin{array}{l}C\delta \\ C\gamma \end{array}\right]=B^{T}C\delta +A^{T}C\gamma =C(B\delta +A\gamma )=0.$$

Furthermore,

$$h^{T}e={\beta }^{T}CC\delta +{\alpha }^{T}CC\gamma ={\beta }^T\delta +{\alpha }^T\gamma =f^{T}g=1.$$

Thus $X(e)$ and $Z(h)$ are non-identity logical operators. It follows that $d^Z\le |h|$ . We get

$$d^Z\le |h|=|C\beta |+|C\alpha |=|\beta |+|\alpha |=|f|=d^X.$$

Thus $d^Z\le d^X$ . Similar argument shows that $d^X\le d^Z$ , that is, $d^X=d^Z$

We note that the equality $d^X=d^Z$ can also be established using the machinery of Ref. [54] by viewing $\mathsf{QC}(A,B)$ as a Lifted Product code.

8 Numerical simulation details

Data reported in Figure 2 A) was generated using BP-OSD software developed by Rofe et al. [51, 60]. The decoder wa extended to the circuit-based noise model as described in Section 6. The simulations were performed using MIN-SUM belief propagation with the limit of 10, 000 iterations and combination sweep version of OSD, as described in [51]. All data points except for those with the smallest error rate accumulated at least 100 logical errors to estimate the logica error rate $p_L$ with the error bars $\approx p_L/10$ . The fitting formula $p_L(p)=p^{d_{\mathrm{circ}}/2}{e}^{c_0+c_{1}p+c_2{p}^2}$ with fitting parameters $c_0,c_1,c_2$ was proposed in [61] in the context of surface code simulations. We observed that the same fitting formula works well for BB LDPC codes. The fitting parameters $c_i$ of the considered codes are provided in Table 6. We note that the logical error rate achieved by the combination of a distance-preserving SM circuit and an optimal decoder is expected to follow an exponential decay $p_L(p)=\exp [-d\cdot f(p)]$ ], where $f(\mathbf{p})$ is an unknown function such that $f(\mathbf{p})>0$ in the sub-threshold regime. The function $f(\mathbf{p})$ must have a logarithmic singularity $f(p)\approx -(1/2)$ log p for small p since one expects degree- $(d/2)$ error suppression for a distance-d code. The fitting formula for $p_L(p)$ approximates the remaining non-singular terms in $f(\mathbf{p})$ by a low-degree polynomial in p. Coeficients of the polynomial are considered as fitting parameters. Since our SM circuit is not distance-preserving, the code distance d in the fitting formula of Ref. [61] is replaced by the circuit-level distance $d_{\mathsf{circ}}$

[[n,k,d]]	$c_0$	$c_1$	$c_2$
[[72,12,6]]	11.09	365.6	-16088
[[90,8,10]]	15.08	524.8	-12670
[[108,8,10]]	13.91	895	-46137
[[144,12,12]]	18.04	1337	-96007
[[288,12,18]]	32.04	3522	-294482

Table 6: Parameters $c_0,c_1,c_2$ in the fitting formula $p_L(p)=p^{d_{\mathrm{circ}}/2}{e}^{c_0+c_{1}p+c_2{p}^2}$ for BB LDPC codes shown in Table 1.

Surface code data reported in Figure 2 B) was generated using software developed by one of the authors and Alexander Vargo in [61]. The simulation was performed for the rotated surface code with parameters $[[d^2,1,d]]$ , where $d\in \{9,11,13,15\}$ , and the standard SM circuit [22]. Let $P_{L,\cdot }$ ₁ be the logical error probability for the surface code encoding one logical qubit and SM circuit with $N_c=d$ syndrome cycles. Encoding $k=12$ logical qubits into 12 separate patches of the surface code results in a logical error probability

$$P_{L,12}=1-(1-P_{L,1}{)}^{12}.$$

Figure 2 B) shows the logical error rate $p_L$ defined as the logical error probability per syndrome cycle,

$$p_L=1-(1-P_{L,12}{)}^{1/N_c}=1-(1-P_{L,1}{)}^{12/d}.$$

9 Logical memory capabilities

In this section we give evidence that BB LDPC codes have the required features for an efective quantum memory or storage unit. Although there are few ways of performing computations on stored qubits, there are fault tolerant operations for initialization and measurement of individual qubits, and most importantly transfer of data into and out of the code via quantum teleportation. These capabilities are based on a combination of two diferent techniques First, we follow [62] to derive fault tolerant unitary operations that require only the connectivity already necessary to perform syndrome measurements. Second, we give low-overhead extensions of the Tanner graph based on work by [46] which enable measurement of a single logical operator while preserving the thickness-2 implementability criterion. Together, these capabilities allow us to address any logical qubit.

A conceptual representation of the logical operators is shown in Figure 6. We first derive logical Pauli operators for BB LDPC codes, and find that the logical qubits divide into an “unprimed” and a “primed” block with equal size and symmetrical structure. We visualize the primed and unprimed block as two sheets featuring a 2D grid of logical operators. Some of these grid cells contain one of the $k/2$ logical qubits per sheet.

Next, we show that there exists a set of fault tolerant depth-four circuits that implement a small family of commut ing logical CNOT circuits. These gates are based on automorphisms of the code: permutations of the data qubits that commute with the stabilizer. Based on their group structure we can think of the automorphism gates as translations of a 2D grid of operators within each of the primed and unprimed blocks. Furthermore, we follow [62] to derive a fault tolerant operation based on a ZX-duality that also allows us to swap the two blocks while also applying Hadamard gates to all qubits.

Finally, we show how to leverage techniques from [46] to extend the Tanner graph to a larger Tanner graph allowing fault-tolerant measurement of one logical X and one logical Z operator. Various subgraphs of this extended Tanner graph contain either this logical X or Z operator as a stabilizer. This construction acts as a “probe” that gives us access to one of the logical qubits.

Measurements of both logical X and Z operators on any qubit can be realized by conjugating this measurement by gates based on automorphisms and the ZX-duality. We can think of this as shifting any desired qubit to be the target of the probe using translation and exchange of the two blocks.

Logical X and Z measurement of any logical qubit also enables transfer of data into and out of the code using a teleportation circuit. This teleportation can be realized through a product measurement of the logical Pauli in the BB code, and a logical Pauli in another quantum error correction code. While the Tanner graph of the BB code demands thickness-2, we show how the ancilla system corresponding to the logical X measurement can be implemented in an “efectively planar” Tanner graph. This makes it possible two connect this ancilla system to another quantum error correction code, like a surface code, within a thickness-2 implementation. This capability indicates the suitability of BB LDPC codes as a fault tolerant quantum memory.

On the other hand, this construction incurs rather significant resource overhead that undercuts the compactness of the error correction codes introduced in this paper. For example, to equip the [[144, 12, 12]] code with ancilla systems capable of measuring X and $Z,$ we require $2\times 30\times (2d-1)=1380$ additional qubits on top of the original 288. However, the argument for fault-tolerance from [46] is designed to be very broadly applicable, and hence may demand excessively many resources for any particular error correction code. We consider it very likely that the size of these systems can be significantly reduced. We leave resource optimization of this scheme for future work.

9.1 Logical Pauli Operators

In this section we derive that the logical Pauli matrices of BB LDPC codes split into a “primed” and an “unprimed” block with $|\mathcal{M}|=$ ℓm many X operators and Z operators each. Operators in the primed block commute with operators in the unprimed block, and the two blocks have identical commutation structure.

We begin by introducing some new notation for Pauli matrices acting on the data qubits. We denote with ${\mathbb{F}}_2^{\mathcal{M}}$ the set of polynomials over ${\mathbb{F}}_2$ with monomials from M. This is equivalent to the quotient ring obtained from ${\mathbb{F}}_2[x,y]$ by identifying $x^{\ell }=y^m=1$ . With $x=S_m\otimes I$ and $y=I\otimes S_{\ell }$ , the elements of ${\mathbb{F}}_2^{\mathcal{M}}$ have natural matrix representations, and can also be interpreted as sets since the coeficient on any particular $x\in \mathcal{M}$ is either 0 or 1.

Figure 6: Conceptual diagram depicting the manner by which logical operators can be loaded into and out of a BB LDPC code. In Subsection 9.1 we derive that there are two blocks of logical Pauli operators corresponding to a 2d grid. Some subset of these grid elements can be chosen as logical qubits (large dots) and the other elements correspond to various Pauli products (small dots). In Subsection 9.2 we show that there are fault tolerant logical gates based on automorphisms that translate the grid of operators within each block, and in Subsection 9.3 we give a fault tolerant gate based on a ZX-duality [62] that swaps the two blocks. Finally, in Subsection 9.4 we show that there exists an ancilla system based on [46] that can measure one logical X operator. We can think of this system as a probe that can access one logical qubit. Together, these operations allow external access of every logical qubit and many of thei products.

For $P,Q\in {\mathbb{F}}_2^{\mathcal{M}}$ , we can consider the set of qubits $q(L,\alpha )$ for $\alpha \in P$ and $q(R,\beta )$ for $\beta \in Q$ . We write $X(P,Q)$ to denote a Pauli matrix acting as X on this collection of qubits, and identity elsewhere. Similarly, $Z(P,Q)$ denotes Z acting on $q(L,\alpha )$ for $\alpha \in P$ and $q(R,\beta )$ for $\beta \in Q$ . For example, we can recall that $q(L,\beta )$ is connected to $q(X,\alpha )$ whenever $\beta \in A\alpha .$ , and see that the stabilizer corresponding to $q(X,\alpha )$ becomes $X(\alpha A,\alpha B)$ . Similarly, the stabilizer corresponding to $q(Z,\alpha )$ can be written as $\mathbf{Z}(\alpha B^T,\bar{\alpha }{\mathbf{A}}^T)$ . There is also the following useful fact:

Lemma 2. $X(P,Q)$ anticommutes with $Z(\bar{P},\bar{Q})$ if and only if $1\in P{\bar{P}}^T+Q{\bar{Q}}^T$

Proof. Write

$$P=\sum _{\alpha \in \mathcal{M}}{p}_{\alpha }\alpha ,\bar{P}=\sum _{\alpha \in \mathcal{M}}{\bar{p}}_{\alpha }\alpha ,Q=\sum _{\alpha \in \mathcal{M}}{q}_{\alpha }\alpha ,\bar{Q}=\sum _{\alpha \in \mathcal{M}}{\bar{q}}_{\alpha }\alpha ,$$

where $p_{\alpha },{\bar{p}}_{\alpha },q_{\alpha },{\bar{q}}_{\alpha }\in {\mathbb{F}}_2$ are coeficients. Pauli operators $X(P,Q)$ and $Z(\bar{P},\bar{Q})$ overlap on a qubit $q(L,\alpha )$ if $p_{\alpha }{\bar{p}}_{\alpha }=1$ and overlap on a qubit $q(R,\alpha )$ if $q_{\alpha }{\bar{q}}_{\alpha }=1$ . Thus $X(P,Q)$ and $\bar{Z}(\bar{P},\bar{Q})$ anti-commute if ${\sum }_{\alpha \in \mathcal{M}}{p}_{\alpha }{\bar{p}}_{\alpha }+q_{\alpha }{\bar{q}}_{\alpha }$ is odd. We have

$$P{\bar{P}}^T=\sum _{\alpha \in \mathcal{M}}{p}_{\alpha }{\bar{p}}_{\alpha }1+\dots \text{ and }Q{\bar{Q}}^T=\sum _{\alpha \in \mathcal{M}}{q}_{\alpha }{\bar{q}}_{\alpha }1+\dots$$

where dots represent all monomials diferent from 1. By linearity,

$$P{\bar{P}}^T+Q{\bar{Q}}^T=\sum _{\alpha \in \mathcal{M}}(p_{\alpha }{\bar{p}}_{\alpha }+q_{\alpha }{\bar{q}}_{\alpha })1+\dots .$$

Thus $X(P,Q)$ and $Z(\bar{P},\bar{Q})$ anti-commute if $P{\bar{P}}^T+Q{\bar{Q}}^T$ contains the monomial 1.

Without loss of generality, we can express logical Pauli matrices as either $X(P,Q)$ or $Z(Q^T,P^T)$ via a choice of $P,Q\in {\mathbb{F}}_2^{\mathcal{M}}$ . The operator $X(P,Q)$ commutes with the stabilizer $Z(\alpha B^T,\alpha A^T)$ whenever $1\notin \dot{P}(\alpha B^T{)}^T+Q(\alpha A^T{)}^T=$ ${\alpha }^T(PB+QA)$ . This is equivalent to α $\notin PB+QA$ . Since we must have α $\notin PB+QA$ for all α, we see that $X(P,Q)$ commutes with the stabilizer whenever $PB+QA$ vanishes. Similarly we can derive that $Z(Q^T,P^T)$ commutes with the stabilizer when $PB+QA=0$

We aim to construct a family of solutions to $PB+QA=0$ which give rise to a basis of logical qubits defined by a set of operators $\{{\bar{X}}_1,{\bar{X}}_2,...,{\bar{Z}}_1,{\bar{Z}}_2,...\}$ with the correct commutation relations. To do so, let us make some observations about Pauli operators defined via solutions to $PB+QA=0$ . First, if $P,Q$ are a solution, then so are $\alpha P,\alpha Q$ for any $\alpha \in \mathcal{M}$ , so each $P,Q$ immediately gives rise to a family of $|\mathcal{M}|=lm$ logical operators for both X and Z. Second, consider using the same $P,Q$ to define both $X(\alpha P,\alpha Q)$ and $\dot{Z}(\beta {\dot{Q}}^T,\beta P^T)$ . Then these operators always commute because $\beta {\alpha }^T\in PQ+QP=0$ never holds. So we require at least two solutions to $PB+QA=0$ to define a set of operators with nontrivial commutation relations.

For reasons described later in Subsection 9.4, we would like a logical X operator with no support on $q(R)$ . To this end, we select $f,g,h\in {\mathbb{F}}_2^{\mathcal{M}}$ that satisfy $Bf=0$ and $gB+hA=0$ , yielding two solutions to the equation $PB+QA=0$ with $P,Q=f,0$ and $P,Q=g,h$ . These yield the following family of logical operators for all $\alpha \in \mathcal{M}$ :

$$\begin{array}{ll}{\bar{X}}_{\alpha }:=X(\alpha f,0)& {\bar{Z}}_{\alpha }:=Z(\alpha h^T,\alpha g^T)\\ {\bar{X}}_{\alpha }^{\prime }:=X(\alpha g,\alpha h)& {\bar{Z}}_{\alpha }^{\prime }:=Z(0,\alpha f^T)\end{array}\text{\hspace{1em}(16)}$$

For all $\alpha ,\beta .$ , we see that ${\bar{X}}_{\alpha },{\bar{Z}}_{\beta }^{\prime }$ always commute because $f{0}^T+0f^T=0.$ , and ${\bar{X}}_{\beta }^{\prime },{\bar{Z}}_{\alpha }$ always commute because $gh+hg=0$ . Furthermore, ${\bar{X}}_{\alpha },{\bar{Z}}_{\beta }$ and ${\bar{X}}_{\alpha }^{\prime },{\bar{Z}}_{\beta }^{\prime }$ form anticommuting pairs when ${\alpha }^T\beta \in fh$ . We see that we have constructed two independent blocks of logical operators with symmetrical structure. It follows that each of these blocks must contain a set of operators that define $k/2$ qubits. We name these the “unprimed” and “primed” logical blocks with ${\bar{X}}_{\alpha },{\bar{Z}}_{\beta }$ and ${\bar{X}}_{\alpha }^{\prime },{\bar{Z}}_{\beta }^{\prime }$ respectively.

Not all choices of $f,g,h$ span all k logical qubits, but valid choices are readily enumerated in software. Solutions to $Bf=0$ and $gB+hA=0$ correspond to null spaces of B and $\left[B\right]$ respectively, which can be constructed by Gaussian elimination. Gaussian elimination can also be used to check if the operators ${\bar{X}}_{\alpha },{\bar{Z}}_{\alpha },{\bar{X}}_{\alpha }^{\prime },{\bar{Z}}_{\alpha }^{\prime }$ together span k qubits up to the stabilizer. We find all codes in Table 3 admit several such choices of $f,g,h$ . In Table 7 we show a particularly favorable choice of $f,g,h$ for the [[144, 12, 12]] code where the resulting logical operators have minimum weight.

Polynomials for Logical Pauli Matrices in the [[144, 12, 12]] Code

Table 7: Choices of polynomials $f,g,h$ such that ${\bar{X}}_{\alpha }:=X(\alpha f,0)$ and ${\bar{Z}}_{\alpha }=Z(\alpha h^T,\alpha g^T)$ as defined in equation 16 are minimum-weight logical Pauli operators. The dots represent the monomials of the form $x^i{y}^j$ with coeficient 1. If we let $\{n_i\}=\{1,y,x^{2}y,x^2{y}^5,x^3{y}^2,x^4\}$ and $\{m_i\}=\{y,y^5,xy,1,x^4,x^5{y}^2\}$ , then ${\bar{X}}_{n_i},{\bar{Z}}_{m_j}$ anticommute exactly when $i=j$ . When used to construct an ancilla system as in Section $\mathrm{9.4.}$ these polynomials give a system with 60 qubits per layer.

To identify logical qubits we can enumerate choices of monomials $\{n_1,n_2,\dots ,n_{k/2}\}$ and $\{m_1,m_2,...,m_{k/2}\}$ such that $n_i^T{m}_j\in fh$ exactly when $i=j$ . That way, ${\bar{X}}_{n_i},{\bar{Z}}_m$ as well as ${\bar{X}}_{n_i}^{\prime },{\bar{Z}}_{m_i}^{\prime }$ for $i=\mathrm{1...}k/2$ form a set of k logical qubits: ${\bar{X}}_{n_i}$ anticommutes with ${\bar{Z}}_{m_j}$ exactly when $i=j$ . A brute force search readily finds choices of $\{n_i\},\{m_i\}$

9.2 Logical Gates based on Automorphisms

An automorphism of an error correction code is a permutation of the physical qubits that is equivalent to a permutation of the checks (more generally, an automorphism can map a check operator to a product of check operators). We focus on permutations that are implementable using fault tolerant circuits within the connectivity already required for syndrome measurements.

The existing connectivity admits some natural fault tolerant circuits implementing a particular family of permuta tions on the data qubits. BB LDPC codes feature two data registers $q(L),q(R)$ and two check registers $q(X),q(Z)$ . We consider circuits that transfer the qubits from the data registers to the ancilla registers, and back again on a diferent path. The adjacency matrices describing the connectivity between the data and the ancilla registers are given by A and B, which are the sum of three monomials $A_1,A_2,A_3$ and $B_1,B_2,B_3$ in $\mathcal{M}$ . Each monomial is a permutation and thus describes a vertex-disjoint set of edges between the data and ancilla block. Hence, all swaps along these edges can be parallelized. In a single circuit we can either swap along the edges defined by A which are $q(L)q(X)$ and $q(R)q(Z)$ , or along edges defined by B which are $q(L)q(Z)$ and $q(R)q(X)$ . See also Figure 4 A).

The monomial defining the particular set of edges in each of these sets of swaps can be chosen independently for each stage of the permutation (data → ancilla or ancilla → data), and on each side of the Tanner graph. For example, we can select any $A_j,A_k,A_{j^{\prime }},A_{k^{\prime }}$ and move $q(L){\to }_{A_i^T}q(X){\to }_{A_k}q(L)$ and simultaneously move $q(R){\to }_{A_{k^{\prime }}}q(Z){\to }_{A_{{÷}^{\prime }}^T}q(R)$ However, we will see later that it is necessary to select $A_j=A_{j{}^{\prime }}$ and $A_k=A_{k^{\prime }}$ . Furthermore, these swaps admit a standard optimization: if we initialize the check registers $q(X),q(Z)$ to the |0⟩ state, then circuits implementing these permutations have CNOT depth four. If we also reset qubits to the |0⟩ state in between the swaps wherever possible, we obtain circuits whose errors cannot propagate between physical qubits, and are hence fault tolerant. See Table 8.

We now verify that the permutations implemented by the circuits described above are indeed automorphisms. After having applied an ‘A’ type permutation based on $A_j,A_k$ , the qubits are permuted by $q(L,\alpha )q(L,A_k^T{A}_j\alpha )$ and $q(R,\alpha )q(R,A_k^T{A}_j\alpha )$ . We see that this transforms a Pauli matrix by $X(P,Q)X(A_j{A}_k^{T}P,A_j{A}_k^{T}Q)$ . Consequently, the stabilizers are transformed as $X(\alpha A,\alpha B)X(\alpha A_j{A}_k^{T}A,\alpha A_j{A}_k^{T}B)$ , which is the same as permuting the X checks by $\alpha \alpha A_j{A}_k^T$ . The Z stabilizers are also permuted by $\alpha \alpha A_j{A}_k^T$ , so the described circuit indeed implements an automorphism. Notice also that this only works because the $q(L)$ and $q(R)$ blocks were transformed by the same

‘A’ type automorphism based on any Aj, Ak
for α ∈ M do	for α ∈ M do
InitZ q(X,α)	InitZ q(Z,α)
CNOT q(L,Ajα) q(X,α)	CNOT q(R,α) q(Z,Ajα)
CNOT q(X,α) q(L,Ajα)	CNOT q(Z,Ajα) q(R,α)
InitZ q(L,ATkα)	InitZ q(R,Akα)
CNOT q(X,α) q(L,Akα)	CNOT q(Z,Akα) q(R,α)
CNOT q(L,Akα) q(X,α)	CNOT q(R,α) q(Z,Akα)
end for	end for
‘B’ type automorphism based on any Bj, Bk
for α ∈ M do	for α ∈ M do
InitZ q(X,α)	InitZ q(Z,α)
CNOT q(R,Bjα) q(X,α)	CNOT q(L,α) q(Z,Bjα)
CNOT q(X,α) q(R,Bjα)	CNOT q(Z,Bjα) q(L,α)
InitZ q(R,BkTα)	InitZ q(L,Bkα)
CNOT q(X,α) q(R,Bkα)	CNOT q(Z,Bkα) q(L,α)
CNOT q(R,Bkα) q(X,α)	CNOT q(L,α) q(Z,Bkα)
end for	end for

Table 8: Circuits implementing automorphisms of a BB LDPC code within the connectivity already present for syndrome checks. These circuits are fault tolerant and have CNOT depth four. If $s=A_j{A}_k^T\mathrm{or}s=B_j{\bar{B}}_k^{\bar{T}}$ , then the logical gate implemented by these automorphisms performs the transformation ${\bar{X}}_{\alpha },{\bar{Z}}_{\alpha },{\bar{X}}_{\alpha }^{\bar{\prime }},{\overline{\stackrel{ˉ}{Z}}}_{\alpha }^{\prime }{\bar{X}}_{s\alpha },{\bar{Z}}_{s\alpha },{\bar{X}}_{s\alpha }^{\prime },{\bar{Z}}_{s\alpha }^{\prime }.$

$A_j{A}_k^T$ . The ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ type permutations can be verified to be automorphisms in the same manner, permuting the checks by some $B_j{B}_k^T$

These automorphisms allow us to fault tolerantly implement a subgroup of the Cliford gates. As we saw in Lemma 3, shifts of the form $A_j{A}_k^T$ or $B_j{B}_k^T$ generate the entire group M whenever the Tanner graph is connected. Therefore, by leveraging these permutations as generators, we can perform all translations of the tori containing $q(L),q(R)$ using fault tolerant circuits of varying depth. An automorphism defined by an element $s\in \mathcal{M}$ transforms ${\bar{X}}_{n_i}{\bar{X}}_{s{n}_i},{\bar{Z}}_{m_i}{\bar{Z}}_{s{m}_i}$ and similarly for the primed logical Pauli matrices. This capability is critical for addressing all logical qubits.

We can also comment on the nature of these operations as logical gates, although they are less useful in this sense. There is one such operation per element in M, and since M is Abelian the subgroup of Cliford gates implemented by these automorphisms must be Abelian as well. A transformation of this form cannot act like the logical identity so all of these gates (except $s=1)$ are nontrivial. Since automorphism operations take X^¯ to X^¯ and Z^¯ to Z^¯, and they must hence be logical CNOT circuits up to a logical Pauli correction. While it is not clear how to use these CNOT circuits to facilitate useful computations, they may make for interesting test cases in an implementation.

9.3 Accessing the Primed Block via a ZX-duality

A ZX-duality is a permutation of the logical qubits that commutes with the stabilizer, except that it turns X checks into Z checks and Z checks into X checks. A physical circuit implementing this permutation and then applying Hadamard to all data qubits always acts as a logical gate [62]. In this section we focus on the implementation of a particular ZX-duality with applications for readout. We leave discovery and implementation of other ZX-dualities for future work. In particular, we derive a general method for constructing fault tolerant circuits for implementing a particular ZX-duality that is present in all BB LDPC codes. While the circuits from this construction are generally quite expensive, they may be amenable to further optimization and can be used sparingly in practice.

Consider a permutation of data qubits that swaps $q(L,\alpha )$ with $q(R,{\alpha }^T)$ for all $\alpha \in \mathcal{M}$ . A check qubit $q(X,\beta )$ which previously implemented the stabilizer $X(\beta A,\beta B)$ now is connected to the qubits $q(L,(\beta B{)}^T)$ and $q(R,(\beta A{)}^T)$ instead, corresponding to the check $Z({\beta }^T{B}^T,{\beta }^{\ddot{T}}{A}^T)$ . We see that this permutation switches the stabilizer implemented by $q(X,\beta )$ with the stabilizer implemented by $\stackrel{\cdot }{q}(Z,{\beta }^T)$ , so this permutation is indeed a ZX-duality.

Figure 7: Diagrams for the description of the implementation of the ZX-duality permutation. A) A subgraph of the Tanner graph providing enough connectivity to fault tolerantly swap $q(L,\alpha )$ and $q(L,A_j{A}_i^T\alpha )$ . B) A sequence of shifts of the data on the qubits in the $q(L)$ block that performs the desired exchange without interacting qubits directly. A naive implementation of this sequence has CNOT depth 12. C) D) Decomposition of the generators of $\mathcal{M}$ via the classification of finite Abelian groups for two diferent codes. Drawing the Cayley graph of the subgroup for each generator reveals the ratios defining pairs of qubits that must be exchanged to implement the permutation $q(L,\alpha )q(L,{\alpha }^T)$

We can also see that implementing this permutation and applying Hadamard to all qubits takes logical Pauli matrices to logical Pauli matrices. In particular, the operation swaps ${\bar{X}}_{\alpha }=X(\alpha f,0)$ with ${\bar{Z}}_{{\alpha }^T}^{\prime }=Z(0,{\bar{\alpha }}^T{f}^T)$ , as well as ${\bar{Z}}_{\alpha }=\breve{Z}(\alpha h^T,\alpha g^T)$ with ${\bar{X}}_{{\alpha }^T}^{\prime }:=\bar{X}({\alpha }^{T}g,{\alpha }^{T}h)$ . This operation swaps the primed and unprimed logical blocks, transposes the grid of operators, and applies logical Hadamard to all qubits. Since we can measure logical X for all qubits in the unprimed block using the ancilla system described in Subsection 9.4, we can use this operation to measure logical Z for qubits in the primed block.

For the rest of this section we describe a fault tolerant method for implementing this operation. We begin with exchanging $q(L)$ and $q(R)$ : since these blocks are connected by pairs of edges in $q(X)$ and $q(Z)$ , for any $A_i\in A$ and $B_j\in B$ there exists a loop connecting the qubits $q(L,\alpha )q(X,A_i^T\alpha )q(R,B_j{A}_i^T\alpha )q(Z,B_j\alpha )q(L,\alpha )$ . A circuit identical in shape to those in Table 8 hence performs a fault tolerant exchange of $q(L,\alpha )$ and $q(R,B_j{A}_i^T\alpha )$ for all α. The additional shift of $B_j{A}_i^T$ can be removed via an additional automorphism gate. It remains to exchange $q(L,\alpha )q(L,{\alpha }^T)$ , as well as $\bar{q}(\overline{R,}\alpha )q(R,{\alpha }^T)$ for all $\alpha .$ , which is significantly more complicated. We focus on $q(L,\alpha )q(L,{\alpha }^T)$ in our discussion but it will be clear the exact same transformations are implementable on $q(R)$ in parallel with those on $q(L)$ ).

Fault tolerant implementation of the permutation $q(L,\alpha )q(L,{\alpha }^T)$ can be achieved using a more sophisticated version of the fault tolerant circuits in Table 8 used for implementing automorphisms. These circuits relied on the existence of a connected loop of alternating check and data qubits, enabling a short depth fault tolerant circuit implementing a cyclic permutation of the data qubits therein. The same connectivity can be leveraged to implement a fault tolerant nearest neighbor swap of two data qubits connected by a check qubit. The fault tolerance of these circuits relies on the same principle: while a swap gate acting on two qubits containing data is not fault tolerant, moving a data qubit onto a blank qubit is. Figure $7\mathrm{A})$ shows a subgraph of the Tanner graph consisting of several connected qubits in the $q(L)$ and $q(X)$ block, and Figure 7 B) shows a sequence of operations where two data qubits can be exchanged without ever interacting directly. This gives us the following capability: whenever the circuits in Table 8 can implement the cyclic permutation $q(L,\alpha )\to q(L,s\alpha )$ for all $\alpha .$ , there also exists a circuit that can swap $q(L,\alpha )$ and $q(L,s\alpha )$ for a particular α. Matching circuits exist for $q(R)$ , and can be implemented simultaneously.

To decompose $q(L,\alpha )q(L,{\alpha }^T)$ into a sequence of swaps, it will be helpful to consider the group structure of $\mathcal{M}$ . Consider for example the [[90, 8, 10]] code with $x^{15}=y^3=1$ . Following the classification of finite Abelian groups we see that $\mathcal{M}\cong {\mathbb{Z}}_3\times {\mathbb{Z}}_5\times {\mathbb{Z}}_3$ . We can re-express elements of $\mathcal{M}$ using generators $p,q,r$ with $p^3=q^5=r^3=1$ where $x=pq$ and $y=r.$ . Transforming α to ${\alpha }^T$ amounts to decomposing α as $\alpha =p^i{q}^j{r}^k$ and exchanging the qubit with ${\alpha }^T=p^{-i}{q}^{-j}{r}^{-k}$

This exchange $p^i{q}^j{r}^k{p}^{-i}{q}^{-j}{r}^{-k}$ can be split into a sequence of swaps that are implementable with the method described above using Figure $7\mathrm{A})$ and B). It sufices to be able to exchange for any $\alpha =q^j{r}^k$ the qubits $q(L,p^i\alpha )q(L,\alpha p^{-i})$ , as well as for any $\dot{\alpha }=p^i{r}^k$ the qubits $q(L,q^j\alpha )q(L,\alpha q^{-j})$ , and finally for any $\alpha =p^i{q}^j$ the qubits $q(L,r^k\alpha )q(L,\alpha r^{-k})$ . This, for any $i,j,k,$ , creates a sequence of qubits $q(L,p^i{q}^j{r}^k)q(L,p^{-i}{q}^j{r}^k)$ $q(L,p^{-i}{q}^{-j}{r}^k)q(L,p^{-i}{q}^{-j}{r}^{-k})$ where swaps are possible along each nearest neighbor. This is suficient for swapping the first and last qubit in the chain. The implementation of the individual generators like $q(L,\alpha q^i)q(L,\alpha q^{-i})$ swaps may also involve additional intermediate qubits, but this only lengthens the chain and does not prohibit implementation.

The resources required for swapping $q(L,p^i\alpha )q(L,\alpha p^{-i})$ where $p^3=1$ and similarly for other generators depends on the order of the generator p as well as the ratios $A_i{A}_i^T$ that can be formed using terms $A_i,A_j\in A$ or similar ratios from B. See Figure $7\mathrm{C})$ . Plotting the Cayley graph of the cyclic subgroup spanned by p immediately reveals that since $p$ is order three, only a single ratio $B_i{B}_i^T=p$ is needed in order to swap any qubits marked $p^1$ and $p^2$ , while leaving $p^0$ qubits in place. Indeed since $B=1+{\stackrel{⌣}{x}}^2+x^7=1+p^2{q}^2+p{q}^2$ we can implement $p=(p^2{q}^2)(p{q}^2{)}^T$ in a single layer of transforms in Figure 7 B).

The exchange $q(L,\alpha q^i)q(L,\alpha q^{-i})$ with $q^5=1$ requires two such ratios $q$ and $q^2$ , the minimal depth expression of which demands the chaining together of two such transforms each. In other codes, like the [[144, 12, 12]] code, we encounter generators $p,q,r,s$ of order $p^4=q^3=r^2=s^3=1$ . Elements of order two like $r$ require no swaps at all, and elements of order four like $p$ can be implemented either using the ratio $p^2$ or just $p,$ as shown in Figure 7 D). Numerical searches can quickly compute the most eficient decompositions of the required swaps. We give the orders of the generators, the ratios defining the required swaps, and the number of transforms required to implement them in Table 9.

We emphasize that the swap $q(L,p^i\alpha )q(L,\alpha p^{-i})$ can be performed for all $\alpha =q^j{r}^k$ simultaneously in parallel. This stems from the structure of the exchange circuit in Figure 7 B). This circuit performs the swap $q(L,\alpha )$ $q(L,A_j{A}_i^T\cdot \alpha )$ ) while using the qubit $q(L,A_k{A}_i^T\cdot \alpha )$ as scratch space. However, we can simultaneously want to swap $q(L,\overline{A_k}\overline{A_i^T}\cdot \alpha )$ ↔ q(L, A_jA^T · A_kA^T · α) since the first step of the exchange circuit in Figure 7 B) is to move the data marked $\mathrm{\Delta }{\cdot }_{\mathrm{A}}\mathrm{\Omega }$ away from the qubit holding it, just as if it were a piece of data marked ${\nabla }^{\mathbf{C}}$ for a diferent exchange.

For clarity, we compute the total depth of the circuit for the [[144, 12, 12]] code without any further optimization. The ratios $p,q,$ s can be implemented using two ratios each via $p\stackrel{...}{=}{x}^{-3}y\cdot y^{-2}\stackrel{.}{y},q=y^{-3}{x}^2\cdot y^{-3}{x}^2$ and $s=y^{-2}y\cdot y^{-2}y$ This results in a chain $q(L,\alpha )q(L,{\alpha }^{\prime })q(L,{\alpha }^{\prime \prime })...q(L,{\alpha }^T)$ of length six (counting the number of ↔s). We can swap the qubits at the ends of a chain of length n using $2n-1$ many nearest neighbor swaps. Each swap circuit of the form Figure ${}^{\text{ 7 B }}$ can be implemented in CNOT depth twelve, resulting in CNOT depth $(2\cdot 6-1)\cdot 12=132$ to implement $q(L,\alpha )q(L,{\alpha }^T)$

Despite its fault tolerance, the implementation of this logical operation is clearly significantly more expensive than that of the automorphisms. Since the intermediate permutations corresponding to each of the generators $p,q,r$ are not ZX dualities in general, it will not be possible in general to perform error correction during this long operation. However, the significant overhead of this operation may be worth such a large cost, since it grants us the capability of accessing the primed block of qubits, efectively doubling the storage capacity of the code. This operation can also be used significantly more sparingly than the automorphism gates, and may be amenable to additional optimization Alternatively, additional connections and qubits beyond those necessary for the Tanner graph could be introduced to more directly implement the ZX-duality, though it is likely this will sacrifice the thickness-2 property.

Code	Base Order	Reduced Order	Required Ratios	Swap Chain Length
[[72,12,6]]	$x^6,y^6$	$p^2,q^3,r^2,s^3$	$q,s$	4
[[90,8,10]]	$x^{15},y^3$	$p^3,q^5,r^3$	$p,q,q^2,r$	6
[[108,8,10]]	$x^9,y^6$	$p^9,q^2,r^3$	$p,p^3,p^5,p^7,r$	9
[[144,12,12]]	$x^{12},y^6$	$p^4,q^3,r^2,s^3$	$p,q,s$	6
[[288,12,18]]	$x^{12},y^{12}$	$p^4,q^3,r^4,s^3$	$p,q,r,s$	10
[[360,12, $\le$ 24]]	$x^{30},y^6$	$p^2,q^3,r^5,s^2,t^3$	$q,ps,ps{r}^2,ps{r}^3,t$	11

Table 9: Table deriving the steps in the circuit implementing the $q(L,\alpha )q(L,{\alpha }^T)$ , permutation for the ZXduality for several codes. The generators of M are decomposed into generators following the decomposition of finite Abelian groups. Following Figure 7 B) and C) these generators demand a set of ratios of terms in A or B which define fault tolerantly implementable exchanges of qubits with corresponding labels. The result is a decomposition of $q(L,\alpha )q(L,{\alpha }^T)$ into a chain $q(L,\alpha )q(L,{\alpha }^{\prime })q(L,{\alpha }^{\prime \prime })...q(L,{\alpha }^T)$ with length as shown (counting the number of arrows, ↔). Note the special implementation of the ratios in the $[[360,12,\le 24]]$ code: the ratios $\overline{r^2},r^3$ are not implementable, but $ps{r}^2,ps{r}^3$ are. This is fine if we can also perform the ps ratio on its own to remove the additional transformation on some of the qubits.

9.4 Logical Measurements

In this section we describe how to leverage methods from [46] to implement fault-tolerant measurements of the operators ${\bar{X}}_1=X(f,0)$ and ${\bar{Z}}_1=Z(h^T,g^T)$ . As described above, this capability sufices to measure $\bar{X}$ and $\bar{Z}$ for all logical qubits. We can also use this technique to measure various Pauli product operators by measuring ${\bar{X}}_{\alpha },{\bar{Z}}_{\alpha },{\bar{X}}_{\alpha }^{\prime },{\bar{Z}}_{\alpha }^{\prime }$ for α not corresponding to logical qubits.

The measurement is facilitated by an ancilla system that extends the Tanner graph of the original code. The code defined by this extended Tanner graph contains the logical operator of interest as a stabilizer, enabling its fault tolerant measurement. A sketch of the structure of this ancilla system is given in Figure 1 C). For the logical operator $X(f,0)$ , we consider a subgraph of the Tanner graph consisting of $q(L,f)$ as well as $q(Z,\alpha )$ operators corresponding to checks with support on $q(L,f)$ . Similarly for the logical operator $Z(h^T,g^T)$ we consider a subgraph consisting of $q(L,h^T),q(R,g^T)$ as well as $q(X,\alpha )$ for the relevant $\alpha .$ These subgraphs are copied several times and are connected together as shown in the figure: we call the resulting construction an ancilla system. With enough copies, the code defined by the extended Tanner graph has the same distance as the original code.

Furthermore, the ancilla system for measuring $X(f,0)$ can be connected to another quantum error correction code, such as a surface code. This enables a joint X^¯ X^¯ measurement between a surface code qubit and any qubit within the BB code. A subsequent measurement of $Z(h^T,g^T)$ and some additional Pauli corrections then achieves a quantum teleportation circuit.

The main challenge of implementing these ancilla systems, in addition to minimizing their size, is to show that the extended Tanner graph satisfies the thickness-2 constraint. If our goal is to leverage the $X(f,0)$ ancilla system to measure a Pauli product measurement with a surface code qubit, then arguably a thickness-2 extension of the Tanner graph does not sufice since there is no obvious way of connecting it to the surface code qubit as in Figure 1 C). To this end, we show how to make the subgraph corresponding to the $X(f,0)$ ancilla system “efectively planar”: while the graph has thickness-2, the planar graph in one plane consists entirely of connected components with two vertices. Given this property of the embedding of the $X(f,0)$ ancilla system, a connection between this system and a surface code may be facilitated by a construction that is thickness-2 overall.

An efectively planar embedding of the ancilla system relies on the fact that the logical operator $X(f,0)$ has no support on the $q(R)$ block. An implementation of more general logical operators is possible, but would require a graph that renders many ancilla qubits inaccessible from the outside.

We briefly give a self-contained description for the construction of the ancilla system from [46], following their notation. Suppose we are interested in measuring a logical operator $\bar{X}$ that is supported on some set of qubits $V_{\bar{X}}$ Then, let $C_{\bar{X}}$ be the collection of Pauli- $Z$ checks that have support on any of the $V_{\bar{X}}$ . If we view these as sets of vertices in a Tanner graph, and let $E_{\bar{X}}$ contain the edges between $V_{\bar{X}}$ and $C_{\bar{X}}$ , then ${\mathcal{G}}_{\bar{X}}:=\left(V_{\bar{X}},C_{\bar{X}},E_{\bar{X}}\right)$ forms a subgraph of the Tanner graph of the BB code.

The ancilla system is constructed out of copies of ‘primal layers’ isomorphic to ${\mathcal{G}}_{\bar{X}}$ , and ‘dual layers’ isomorphic to ${\mathcal{G}}_{\bar{X}}^T:=(V_{\bar{X}}^T,C_{\bar{X}}^T,{\bar{E}}_{\bar{X}}^T)$ defined as follows: each $v\in V_{\bar{X}}$ has a corresponding ${\bar{v}}^T\in C_{\bar{X}}^T$ , each $c\in C_{\bar{X}}$ has a corresponding $c^{\hat{T}}\in V_{\bar{X}}^T$ , and each edge $(v,c)\in E_{\bar{X}}$ has a corresponding $(v^T,c^T)\in E_{\bar{X}}^T$ . For some parameter r, the final Tanner graph is that of the BB code, plus r additional copies of the dual graph labeled ${\mathcal{G}}_{\bar{X}}^T[j]$ for $1\le j\le r,$ and $r-1$ additional copies of the primal graph labeled ${\mathcal{G}}_{\bar{X}}[j]$ for $2\le j\le r$ . We regard the ${\mathcal{G}}_{\bar{X}}$ within the original code as ${\mathcal{G}}_{\bar{X}}[1]$ . We also add additional connections between ${\mathcal{G}}_{\bar{X}}[j]$ and ${\mathcal{G}}_{\bar{X}}^T[j]$ for $j\le r,$ , as well as ${\mathcal{G}}_{\bar{X}}^T[j]$ and ${\mathcal{G}}_{\bar{X}}[j+1]$ for $j<r:$ specifically, we connect the associated pairs of $v,v^T$ and $c,c^T$

It is shown by [46] that the resulting Tanner graph defines an error correction code of distance d when $r=d.$ We construct two such ancilla systems: one for $\bar{X}:=X(f,0)$ and one for $\bar{Z}:=Z(h^T,g^T)$ . Table 7 shows a choice of $f,g,h$ for the [[144, 12, 12]] code, defining $X(f,0)$ and $Z(h^T,g^T)$ such that these operators are all minimum weight, and define ${\mathcal{G}}_{\bar{X}}$ and ${\mathcal{G}}_{\bar{Z}}$ with 30 qubits each. To achieve $d=12$ we hence require $2\times 30\times (2d-1)=1380$ additional qubits. We suspect that significantly more eficient variations of this constructions are possible, but leave their development for future work.

The construction presented above is complicated by the fact that vertices in the Tanner graph take on alternating roles in each layer: in the primal layers the vertices v are physical qubits, whereas in the dual layers the $v^T$ are checks. However, for the purposes of giving a thickness-2 decomposition we need not concern ourselves with this. If we do not distinguish between checks and physical qubits, then the primal layers ${\mathcal{G}}_{\mathcal{X}}$ and dual layers ${\mathcal{G}}_{\mathcal{X}}^T$ have isomorphic Tanner graphs. Hence, for the purposes of the following, we view all layers as identical.

We now show why a thickness-2 embedding of the $Z(h^T,g^{\dot{T}})$ ancilla system, and an efectively planar embedding of the $X(f,0)$ ancilla system is possible. This argument is best understood in reference to Figure 8. We begin by understanding the thickness-2 decomposition of each layer of the ancilla systems, leveraging Figure 3. In Figure $8\mathrm{A})$ we can see that ${\mathcal{G}}_{\bar{Z}}$ for the $Z(h^T,g^T)$ system decomposes into ‘hairy rings’ in both the ${\Omega }^{⟨}{\mathrm{A}}^{⟩}$ plane and the ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ plane since it has no support on $q(Z)$ ${\mathcal{G}}_{\bar{X}}$ for the $X(f,0)$ system is a collection of connected pairs in the $⟨\mathrm{A}⟩$ plane and collection of rings in the ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ plane, since it has no support on $q(X)$

Since ${\mathcal{G}}_{\bar{X}},{\mathcal{G}}_{\bar{Z}}$ are subgraphs of the BB code’s Tanner graph, and its Tanner graph has thickness-2, and since ${\mathcal{G}}_{\bar{X}},{\mathcal{G}}_{\bar{Z}}$ and ${\mathcal{G}}_{\bar{X}}^T,{\mathcal{G}}_{\bar{Z}}^{\bar{T}}$ are isomorphic if we do not distinguish between qubits and checks, we see that each layer of the ancilla construction must be thickness-2 individually. The main challenge is to show that the connections between the layers can be facilitated without introducing any crossings.

Figure 8 B) shows how to connect several layers of the two ancilla systems to both the wheel graphs of the BB code, and also an ancillary surface code. We arrange the wheels of the BB code such that $q(X),q(L)$ are on the inside of the ${\Omega }^{⟨}{\mathrm{A}}^{⟩}$ wheels, and that $q(X),q(R)$ are on the inside of the ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ wheels. ${\mathcal{G}}_{\bar{Z}}$ and ${\mathcal{G}}_{\hat{Z}}^T$ for of the $Z(h^T,g^T)$ system can be repeatedly nested inside of the wheels of the BB code. The $q(L)$ qubits can be connected together on the $\mathrm{\Delta }{\cdot }_{\mathrm{A}}\mathrm{\Omega }$ plane, and the $q(R)$ and $q(X)$ qubits can be connected on the ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ plane. As for ${\mathcal{G}}_{\bar{X}}$ and ${\mathcal{G}}_{\bar{X}}^T$ for the $X(f,0)$ system, the rings in the ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ plane can be wrapped around the wheels of the BB code which already allows connection of the required $q(L)$ and $q(Z)$ qubits. This leaves the pairs of connected qubits in the ${\Omega }^{⟨}{\mathrm{A}}^{⟩}$ plane completely free of any connections between the layers, making them available to be connected to a surface code system.

We have considered just two ancilla systems here for measuring $X(f,0)$ and $Z(h^T,g^T)$ . However, using additional ancilla systems, especially if their size can be reduced, or equipping these two ancilla systems with additional connections to the $X(g,h)$ and $Z(0,f^T)$ logical operators are potential ways to eliminate the need for the error-prone ZX-duality from Subsection 9.3 and access all logical qubits. $\mathrm{On}$ the other hand, it is not clear that either approach would preserve the thickness-2 property.

10 Conclusion

In summary, we ofered a new perspective on how a fault-tolerant quantum memory could be realized using near term quantum processors with a small qubit overhead. Our approach complements a concatenation-based scheme by Pattison, Krishna, and Preskill [63] where each data qubit of a high-rate LDPC code is additionally encoded b the surface code. Although the concatenation approach makes use of the high error threshold of the surface code and its geometric locality to address quantum hardware limitations such as a relatively high noise rate and limited qubit connectivity, the additional surface code encoding incurs a significant qubit overhead, partially negating the advantages ofered by LDPC codes. Here we have shown that the concatenation step can be avoided by introducing examples of high-rate LDPC codes which have nearly the same error threshold as the surface code itself. Although these LDPC codes are not geometrically local, qubit connectivity required for syndrome measurements is described by a thickness-two graph which can be implemented using two planar degree-3 layers of qubit couplers. This is a valid architectural solution for platforms based on superconducting qubits. Numerical simulations performed for the circuit-based noise model indicate that the proposed LDPC codes compare favorably with the surface code in the practically relevant range of error rates p ≥ 0.1% ofering the same level of error suppression with nearly 15x reduction in the qubit overhead.

The key hardware challenges to enable the new codes with superconducting qubits are:

1. the development of a low-loss second layer,

2. the development of qubits that can be coupled to 7 connections (6 buses and 1 control line), and

3. the development of long-range couplers.

These are all dificult to solve but not impossible. For the first challenge, we can imagine a small change to the packaging [53] which was developed for the IBM Quantum Eagle processor [64]. The simplest would be to place the extra buses on the opposite side of the qubit chip. This would require the development of high Q through substrate vias (TSV) which would be part of the coupling buses and as such would require intensive microwave simulation to make sure these TSVs could support microwave propagation while not introducing large unwanted crosstalk.

The second challenge is an extension of the number of couplers from the heavy hex lattice arrangement [65] which is 4 (3 couplers and 1 control) to 7. The implication of this is that the cross-resonance gate, which has been the core gate used in large quantum systems for the past few years, would not be the path forward. This is due to the fact that the qubits in the cross-resonance gate are not tunable and as such for a large device with a large number of connections the probability of energy collisions (not just the qubit levels but also higher levels of the transmon) trends to one very fast [66]. This is because of frequency requirements for the gate to work properly and intrinsic device variability, which is fundamental to Josephson junction fabrication. However, with the tunable coupler [67, 68], which was used in the IBM Quantum Egret and is now being developed for the IBM Quantum Heron, this problem no longer exists as the qubits can be designed to be further apart. This new gate is also similar to the gates used by Google Quantum AI [69], which have shown that a square lattice arrangement is possible. Extending the coupling map to 7 connections will require significant microwave modeling; however, typical transmons have about 60fF of capacitance and each gate is around 5fF to get the appropriate coupling strengths to the buses, so it is fundamentally possible to develop this coupling map without changing the properties of the transmon qubits which have been shown to have larger coherence and are stable.

The final challenge is the most dificult. For the buses that are short enough so that the fundamental mode can be used the standard circuit QED model holds. However, to demonstrate the 144-qubit code some of the buses will be long enough that we will require frequency engineering. One way to achieve this is with filtering resonators, and a proof of principle experiment was demonstrated in Ref. [70].

Our work leaves several open questions concerning BB LDPC codes and their applications.

1. What are the tradeofs between the code parameters n, k, d and can one achieve a constant non-zero encoding rate and a growing distance?

2. Are there more general LDPC codes compatible with our syndrome measurement circuit(s)? We expect that the same circuit applies to any two-block LDPC code based on an Abelian group [37, 38]. However, our circuit analysis breaks down for non-Abelian groups.

3. Our work gives a depth-7 syndrome measurement circuit, as measured by the number of CNOT layers. Is it possible to reduce the circuit depth? Numerical experiments performed for the code [[72, 12, 6]] indicate that this code may have no depth-6 syndrome measurement (SM) circuit [71].

4. We observed that a depth-7 SM circuit is not unique. A natural next step is identifying a SM circuit that works best for a particular code. In addition, it may be possible to improve the circuit-level distance by using diferent SM circuits in diferent syndrome cycles. Even though some low-weight fault paths are not detectable by any single circuit, such fault paths may be detected if two circuits are used in tandem.

5. How much would the error threshold change for a noise biased towards measurement errors? Note that measurements are the dominant source of noise for superconducting qubits. Since the considered BB codes have a highly redundant set of check operators, one may expect that they ofer extra protection against measurement errors.

6. The general-purpose BP-OSD decoder used here may not be fast enough to perform error correction in real time Is there a faster decoder making use of the special structure of BB codes?

7. How to apply logical gates? While our work gives a fault-tolerant implementation of certain logical gates, these gates ofer very limited computational power and are primarily useful for implementing memory capabilities.

Acknowledgements

The authors thank Ben Brown, Oliver Dial, Alexander Ivrii, Tomas Jochym-O’Connor, Yunseong Nam, Matthias Steffen, Kevin Tien, and John Blue for stimulating discussions at various stages of this project. The authors acknowledge the IBM Research Cognitive Computing Cluster service for providing resources that have contributed to the research results reported within this paper.

References

[1] Michael A. Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.

[2] Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073–1078, 1996.

[3] Hefeng Wang, Sabre Kais, Al´an Aspuru-Guzik, and Mark R. Hofmann. Quantum algorithm for obtaining the energy spectrum of molecular systems. Physical Chemistry Chemical Physics, 10(35):5388–5393, 2008.

[4] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114(29):7555–7560, 2017.

[5] Yuri Alexeev, Dave Bacon, Kenneth R. Brown, Robert Calderbank, Lincoln D. Carr, Frederic T. Chong, Brian DeMarco, Dirk Englund, Edward Farhi, Bill Feferman, et al. Quantum computer systems for scientific discovery. PRX Quantum, 2(1):017001, 2021.

[6] Jay M. Gambetta, Jerry M. Chow, and Matthias Stefen. Building logical qubits in a superconducting quantum computing system. npj Quantum Information, 3(1):2, 2017.

[7] Pranav S. Mundada, Aaron Barbosa, Smarak Maity, Yulun Wang, T. M. Stace, Thomas Merkh, Felicity Nielson, Andre R. R. Carvalho, Michael Hush, Michael J. Biercuk, and Yuval Baum. Experimental benchmarking of an automated deterministic error suppression workflow for quantum algorithms, 2023.

[8] Nathalie P. De Leon, Kohei M. Itoh, Dohun Kim, Karan K. Mehta, Tracy E. Northup, Hanhee Paik, B.S. Palmer, Nitin Samarth, Sorawis Sangtawesin, and David W. Steuerman. Materials challenges and opportunities for quantum computing hardware. Science, 372(6539):eabb2823, 2021.

[9] Antonio D. C´orcoles, Jerry M. Chow, Jay M. Gambetta, Chad Rigetti, J. R. Rozen, George A. Keefe, Mary Beth Rothwell, Mark B. Ketchen, and M. Stefen. Protecting superconducting qubits from radiation. Applied Physics Letters, 99(18):181906, 11 2011.

[10] Antti P. Veps¨al¨ainen, Amir H. Karamlou, John L. Orrell, Akshunna S. Dogra, Ben Loer, Francisca Vasconcelos, David K. Kim, Alexander J. Melville, Bethany M. Niedzielski, Jonilyn L. Yoder, et al. Impact of ionizing radiation on superconducting qubit coherence. Nature, 584(7822):551–556, 2020.

[11] Ted Thorbeck, Andrew Eddins, Isaac Lauer, Douglas T. McClure, and Malcolm Carroll. Two-level-system dy namics in a superconducting qubit due to background ionizing radiation. PRX Quantum, 4:020356, Jun 2023.

[12] Yukai Wu, Sheng-Tao Wang, and L.-M. Duan. Noise analysis for high-fidelity quantum entangling gates in an anharmonic linear Paul trap. Physical Review A, 97(6):062325, 2018.

[13] Matthew J. Boguslawski, Zachary J. Wall, Samuel R. Vizvary, Isam Daniel Moore, Michael Bareian, David T.C. Allcock, David J. Wineland, Eric R. Hudson, and Wesley C. Campbell. Raman scattering errors in stimulated raman-induced logic gates in ba+ 133. Physical Review Letters, 131(6):063001, 2023.

[14] A. A. Houck, J. A. Schreier, B. R. Johnson, J. M. Chow, Jens Koch, J. M. Gambetta, D. I. Schuster, L. Frunzio, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf. Controlling the spontaneous emission of a superconducting transmon qubit. Physical Review Letters, 101:080502, 2008.

[15] Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Physical Review A, 52(4):R2493, 1995.

[16] Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the twenty-ninth Annual ACM Symposium on Theory of Computing, pages 176–188, 1997.

[17] Alexei Yu. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191, 1997.

[18] Panos Aliferis, Daniel Gottesman, and John Preskill. Quantum accuracy threshold for concatenated distance-3 codes. arXiv preprint quant-ph/0504218, 2005.

[19] Alexei Kitaev. Fault-tolerant quantum computation by anyons. arXiv preprint quant-ph/9707021, 1997.

[20] Sergey B. Bravyi and Alexei Yu. Kitaev. Quantum codes on a lattice with boundary. arXiv preprint quantph/9811052, 1998.

[21] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452–4505, 2002.

[22] Austin G. Fowler, Ashley M. Stephens, and Peter Groszkowski. High-threshold universal quantum computation on the surface code. Physical Review A, 80(5):052312, 2009.

[23] Maika Takita, Antonio D. C´orcoles, Easwar Magesan, Baleegh Abdo, Markus Brink, Andrew Cross, Jerry M. Chow, and Jay M. Gambetta. Demonstration of weight-four parity measurements in the surface code architecture. Physical Review Letters, 117(21):210505, 2016.

[24] J. F. Marques, B. M. Varbanov, M. S. Moreira, Hany Ali, Nandini Muthusubramanian, Christos Zachariadis, Francesco Battistel, Marc Beekman, Nadia Haider, Wouter Vlothuizen, et al. Logical-qubit operations in an error-detecting surface code. Nature Physics, 18(1):80–86, 2022.

[25] Sebastian Krinner, Nathan Lacroix, Ants Remm, Agustin Di Paolo, Elie Genois, Catherine Leroux, Christoph Hellings, Stefania Lazar, Francois Swiadek, Johannes Herrmann, et al. Realizing repeated quantum error correction in a distance-three surface code. Nature, 605(7911):669–674, 2022.

[26] Youwei Zhao, Yangsen Ye, He-Liang Huang, Yiming Zhang, Dachao Wu, Huijie Guan, Qingling Zhu, Zuolin Wei, Tan He, Sirui Cao, et al. Realization of an error-correcting surface code with superconducting qubits. Physica Review Letters, 129(3):030501, 2022.

[27] Google Quantum AI. Suppressing quantum errors by scaling a surface code logical qubit. Nature, 614(7949):676– 681, 2023.

[28] Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. arXiv preprint arXiv:1310.2984, 2013.

[29] Maxime A. Tremblay, Nicolas Delfosse, and Michael E. Beverland. Constant-overhead quantum error correction with thin planar connectivity. Physical Review Letters, 129(5):050504, 2022.

[30] Nikolas P. Breuckmann and Barbara M. Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE Transactions on Information Theory, 62(6):3731–3744, 2016.

[31] Oscar Higgott and Nikolas P. Breuckmann. Subsystem codes with high thresholds by gauge fixing and reduced qubit overhead. Physical Review X, 11(3):031039, 2021.

[32] Oscar Higgott and Nikolas P. Breuckmann. Constructions and performance of hyperbolic and semi-hyperbolic floquet codes. arXiv preprint arXiv:2308.03750, 2023.

[33] Jean-Pierre Tillich and Gilles Z´emor. Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60(2):1193–1202, 2013.

[34] Nikolas P. Breuckmann and Jens N. Eberhardt. Balanced product quantum codes. IEEE Transactions on Information Theory, 67(10):6653–6674, 2021.

[35] Alexey A. Kovalev and Leonid P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Physical Review A, 88(1):012311, 2013.

[36] Pavel Panteleev and Gleb Kalachev. Degenerate quantum LDPC codes with good finite length performance. Quantum, 5:585, 2021.

[37] Hsiang-Ku Lin and Leonid P. Pryadko. Quantum two-block group algebra codes. arXiv preprint arXiv:2306.16400, 2023.

[38] Renyu Wang, Hsiang-Ku Lin, and Leonid P. Pryadko. Abelian and non-Abelian quantum two-block codes. arXiv preprint arXiv:2305.06890, 2023.

[39] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 375–388, 2022.

[40] Anthony Leverrier and Gilles Z´emor. Quantum Tanner codes. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 872–883. IEEE, 2022.

[41] Nou´edyn Baspin and Anirudh Krishna. Quantifying nonlocality: How outperforming local quantum codes is expensive. Physical Review Letters, 129(5):050505, 2022.

[42] Sergey Bravyi, David Poulin, and Barbara Terhal. Tradeofs for reliable quantum information storage in 2D systems. Physical Review Letters, 104(5):050503, 2010.

[43] Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt. The thickness of graphs: a survey. Graphs and combinatorics, 14:59–73, 1998.

[44] Andrew Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 452(1954):2551–2577, 1996.

[45] A. Robert Calderbank and Peter W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54(2):1098, 1996.

[46] Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett, and Benjamin J. Brown. Low-overhead fault-tolerant quantum computing using long-range connectivity. Science Advances, 8(20), 2022.

[47] Nicolas Delfosse and Adam Paetznick. Spacetime codes of cliford circuits. arXiv preprint arXiv:2304.05943, 2023.

[48] Matt McEwen, Dave Bacon, and Craig Gidney. Relaxing hardware requirements for surface code circuits using time-dynamics. Quantum, 7:1172, 2023.

[49] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell. Improved decoding of circuit noise and fragile boundaries of tailored surface codes. Physical Review X, 13(3):031007, 2023.

[50] Gyorgy P. Geher, Ophelia Crawford, and Earl T. Campbell. Tangling schedules eases hardware connectivity requirements for quantum error correction. arXiv preprint arXiv:2307.10147, 2023.

[51] Joschka Rofe, David R. White, Simon Burton, and Earl Campbell. Decoding across the quantum low-density parity-check code landscape. Physical Review Research, 2(4):043423, 2020.

[52] Peter Groszkowski, Austin Fowler, and Ashley M. Stephens. High-threshold surface code quantum computing: threshold calculation. In APS March Meeting Abstracts, pages W17–002, 2009.

[53] Sergey Bravyi, Oliver Dial, Jay M. Gambetta, Dar´ıo Gil, and Zaira Nazario. The future of quantum computing with superconducting qubits. Journal of Applied Physics, 132(16), 2022.

[54] Pavel Panteleev and Gleb Kalachev. Quantum LDPC codes with almost linear minimum distance. IEEE Transactions on Information Theory, 68(1):213–229, 2021.

[55] Andrew J. Landahl, Jonas T. Anderson, and Patrick R. Rice. Fault-tolerant quantum computing with color codes. arXiv preprint arXiv:1108.5738, 2011.

[56] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004.

[57] Austin G. Fowler, Adam C. Whiteside, Angus L. McInnes, and Alimohammad Rabbani. Topological code autotune. Physical Review X, 2(4):041003, 2012.

[58] Oscar Higgott and Craig Gidney. Sparse blossom: correcting a million errors per core second with minimum-weight matching. arXiv preprint arXiv:2303.15933, 2023.

[59] Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory, 24(3):384–386, 1978.

[60] Joschka Rofe. LDPC: Python tools for low density parity check codes, 2022.

[61] Sergey Bravyi and Alexander Vargo. Simulation of rare events in quantum error correction. Physical Review A, 88(6):062308, 2013.

[62] Nikolas P. Breuckmann and Simon Burton. Fold-transversal Cliford gates for quantum codes. arXiv preprint arXiv:2202.06647, 2022.

[63] Christopher A. Pattison, Anirudh Krishna, and John Preskill. Hierarchical memories: Simulating quantum LDPC codes with local gates. arXiv preprint arXiv:2303.04798, 2023.

[64] Jerry Chow, Oliver Dial, and Jay Gambetta. IBM Quantum breaks the 100-qubit processor barrier, 2021.

[65] Paul Nation, Hanhee Paik, Andrew Cross, and Zaira Nazario. The IBM Quantum heavy hex lattice, 2021.

[66] Jared B. Hertzberg, Eric J. Zhang, Sami Rosenblatt, Easwar Magesan, John A. Smolin, Jeng-Bang Yau, Vivekananda P. Adiga, Martin Sandberg, Markus Brink, Jerry M. Chow, and Jason S. Orcutt. Laser-annealing josephson junctions for yielding scaled-up superconducting quantum processors. npj Quantum Information, 7:129, 2021.

[67] David C. McKay, Stefan Filipp, Antonio Mezzacapo, Easwar Magesan, Jerry M. Chow, and Jay M. Gambetta. Universal gate for fixed-frequency qubits via a tunable bus. Physical Review Applied, 6:064007, Dec 2016.

[68] J. Stehlik, D. M. Zajac, D. L. Underwood, T. Phung, J. Blair, S. Carnevale, D. Klaus, G. A. Keefe, A. Carniol M. Kumph, Matthias Stefen, and O. E. Dial. Tunable coupling architecture for fixed-frequency transmon superconducting qubits. Physical Review Letters, 127:080505, Aug 2021.

[69] F. Arute, K. Arya, R. Babbush, and et al. Quantum supremacy using a programmable superconducting processor. Nature, 574:505–510, 2019.

[70] David C. McKay, Ravi Naik, Philip Reinhold, Lev S. Bishop, and David I. Schuster. High-contrast qubit inter actions using multimode cavity qed. Physical Review Letters, 114:080501, 2015.

[71] Alexander Ivrii. Private communication, 2023.

A) Topology for each Ancilla System Layer

B) Implementation of Ancilla Systems in Thickness-2

Figure 8: Illustration of the thickness-2 property of the Tanner graph of BB LDPC codes. A) Planar embedding of each layer of the ancilla system from Figure 1 C) via truncating the $⟨\mathrm{A}⟩$ and ${\mathrm{\Delta }}^6{\mathrm{B}}^{\prime }$ wheels. B) Implementation of the graph from Figure 1 C) within thickness-2 by nesting wheels. Wheels corresponding to $X(f,0)$ are placed on the outside and wheels corresponding to $Z(h^T,g^{\dot{T}})$ are placed on the inside. The $X(f,0)$ system can be connected to a surface code in the ${\Omega }^{⟨}{\mathrm{A}}^{⟩}$ plane. Here we only show one layer per system, but this construction can be repeated for arbitrarily many layers.