```html Authors: Sergey Bravyi Andrew W. Cross Jay M. Gambetta Dmitri Maslov Patrick Rall Theodore J. Yoder Abstract Physical errors accumulating prevent the execution of large-scale algorithms in current quantum computers. Quantum error correction promises a solution by encoding logical qubits onto a larger number of physical qubits, such that the physical errors are suppressed enough to allow running a desired computation with tolerable fidelity. Quantum error correction becomes practically realizable once the physical error rate is below a threshold value that depends on the choice of quantum code, syndrome measurement circuit and decoding algorithm. We present an end-to-end quantum error correction protocol that implements fault-tolerant memory on the basis of a family of low-density parity-check codes. Our approach achieves an error threshold of 0.7% for the standard circuit-based noise model, on par with the surface code that for 20 years was the leading code in terms of error threshold. The syndrome measurement cycle for a length- code in our family requires ancillary qubits and a depth-8 circuit with CNOT gates, qubit initializations and measurements. The required qubit connectivity is a degree-6 graph composed of two edge-disjoint planar subgraphs. In particular, we show that 12 logical qubits can be preserved for nearly 1 million syndrome cycles using 288 physical qubits in total, assuming the physical error rate of 0.1%, whereas the surface code would require nearly 3,000 physical qubits to achieve said performance. Our findings bring demonstrations of a low-overhead fault-tolerant quantum memory within the reach of near-term quantum processors. k n n n Main Quantum computing attracted attention due to its ability to offer asymptotically faster solutions to a set of computational problems compared to the best known classical algorithms. It is believed that a functioning scalable quantum computer may help solve computational problems in such areas as scientific discovery, materials research, chemistry and drug design, to name a few. The main obstacle to building a quantum computer is the fragility of quantum information, owing to various sources of noise affecting it. As isolating a quantum computer from external effects 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 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. for a summary. Whereas some sources of noise can be eliminated with better control, materials and shielding, several other sources appear to be difficult if at all possible to remove. The last kind can include spontaneous and stimulated emission in trapped ions, and the interaction with the bath (Purcell effect) 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 is well-established. 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, 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 that offers a high error threshold close to 1%, fast decoding algorithms and compatibility with the existing quantum processors relying on two-dimensional (2D) square lattice qubit connectivity. Small examples of the surface code with a single logical qubit have already been demonstrated experimentally by several groups. However, scaling up the surface code to 100 or more logical qubits would be prohibitively expensive due to its poor encoding efficiency. This spurred interest in more general quantum codes known as low-density parity-check (LDPC) codes. Recent progress in the study of LDPC codes suggests that they can achieve quantum fault tolerance with a much higher encoding efficiency. Here, we focus on the study of LDPC codes, as our goal is to find quantum error correction codes and protocols that are both efficient 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 in only a few checks. Several variants of the LDPC codes have been proposed recently including hyperbolic surface codes, hypergraph product, balanced product codes, two-block codes based on finite groups and quantum Tanner codes. The latter were shown to be asymptotically ‘good’ in the sense of offering a constant encoding rate and linear distance: a parameter quantifying the number of correctable errors. By 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 practical implications. First, the fault-tolerance overhead (the ratio between the number of physical and logical qubits) could be reduced notably. Second, high-distance codes show 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 that 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 state preparation and measurement errors may require very large LDPC codes with more than 10,000 physical qubits. 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 efficient decoding algorithm and a fault-tolerant protocol for addressing individual logical qubits. These codes show an error threshold close to 0.7%, show excellent performance in the near-threshold regime and offer a 10 times 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. Our codes are a generalization of bicycle codes proposed by MacKay et al. and studied in more depth in refs.. We named our codes bivariate bicycle (BB) because they are based on bivariate polynomials, as detailed in the Methods. These are stabilizer codes of the Calderbank–Shor–Steane (CSS) type that can be described by a collection of six-qubit check (stabilizer) operators composed of Pauli and . At a high level, a BB code is similar to the two-dimensional toric code. 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 and 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 BB codes are not geometrically local. Furthermore, each check acts on six qubits rather than four qubits. We will describe the code by a Tanner graph such that each vertex of represents either a data qubit or a check operator. A check vertex and a data vertex are connected by an edge if the th check operator acts non-trivially on the th data qubit (by applying Pauli or ). See Fig. a,b for example Tanner graphs of surface and BB codes, respectively. The Tanner graph of any BB code has vertex degree six and graph thickness equal to two, which means it can be decomposed into two edge-disjoint planar subgraphs (Methods). Thickness-2 qubit connectivity is well suited for superconducting qubits coupled by microwave resonators. For example, 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. X Z X Z G G i j i j X Z , Tanner graph of a surface code, for comparison. , Tanner graph of a BB 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 ( ) and ( ) 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. We only show a few long-range edges to avoid clutter. Dashed and solid edges indicate two planar subgraphs spanning the Tanner graph, see the Methods. , Sketch of a Tanner graph extension for measuring and following ref., attaching to a surface code. The ancilla corresponding to the measurement can be connected to a surface code, enabling load-store operations for all logical qubits by means of quantum teleportation and some logical unitaries. This extended Tanner graph also has an implementation in a thickness-2 architecture through the and edges (Methods). a b q L q R c A B A BB code with parameters [[ , , ]] encodes logical qubits into data qubits offering a code distance , meaning that any logical error spans at least data qubits. We divide data qubits into registers ( ) and ( ) of size /2 each. Any check acts on three qubits from ( ) and three qubits from ( ). The code relies on ancillary check qubits to measure the error syndrome. We divide check qubits into registers ( ) and ( ) of size /2 that collect syndromes of and types, respectively. In total, the encoding relies on 2 physical qubits. The net encoding rate is therefore = /(2 ). For example, the standard surface code architecture encodes = 1 logical qubit into = data qubits for a distance- code and uses − 1 check qubits for syndrome measurements. The net encoding rate is ≈ 1/(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. By contrast, BB codes have encoding rate ≫ 1/ , see Table for code examples. To the best of our knowledge, all codes shown in Table are new. 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 = 1/24. For comparison, the distance-11 surface code has a net encoding rate = 1/241. Below, we show that the distance-12 BB code outperforms the distance-11 surface code for the experimentally relevant range of error rates. n k d k n d d n q L q R n q L q R n n q X q Z n X Z n r k n k n d 2 d n r d 2 r d 2 r r To prevent the accumulation of errors one must be able to measure the error syndrome frequently enough. This is accomplished by a syndrome measurement 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 syndrome measurement circuit is proportional to its depth: the number of gate layers composed of non-overlapping CNOTs. As new errors continue to occur while the syndrome measurement circuit is executed, its depth should be minimized. The full cycle of syndrome measurement for a BB code is illustrated on Fig.. The syndrome cycle requires only seven 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 the Methods for details). The circuit respects the cyclic shift symmetry of the underlying code. Full cycle of syndrome measurements relying on seven layers of CNOTs. We provide a local view of the circuit that only includes one data qubit from each register ( ) and ( ). The circuit is symmetric under horizontal and vertical shifts of the Tanner graph. Each data qubit is coupled by CNOTs with three *X-*check and three *Z-*check qubits: see the Methods for more details. q L q R The full error correction protocol performs ≫ 1 syndrome measurement cycles and then 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 returns data qubits to the initial logical sate. Otherwise, if the guessed and the actual error differ 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. The original work 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, see the Supplementary Information for details. Our approach closely follows refs.. N c A noisy version of the syndrome measurement circuit may include several types of faulty operations such as memory errors on idle data or check qubits, faulty CNOT gates, qubit initializations and measurements. We consider the circuit-based noise model in which each operation fails independently with probability . The probability of a logical error depends on the error rate , details of the syndrome measurement circuits, and the decoding algorithm. Let ( ) be the logical error probability after performing syndrome cycles. Define the logical error rate as . Informally, can be viewed as the logical error probability per syndrome cycle. Following common practice, we choose = for a distance- code. Figure shows the logical error rate achieved by codes from Table. The logical error rate was computed numerically for ≥ 10 and extrapolated to lower error rates using a fitting formula (Methods). The pseudo-threshold is defined as a solution of the break-even equation ( ) = . Here is an estimate of the probability that at least one of unencoded qubits suffers from an error. BB codes offer a pseudo-threshold close to 0.7%, see Table, which is nearly the same as the error threshold of the surface code and exceeds the threshold of all high-rate LDPC codes known to the authors. p p L p P L N c N c p L N c d d p −3 p 0 p L p kp kp k , Logical versus physical error rate for small examples of BB LDPC codes. A numerical estimate of (diamonds) was obtained by simulating syndrome cycles for a distance- code. Most of the data points have error bars roughly equal to /10 due to sampling errors. , Comparison between the BB LDPC code [[144, 12, 12]] and surface codes with 12 logical qubits and distance ∈ {9, 11, 13, 15}. The distance- surface code with 12 logical qubits has the length = 12 because each logical qubit is encoded into a separate × patch of the surface code lattice. a p L d d p L b d d n d 2 d d For example, suppose that the physical error rate is = 10 , which is a realistic goal for near-term demonstrations. Encoding 12 logical qubits using the distance-12 code from Table would offer the logical error rate 2 ×10 , which is enough to preserve 12 logical qubits for nearly 1 million syndrome cycles. The total number of physical qubits required for this encoding is 288. The distance-18 code from Table would require 576 physical qubits whereas suppressing the error rate from 10 to 2 ×10 enabling nearly hundred billion syndrome cycles. For comparison, encoding 12 logical qubits into separate patches of the surface code would require more than 3,000 physical qubits to suppress the error rate from 10 to 10 (Fig.). In this example, the distance-12 BB code offers 10 times saving in the number of physical qubits compared with the surface code. p −3 −7 −3 −12 −3 −7 A proposal for quantum error correction is only useful if the logical qubits are accessible. Fortunately, BB LDPC codes possess the required features to act as a logical memory. As shown in Fig.c, extensions of the Tanner graph leveraging techniques by Cohen et al. enable fault-tolerant measurement operations involving an ancillary surface code. These measurements enable fault-tolerant load-store operations. See the Supplementary Information for details. Our work highlights key hardware challenges to enable the new codes with superconducting qubits: (1) the development of low-loss second layer in the thickness-2 architecture; (2) the development of qubits that can be coupled to seven connections (six buses and one control line); and (3) the development of long-range couplers. These are all difficult to solve but not impossible. For the first challenge, we can imagine a small change to the packaging that was developed for the IBM Quantum Eagle processor. The simplest would be to place the extra buses on the opposite side of the qubit chip. This would require the development of high through substrate vias that would be part of the coupling buses and as such would require intensive microwave simulation to make sure these through substrate vias could support microwave propagation while not introducing large unwanted crosstalk. Q The second challenge is an extension of the number of couplers from the heavy hex lattice arrangement, which is four (three couplers and one control) to seven. 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. Qubits in cross-resonance gates are not tuneable and as such for a large device with many connections the probability of a energy collisions (not just the qubit levels but also higher levels of the transmon) trends to one very quickly. However, with the tuneable coupler in IBM Quantum Egret and now being developed for the IBM Quantum Heron, this problem no longer exists as qubit frequencies can be designed to be farther apart. This new gate is also similar to the gates used by Google Quantum AI, which have shown that a square lattice arrangement is possible. Extending the coupling map to seven connections will require notable microwave modelling; however, typical transmons have about 60 fF of capacitance and each gate is around 5 fF to get the appropriate coupling strengths to the buses, so it is fundamentally possible to develop this coupling map without altering the long coherence times and stability of transmon qubits. The final challenge is the most difficult. For the buses that are short enough so that the fundamental mode can be used, the standard circuit quantum electrodynamics 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.. In summary, we offer a new perspective on how a fault-tolerant quantum memory could be realized using near-term quantum processors with a small qubit overhead. Although these LDPC codes are not geometrically local, qubit connectivity required for syndrome measurements is described by a thickness-2 graph that 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 favourably with the surface code in the practically relevant range of error rates ≥ 0.1% offering the same level of error suppression with 10 times reduction in the qubit overhead. Meanwhile, it remains unclear whether our code examples can be scaled up while retaining the high encoding rate in the limit of large code length. p Methods Code construction We begin with a formal definition of BB codes. Let and be the identity matrix and the cyclic shift matrix of size × respectively. The th row of has a single non-zero entry equal to one at the column ( mod ) + 1. I ℓ S ℓ ℓ ℓ i S ℓ i ℓ For example, Consider matrices Note that = , = = , and = = . A BB code is defined by a pair of matrices xy yx x T x y T y I ℓm x ℓ y m I ℓm where each matrix and is a power of or . Here and below the addition and multiplication of binary matrices is performed modulo two, unless stated otherwise. Thus, we also assume the are distinct and the are distinct to avoid cancellation of terms. For example, one could choose = + + and = + + . Note that and have exactly three non-zero entries in each row and each column. Furthermore, = because = . The above data defines a BB quantum code denoted QC( , ) with length = 2 and check matrices A i B j x y A i B j A x 3 y y 2 B y 3 x x 2 A B AB BA xy yx A B n ℓm Here the vertical bar indicates stacking matrices horizontally and stands for the matrix transposition. Both matrices and have size ( /2) × . Each row $\mathbf{r}$ of defines an -type check operator $X_{\mathbf{r}} = \prod_{j=1}^{n} X_j^{r_j}$ and each row $\mathbf{r}$ of defines a -type check operator $Z_{\mathbf{r}} = \prod_{j=1}^{n} Z_j^{r_j}$. Any and checks commute as they overlap on even number of qubits (note that $A_i B_j$ has even weight for all $i,j$). By construction, the code QC( , ) has weight-6 check operators and each qubit participates in six checks (three -type plus three -type checks). Accordingly, the code QC( , ) has a degree-6 Tanner graph. One can view the matrices and as bivariate polynomials over the variables and . Specializing BB codes to the case = 1 and = gives the original bicycle codes based on univariate polynomials. Likewise, BB codes are a specialization of the generalized bicycle codes, two-block group-based codes and polynomial-based codes. Given a binary matrix , let Null( ) be its nullspace spanned by all binary vectors such that =0. Let rs( ) be the row space of spanned by rows of . T H X H Z n n H X X H Z Z X Z A B X Z A B A B x y m B A T M M v M v M M M Lemma 1 The code QC( , ) has parameters [[ , , ]], where A B n k d The code offers equal distance for -type and -type errors. X Z The proof, relying on elementary linear algebra, is deferred to the Supplementary Information. Extended Data Table describes the polynomials and that give rise to examples of high-rate, high-distance BB codes found by a numerical search. This includes all codes from Table and two examples of higher distance codes. To the best of our knowledge, all these examples are new. The code [[360, 12, ≤24]] improves on a code [[882, 24, ≤24]] with weight-6 checks found by Panteleev and Kalachev in ref. (assuming that our distance upper bound is tight). Indeed, taking two independent copies of the 360-qubit code gives parameters [[720, 24, ≤24]]. Appendix C in ref. also describes a code [[126, 12, 10]] that has parameters similar to ours. This code has a form QC( , ) with = 1 + + , = 1 + + , = 63 and = 1. We note that the recent work by Wang, Lin and Pryadko 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 ref. outperform our BB codes with weight-6 checks in terms of the parameters , , . 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. A B A B A x 43 x 37 B x 59 x 31 ℓ m n k d In the following, we partition the set of data qubits as [ ] = ∪ , where ≔ ( ) and ≔ ( ) are the left and right blocks of /2 = data qubits. Then, data qubits and and checks and may each be labelled by integers 1, ..., 3 , which are indices into the matrices , . Alternatively, qubits and checks can be labelled by monomials from {1, , ..., } × {1, , ..., } in this order, so that ( , ) labels the same qubit or check as ( ) for , ∈ {0,..., -1} and , ∈ {0,..., -1}. Using the monomial labelling, data qubit is part of checks $\sum_i A_i x^{a} y^{b}$ and checks $\sum_j B_j x^{a} y^{b}$ for =1, 2, 3. Similarly, data qubit is part of checks $\sum_i A_i^T x^{a} y^{b}$ and checks $\sum_j B_j^T x^{a} y^{b}$. A unified notation assigns each qubit or check a label ( , ) where ∈ { , , , } denotes its type and its monomial label. (The monomial notations should not be confused with the matrix notations used earlier in this section. For example, multiplication of monomials such as is different from multiplying a vector by a matrix ). n L R L q L R q R n ℓm L R X Z ℓm A B x x −1 ℓ y y −1 m x a y b x c y d x + mod a c ℓ y + mod b d m a c ℓ b d m L x a y b X Z i R x a y b X Z q T α T L R X Z α B iα α B i One drawback of high-rate LDPC codes is that their Tanner graphs may not be locally embeddable into the 2D grid. This poses a challenge for hardware implementation with superconducting qubits coupled by microwave resonators. A useful very-large-scale integration (VLSI) design concept is graph thickness, see refs. for details. A graph = ( , ) is said to have thickness if one can partition its set of edges into disjoint union of sets ⊔ ⊔…⊔ = such that each subgraph ( , ) is planar. Informally, a graph with thickness can be viewed as a vertical stack of planar graphs. Qubit connectivity described by a planar graph (thickness = 1) is the simplest one from hardware perspective because the couplers do not cross. G V E θ E θ E 1 E 2 E θ E V E i θ θ θ Here we show that the Tanner graph of any BB code has thickness-2. This
