The theory of quantum error correction [1][2][3][4][5][6][7][8][9][10] opens the path towards large-scale quantum computation. Stabilizer codes are a conventional choice of quantum error-correcting codes [7,8,11], where error correction is performed conditional on the measurement outcomes of a set of code stabilizers, also known as the error syndrome bit string. The syndrome extraction circuits need to be fault tolerant [9,[12][13][14][15][16][17][18] as the act of measuring syndromes also introduces extra errors in the quantum system.
The first fault-tolerant syndrome extraction scheme was proposed by Shor [9,10]. In Shor's scheme, each syndrome bit is extracted from the data qubits to a verified ancilla cat state by transversal two-qubit gates. As transversal operations limit the error propagation, no high-weight correlated errors can occur on the data qubits if the cat states are verified by postselection. The value of the syndrome bit is the parity of the transversal measurement outcome of the cat state. As any measurement error will flip the syndrome bit, for a stabilizer code of distance d, one needs to repeat the syndrome extraction for O(d 2 ) rounds to guarantee fault tolerance. Utilizing the information of the code structure, the time overhead can be significantly reduced on particular codes [19][20][21][22][23][24]. Optimizing Shor's scheme is an active area of research building off substantial progress since its invention. For example, for low-weight stabilizers, ancilla postselection could be avoided by decoding the ancilla cat states [16,25,26]. On specific stabilizer codes, the space overhead can be reduced by allowing nontransversal data-ancilla interactions that preserve the code distance [19,[26][27][28][29][30][31][32]. The time overhead can also be reduced by careful choice of sequential extractions [23,24]. Notably, as an alternative to cat-state measurements, flag error-correction gadgets [16][17][18]30] circumvent the need of ancilla postselection for arbitrary stabilizer codes, while having a low-qubit overhead for low-distance codes or highdistance codes with low-weight stabilizer measurements.
The extraction gadgets for Shor's scheme are arguably the smallest. As a tradeoff, a large number of two-qubit gates are applied between data and ancilla qubits. For many quantum devices, two-qubit gates are usually the most challenging operations to implement with high fidelity [33,34]. To minimize the data-ancilla interaction, Steane [13] and Knill [15] suggested the use of transversal two-qubit gates to transfer the errors from the data block to an ancilla code block and then measurement of the ancilla block to gain error information. Steane's scheme is specialized for Calderbank-Shor-Steane (CSS) codes [5,6] and needs two separate rounds of transversal two-qubit gates for extracting the X -and Z-type stabilizers, respectively. Knill's scheme works for arbitrary stabilizer codes and only needs one round of the transversal gate to extract all the stabilizers. Using a constant number of Steane or Knill syndrome extractions, an arbitrary logical Clifford circuit can be implemented fault tolerantly in O (1) steps [35]. Both Steane's and Knill's schemes are single shot, i.e., no repetition of measurements is required. Indeed, each data qubit is touched by O(1) two-qubit gates. However, comparing to a cat state, the ancilla blocks for both Steane's and Knill's schemes are much harder to prepare, as they are as large as the data block [14,[36][37][38][39].
A natural question to raise is whether it is possible to balance the complexities of ancilla preparation and data-ancilla interaction. In Ref. [40] we gave a positive answer for CSS codes and in this companion paper we elaborate on the theory behind the method and present additional numerical details. We have generated a family of extraction circuits including Shor's and Steane's constructions as its two extremes. This family increases the complexity of ancilla construction in exchange for reducing the number of two-qubit gates between data and ancilla qubits required to fault-tolerantly measure the error. Applying our construction on the toric code, we are able to use a single ancilla block to measure the plaquette operators (Z-stabilizer elements) inside any connected sublattice. In particular, one can partition the L × L toric lattice into patches, each of which contains m × m plaquettes. Shor's and Steane's schemes correspond to the special cases m = 1 and m = L, respectively. Moreover, by offsetting the partition periodically, one can achieve fault tolerance within O(L/m) measurement rounds. Indeed, the parameter m simultaneously controls the ancilla-block size and the time overhead of fault tolerance. Our result is compatible with the fact that Shor's and Steane's schemes require O(L) and O(1) measurement rounds on the toric code, respectively.
Our paper is organized as follows. In Sec. II we review the essential background and present our notation. In Sec. III we discuss the construction of our family of extraction circuits. In particular, a subfamily called transversal gadgets is proposed. In Sec. IV we discuss the application of transversal gadgets on the toric code and analyze the time overhead of fault-tolerant syndrome measurements. We conclude with a summary and discussion in Sec. V.
We start by developing our notation for connecting sets and binary vector spaces. Given a set , we can define a vector space V where each vector corresponds to a finite subset A ⊆ , and vector addition is defined as the symmetric difference of two finite subsets of , i.e., for any two finite subsets A, B ⊆ we define A + B := (A ∪ B) \ (A ∩ B). The symmetric difference yields A + A = ∅ and as a result V is a binary vector space. For convenience, each element w ∈ is associated with two other meanings: a subset {w} ⊆ and indeed a vector {w} ∈ V . We can then simplify the equation A = w∈A {w} as A = w∈A w for every A ∈ V . As a result, we have
i.e., V is the binary vector space spanned by the set , denoted by F 2 [ ]. The cardinality of a finite subset A ⊆ , |A|, is also referred to as the weight of the vector
are said to be orthogonal if and only if φ, ψ = 0. More generally, two vector subspaces V, W ⊆ F 2 [ ] are said to be orthogonal (denoted by V ⊥W ) if we have v, w = 0 for every v ∈ V and w ∈ W .
Let and be two sets and M : F 2 [ ] → F 2 [ ] be a linear map. The kernel and image of M are denoted by ker M and im M, respectively. When and are finite, the transpose of M is defined to be a linear map
for every a ∈ and b ∈ . In other words, under the standard bases and , the matrix M T is the transpose of the matrix M. We also define the transpose of a vector φ ∈ F 2 [ ], denoted by φ T , as the map
(
We now briefly discuss linear codes. Let be a set of n classical bits. A linear code on is a subspace
The vectors of C are called codewords. A parity-check matrix H of C is a linear map from F 2 [ ] to some other F 2 -vector space, F m 2 , such that C ⊆ ker H. In this work, we are not required to have C = ker H. The dual code of C is defined by
for every c ∈ C.
Let be a set of n qubits. The state space of the quantum system is denoted by
The Pauli group on is denoted by P . For each qubit q ∈ , the Pauli X and Z operators on H q are denoted by X q and Z q , respectively. For each subset ψ ⊆ , the X -type and Z-type operators supporting on ψ are defined by
and
respectively. Note that
A stabilizer code on is defined by an Abelian subgroup S ⊆ P such that every operator P ∈ S has eigenvalues ±1 and -1 H / ∈ S. The corresponding code space C Q is the common +1 eigenspace of all the operators in S. In particular, if dim C Q = 1, the unique state in C Q (up to a constant) is said to be a stabilizer state. If S = S X ⊕ S Z , where elements in S X (S Z ) are all X type (Z type), we say that S = S X ⊕ S Z is a Calderbank-Shor-Steane code [5,6] and S X and S Z are the X and Z stabilizers, respectively. We can represent S X and S Z by two binary vector subspaces
and
respectively. Note that for any ψ, φ ⊆ , X [ψ] and Z[φ] commute with each other if and only if ψ and φ are orthogonal. As S = S X ⊕ S Z is Abelian, we must have C X ⊥C Z . In this paper, we prefer the binary vector space representation of CSS codes and use the notation C X ⊥C Z to denote a CSS code. For a CSS code C X ⊥C Z with a codespace
Thus we say that C X ⊥C Z encodes k logical qubits. For any vector ψ ∈ C ⊥ Z , X [ψ] commutes with any stabilizer and hence must be a logical operator. Similarly, for any φ ∈ C ⊥ X , Z[φ] is a logical operator. In fact, we can always find k vectors ψ 1 , . . . ,
Indeed, Xi and Zi can be regarded as the logical Pauli X and Z operators of the ith logical qubit, respectively.
On a stabilizer code, the errors are detected by measuring the stabilizer elements. For CSS codes, it is natural to measure the Z-and X -stabilizer elements so that the X errors (bit flips) and the Z errors (phase flips) can be handled separately. Here we are regarding a Y error as the combination of an X error and a Z error. In this paper, we focus on Z-stabilizer measurements, since an analysis of X -stabilizer measurements would be the same up to a Hadamard transform.
Let C X ⊥C Z be a CSS code on a set of data qubits D with a codespace C Q ⊆ H D . Suppose we have an X error X [ψ] (ψ ⊆ D) and we are measuring the Z-stabilizer elements {Z[φ b ]} b∈B , where φ b ∈ C Z and B is a finite set of syndrome bits. For each syndrome bit b ∈ B, the outcome of the measurement Z[φ b ] is determined by the value φ T b ψ ∈ F 2 . The binary vector
is called the syndrome. The map H = b∈B bφ T b is called a Z-check matrix of the CSS code C X ⊥C Z . Note that we do not require the condition im H T = C Z . However, we do require that im
If we are at the end of the computation, the syndrome of a Z-check matrix H can be obtained by measuring all qubits of D in the Z basis: If D is measured to be in the state |ψ ∈ H D , where ψ ∈ F 2 [D], then the syndrome is simply Hψ. In the intermediate steps, however, we are not allowed to measure the data qubits directly, as the single-qubit Z measurements anticommute with the X -stabilizer elements. A general idea shared by both Shor's and Steane's syndrome extraction protocols is to transfer the X errors to a set of ancilla qubits A by CNOT gates: As the CNOT gate propagates the X errors on the control qubit to the target qubit, we can perform CNOT gates with controls in D and targets in A and then apply Z measurements on all ancilla qubits to detect these errors. Of course, this is far from being a valid construction. In the following, we explore the necessary and sufficient conditions for a valid extraction circuit. To simplify our problem, we do not initially consider the challenge of fault tolerance.
As a first step, we encode the information of the CNOT gates by a matrix :
, where for each data qubit d ∈ D and ancilla qubit a ∈ A, a T d = 1 if and only if a CNOT gate with control d and target a is applied. As these CNOT gates commute with each other and we do not consider the fault-tolerance properties, the order of these CNOT gates does not matter. The product of all CNOT gates is denoted by U . One can easily verify the identities
where
Suppose the ancilla block A is prepared in a state |anc . When there are no errors on the data block D, the action of U is required to be trivial, i.e., for any code state |ω ∈ C Q , we should have
Note that the code space C Q is spanned by
where |+ k , the logical |+ k state, is the CSS stabilizer state of C ⊥ Z ⊥C Z . This is true because we have enumerated all the logical Z-type operators. From (13), Z[φ] commutes with U for any φ ⊆ D. Thus ( 14) can be simplified as
we can obtain Hψ = H ψ, the syndrome of H, by measuring all qubits of A in the Z basis. One could naturally ask the following question.
Question 1. Given two matrices H :
Suppose we already have a satisfying ancilla state |anc for a given H and . In (17), if we take ψ ∈ C ⊥ Z and combine ( 16), we will have
On the other hand, let CZ ⊆ F 2 [A] represents the Z-stabilizer group of |anc . For every φ ∈ CZ we have
Therefore, T φ ∈ C Z and hence
The conditions ( 18) and ( 19) imply that U preserves the CSS stabilizer group
If CX = C⊥ Z , i.e., |anc is a CSS stabilizer state and hence |+ k |anc is the stabilizer state of ( 20), the condition ( 16) must hold.
Our problem now becomes finding a CSS stabilizer state |anc with X and Z stabilizers CX and CZ ( CX = C⊥ Z ), respectively, satisfying ( 18), (19), and the condition im HT ⊆ CZ . A natural strategy is to minimize CZ and maximize CX = C⊥ Z . The minimal choice of CZ is just im HT as required. The following lemma shows that CZ = im HT and CX = ker H always satisfy (18) and (19).
Lemma 1. T (im HT ) ⊆ C Z and (C ⊥ Z ) ⊆ ker H . Proof. The first part follows from a direct calculation
The latter part is also straightforward: For any ψ ∈ C ⊥ Z , we have H ψ = Hψ = 0. Thus ψ ∈ ker H.
From the discussion above, we can conclude that given a Z-check matrix H of C X ⊥C Z , any decomposition H = H corresponds a valid gadget extracting the syndrome of H. All the information of the gadget is determined by H and , which allows us to define a gadget in an abstract way.
where A is the set of ancilla qubits, B is the set of syndrome bits, and H :
Here H, H, and are referred to as the data check matrix, ancilla check matrix, and gate matrix, respectively. The ancilla block A is prepared in the CSS state of ker H⊥im H T , while the gate applied between D and A is U .
If we apply two gadgets
The gate matrix and the ancilla check matrix H are defined by = 1 2 (21) and
respectively. The total parity check matrix
We say that G is a sum of G 1 and G 2 , denoted by
We now review Shor's and Steane's constructions in our notation.
Example 1 (Shor's scheme). In Shor's scheme [9,10], Example 2 (Steane's scheme). In Steane's scheme [13], all the Z-stabilizer elements are extracted by one ancilla block. The ancilla block A is a set identical to the data block D. The gate matrix is an identity matrix under the standard bases, and the ancilla check matrix H is identical to the data check matrix H. The ancilla state is the CSS stabilizer state of
where k is the number of logical qubits.
Shor's scheme benefits from having small transversal catstate gadgets with ancilla blocks whose sizes are defined by the weight of the measured stabilizers, |A b | = |φ b |. If the stabilizers are measured in a serial manner, one only needs a number of ancilla qubits equal to the highest-weight stabilizer max b (|φ b |). Parallel syndrome measurement is desirable and one will need F ancilla qubits where F = b∈B |φ b |. If each one of the n data qubits interacts on average with f measured stabilizers, then we can also write F = f n. Measurements need to be repeated T times until errors due to measurement can be distinguished from errors on the data; T can scale as O(d 2 ) [9,23,24] in the worst case, but scales as O(d ) for topological codes [19].
Steane's scheme requires large ancilla-block size equal to the data block. However, only one block is needed for Z extraction. The total number of ancilla qubits is just n, which is less than the f n needed for the parallel Shor scheme. In addition, Steane's scheme is a single-shot method, so T is constant. The cost of Steane's scheme is the preparation and verification of the ancilla block, which becomes challenging as the code distance increases. However, if we can prepare the ancilla, it greatly reduces the number of interactions between the data block and the ancilla block before correction is applied.
Our goal is to construct gadgets other than Shor-and Steane-style ones that result in simplified ancilla blocks compared to Steane's and fewer interactions between data and ancilla than Shor's. Conceptually, we can start with Shor ancilla blocks and merge ancilla blocks in a way that removes ancilla qubits. We now describe this procedure in detail.
We start from Shor's cat-state syndrome measurement circuit, denoted by G = (A, B, H , ). For every ancilla qubit a ∈ A, it interacts with exactly one data qubit and transfers the error to exactly one syndrome bit, i.e., | T a| = | Ha| = 1. In matrix language, each row of and each column of H contains exactly one nontrivial entry. We construct gadgets by applying a series of steps, each of which is described by one of the following operations.
(i) Pick two ancillas It is easy to check that the updated H and satisfy the condition H = H . If we only apply (i), each row of will always have exactly 1 nontrivial entry. Indeed, the gadget will be transversal on the ancilla. Assuming the ancilla block can be fault-tolerantly prepared by postselection so that no correlated errors can occur, a transversal gadget will not introduce correlated errors to the data block. If we keep doing (i), we will eventually obtain Steane's scheme. On the other hand, if we only apply (ii), we make the cat states smaller and introduce nontransversal interactions. The extreme case where no ancilla can be further merged is the bare-ancilla scheme.
By allowing both types of ancilla merging, we can generate a large number of gadgets. In fact, arguably, all the gadgets can be generated in this way. To see this, for any gadget G = (A, B, H , ) we can split each ancilla qubit a ∈ A into | T a| × | Ha| ancilla qubits: With each data qubit q ∈ T a and syndrome bit b ∈ Ha ⊆ B, we associate an ancilla qubit to pass the X error on q to b. The obtained gadget is Shor's cat-state syndrome measurement scheme, and the reverse of the splitting provides us the merging steps from Shor's scheme to G.
However, such an argument has a few exceptions. First, if | T a| = 0 or | Ha| = 0, a will be split into 0 qubits so that the process is irreversible. Second, for each data qubit q and each syndrome bit b, the number of ancilla qubits connecting them after splitting, whose parity is b T Hq, can be more than 1. In contrast, for Shor's scheme, there must be exactly b T Hq ∈ {0, 1} ancilla qubits. To handle these exceptions, we can introduce pairs of redundant ancilla qubits to Shor's scheme before merging: Each pair of ancilla qubits passes the error on the same data qubit to the same syndrome bit. After merging, we can add ancilla qubits that only connect syndrome bits. Of course, we can add ancilla qubits that only connect data qubits as well. These ancilla qubits, however, are not helpful for gaining error information.
The tradeoffs of two merging operations are different: Operation (i) reduces the number of CNOT gates between data and ancillas while making the ancilla block more entangled; (ii) simplifies the ancilla-block preparation while taking the risk of introducing correlated errors and breaking fault tolerance. If we wish to have postselection-free ancillas, the stabilizer generators of the ancilla block should have weight no more than 3 so that the residual error of each single error in the preparation circuit can be reduced to a weight-1 error. Bare ancillas, Bell states, and three-qubit Greenberger-Horne-Zeilinger states are example states that satisfy this requirement. More generally, any CSS state equivalent to a one-dimensional cluster state (up to Hadamard gates) can be directly prepared. To preserve the code distance, the correlated errors introduced by these simple gadgets need to be handled by either a well-designed decoder or modifications to the decoding circuits, such as flag qubits [16,18,30] and DiVincenzo-Aliferis ancilla decoding [25]. However, as the matrix decomposition H = H inherits the code structure from H, the detailed fault-tolerance design will be code specific.
In Fig. 1 we illustrate how to obtain syndrome extraction methods for Steane's seven-qubit code by applying merging operations on Shor's scheme. Instead of applying only one type of operation, we can apply both. As an example, we apply (i) on Shor's scheme twice to obtain a transversal gadget (referred to as scheme A in Fig. 1) and then apply (ii) five times to obtain a non-fault-tolerant circuit (referred to as scheme B) whose ancilla state can be prepared without verification. As Steane's code has distance 3, one can apply a DiVincenzo-Aliferis decoding circuit [25] to make scheme B fault tolerant. The details of the protocol are given in Appendix A.
When measurement errors are being considered, the use of different extraction gadgets will lead to different decoding problem details. In the next section, as an example, we will study the behavior of transversal gadgets on Kitaev's toric code [4] thoroughly. In particular, we will show that by switching between different gadgets, the time overhead of fault tolerance can be reduced without increasing the ancilla complexity.
We briefly review the construction of the toric code [4]. A toric code is a CSS code defined on an L × L periodic lattice on the torus. The lattice has a set V of L 2 vertices, a set E of 2L 2 edges, and a set F of L 2 faces. Define the boundary map
and the coboundary map
For each
] code, we show how to construct syndrome extraction circuits by merging ancilla qubits in Shor's scheme. In the circuit diagram, the labeled sets of the data qubits, ancilla qubits, and syndrome bits are {1, . . . , 7}, {1 , . . . , 12 }, and {a, b, c}, respectively. The syndrome bits can be determined by a collective measurement of the labeled qubit outputs. Two ancilla qubits can be merged if they (i) talk to the same set of data qubits or (ii) contribute to the same set of syndrome bits. If we repeat application of rule (i), we will eventually obtain Steane's scheme. Bare-ancilla extraction is the limit for applying rule (ii) only. For example, we demonstrate scheme A, a transversal gadget obtained by applying (i) to Shor's scheme twice, and scheme B, obtained by applying (ii) on scheme A five times. We illustrate the matrix decomposition description H = H of these gadgets. Empty elements in H are zeros, which are not shown to emphasize the block structure. The Z-and X -stabilizer generators are generated from im HT and ker H , respectively. We note that the ancilla state for scheme B is (|000 + |111 ) ⊗ (|00 + |11 ), which can be directly prepared without verification. However, as the circuit is not transversal on the ancilla block, we will require a DiVincenzo-Aliferis decoding circuit [25] to achieve fault tolerance. The details are given in Appendix A.
edge set E . A nontrivial logical Z-type (X -type) operator is represented by a noncontractible loop (cut) on the torus, which has minimum length L. In other words, the toric code has distance L. The Z-and X -check matrices of the toric code are ∂ T and δ T , respectively. A Z-extraction gadget is therefore represented by a decomposition ∂ T = ∂T γ T , or ∂ = γ ∂. The matrices ∂T and γ T are the ancilla check and gate matrices, respectively.
The Shor-style extraction gadget, denoted by ( Ẽ0 , F, ∂T 0 , γ T 0 ), can be understood as cutting the torus into L 2 disjoint square faces. The set Ẽ0 contains the 4L 2 edges of these squares. For two edges ẽ1 , ẽ2 ∈ Ẽ0 , if they were the same edge γ 0 ẽ1 = γ 0 ẽ2 ∈ E before the torus was cut, we can glue the two edges back, which corresponds to a type-(i) merging of ancilla qubits ẽ1 and ẽ2 . Therefore, any transversal gadgets can be constructed by cutting the torus along some chosen edges. If we do not make any cut, the gadget will be Steane style; if we choose to cut along all edges, we will obtain the Shor-style gadget. In general, we will obtain a new topological space, with an edge set Ẽ and a boundary map ∂ :
maps an edge ẽ ∈ Ẽ back to its corresponding edge e ∈ E on the torus. The boundary of the space is ∂F ⊆ Ẽ . Here, as a reminder, F is viewed as an F 2 -vector. If we cut along an edge e ∈ E so that |γ T e| = 2, we must have γ T e ⊆ ∂F . If we cut the torus into several connected components so that the face set F is decomposed as F = i F i , where each F i is the face set of a component, then the gadget ( Ẽ , F, ∂T , γ T ) can be decomposed as
where each Ẽi := f ∈F i ∂ f is the set of edges of the component F i , ∂| F i is the restriction of ∂ on F i , and γ | Ẽi is the restriction of γ on Ẽi . That is, the ancilla block Ẽ is decomposed as subblocks Ẽi , and two different blocks are not entangled.
We now describe our model of fault-tolerant error correction following the presentation in Ref. [40]. As X and Z errors can be corrected separately, we can ignore the Z errors on the data qubits and the X -stabilizer measurements. Suppose our computation starts from time 0 and never ends. We extract the Z-check matrix ∂ at every positive integer time. For every t ∈ Z + , each data qubit could have an X error at time t -1 2 , and the measurement outcome of each ancilla qubit at time t could have a classical bit-flip error. For now, we ignore the data errors between two CNOT gates in the same extraction round.
Suppose the transversal gadget applied at time
, where γ t ∂t = ∂. An X error on the data qubit e ∈ E at time t - 1 2 is denoted by the pair (e, t ). The measurement error on the ancilla qubit ẽ ∈ Ẽt at time t ∈ T is denoted by the pair (ẽ, t ). The set of all single data-qubit errors, denoted by D, is
while the set of measurement errors, denoted by M, is
An error history is defined to be a finite subset ψ ⊆ D ∪ M, or equivalently a vector
For later convenience, the time coordinates of the errors are discarded. Similarly, the evaluation of measurement errors at time t is a map
The data error propagating to the ancilla block Ẽt is the accumulation of all data errors before time t, which can be evaluated by the map
In particular, we define D := t∈N D t . The syndrome at time t can therefore be evaluated by the map
We can take the difference of the syndrome sequence {σ t } t∈N ,
In the above calculation, we set σ 0 = 0, D0 = 0, and M 0 = 0 for convenience. We can see that the data error D t only contributes to t , while the measurement error M t contributes to both t and t+1 . The syndrome history is defined as a map
We now analyze the behavior of each single error. For each data error (e, t ), one can verify that
where f 1 , f 2 ∈ F are the two faces sharing e as their borders.
For each measurement error (ẽ, t ) ∈ M, where ẽ ∈ Ẽt , one can verify that
If ẽ ∈ ∂t F , i.e., ẽ is an split edge, ∂T t ẽ has only one face and we say that (ẽ, t ) is a type-I error. Otherwise, | ∂T t ẽ| = 2 and (ẽ, t ) is said to be a type-II error. The set of type-I errors, denoted by M 1 , is
while the set of type-II errors is denoted by
The syndrome bit flips can be viewed as defects in the (2 + 1)-dimensional lattice: Each data error creates two defects in the same time slice: Each type-I error creates two defects on the same location, but in two consecutive time slices, and each type-II error creates four defects. We give an example of the effect of different error types in Fig. 2. If G t is a Shor-style gadget, all measurement errors at time t will be of type I, and the data and measurement errors are referred to as spacelike and timelike errors, respectively [19]. If G t is a Steanestyle gadget, however, all measurement errors at time t will be of type II.
will take ψ as the input and output an estimation of error history ψ = Dec( ψ ) such that ψ = ψ. The optimal choice of the decoder is the minimum-weight-error (MWE) decoder Dec MWE defined by
If the gadgets are all Shor style so that M = M 1 , the decoding problem can be visualized by a decoder graph G with vertex set F × N and edge set D ∪ M 1 : Each ( f , t ) ∈ F × N is a vertex and each error ψ ∈ D ∪ M 1 is an edge connecting the two vertices (defects) in ψ. The error histories are also called error chains, as they can be visualized as sums of chains in G. Note that the map evaluates the boundary of a given error chain. Decoding a syndrome ψ is essentially finding an error chain ψ whose boundary coincides with ψ. As an error chain ψ always matches the defects in ψ into pairs, the MWE decoder returns a minimum-weight perfect matching (MWPM) of the defects [19,27,41].
The existence of type-II errors complicates our problem, as they create four defects instead of two. We have to use hyperedges to represent these errors in the decoder (hyper)graph. Although we can still use a MWE decoder, the geometric meaning will be less clear. Notice that for any type-II error (ẽ, t ) ∈ M 2 is equivalent to two data errors (γ t ẽ, t ) + (γ t ẽ, t + 1) ∈ F 2 [D]. As an approximation, we can pretend that the type-II errors do not exist and use the MWPM decoder
on the decoder graph with an edge set D ∪ M 1 . For convenience, we define a map
that projects all the errors onto the decoder graph. For each error history ψ ∈ F 2 [D ∪ M], the MWPM decoder will regard it as an error chain ψ on the decoder graph with total length The ancilla blocks when aligned lead to timelike correlations between direct repeated measurements. (d) By offsetting the ancilla blocks, the timelike correlations require spacelike errors in order to correlate defects from top to bottom. The images in (c) and (d) have been reproduced from Ref. [40].
Indeed, the MWPM decoder can only guarantee that
However, as shown below, Dec MWPM can preserve the code distance L. Theorem 1. If |ψ| < L/2, Dec MWPM will correct ψ without introducing a logical error.
Proof. Let ψ = Dec MWPM ( ψ ). By applying the correction ψ , the data error will become an undetectable error D(ψ + ψ ). Since the toric code has distance L, it suffices to show that | D(ψ + ψ )| < L.
From ( 41) and the fact that |ψ ∩ D| |ψ |, we obtain
The theorem is proved by combining (42) and the fact that
In practice, the circuit will always end in some finite time T . All the errors and defects can only occur before T . Indeed, the MWPM decoder will have a finite decoder graph of size O(T L 2 ). As the MWPM algorithm runs in polynomial time to the input size, for the purpose of reliable quantum memory, we can delay the decoding until the end of the circuit execution. However, this will be impractical for quantum computation tasks with non-Clifford gates [42]. Instead, we need to process the syndrome bits and correct the errors as soon as possible. As the information provided by the latest syndrome bits is always unreliable, they will be processed only when further syndrome bits are gathered. For example, we can divide the time axis by some chosen time
In the ith round of error correction, we decode the syndrome bits in the time interval [t i , t i+2 ) but only correct the errors in [t i -1 2 , t i+1 -1 2 ); then we discard the syndrome bits in [t i , t i+1 ) while keeping the syndrome bits in [t i+1 , t i+2 ) for the next round of correction. Note that the syndrome bits at time t i+1 need to be updated. This is known as the overlapping recovery method [19,23]. The details are formally described in Procedure 1, for which we define
and
for convenience.
Procedure 1 Overlapping recovery.
1:i ← 1.
2: Use MWPM to find an error history ψ such that
. // Correct the error history. In practice, this is equivalent to applying error correction on the data qubits and updating the syndrome at time t i+1 .
In the ith iteration of Procedure 1, the decoder graph for MWPM only contains the vertices (syndrome bits) and edges (errors) in [t i -1 2 , t i+2 -1 2 ). In particular, the type-I errors at time t i+2 -1 will become open edges, i.e., edges connecting to the time boundary. The defects not only can be paired with each other, but also can be fused with the time boundary so that its lifetime is extended to the next round. Intuitively, if the distance from time slice t i to t i+1 on the decoder graph, denoted by d (t i , t i+1 ), is too small, it would be too easy for the decoder to fuse a defect at time t i to the time boundary. As a consequence, errors can hardly be corrected. If we use the Shor-style gadget all the time, we will have d (t i , t i+1 ) = |t i+1t i |, and it has been shown that |t i+1t i | = O(L) suffices for fault tolerance [19]. Naturally, the result should be generalized as d (t i , t i+1 ) = O(L) for arbitrary choices of gadgets. To show this, we prove the following.
Theorem 2. In the ith round of error correction, if the correction ψ creates a propagating error, i.e., ψ + ψ contains a path from the time slice t i to the time slice t i+1 , then |ψ[t i , t i+1 ]| 1 2 [d (t i , t i+1 ) -L]. Proof. Suppose ψ + ψ contains a path P 1 from a vertex ( f 1 , t i ) to some vertex ( f 2 , t i+1 ), where f 1 , f 2 ∈ F . Then ψ + ψ must contain another path P 2 from a vertex ( f 1 , t i ) to a vertex ( f 2 , t i+1 ), where f 1 , f 2 ∈ F and P 1 ∩ P 2 = ∅. We must have
Adding | ψ ∩ P 1 | + | ψ ∩ P 2 | to both side of (48) and combining (46), we obtain
Given the gadgets {G t } t∈N , we can choose the time slices {t i } i∈N such that d (t i , t i+1 ) αL = O(L) for some constant α 1. By Theorem 2, to make a propagating error happen, the system should have at least (α-1)L 2 errors. As L 2 (α-1)L 2 errors can already lead to a logical error, assuming the errors are independent, the probability of a propagating error is negligible compared to that of a logical error. Now we can move from these theorems to comparing different transversal gadgets by visualizing their decoder graph in time and space. The Shor gadget leads to a uniform three-dimensional lattice decoder graph where the vertices are syndrome bits as shown in Fig. 3(a). As proved above, we need the time dimension to be comparable to the space dimension. Steane-style syndrome extraction is capable of single-shot error correction [14]. In our method, this is clear from the lack of timelike edges in the decoder graph in Fig. 3(b). What intermediate schemes with block decoding generate are decoder graphs that only have timelike edges on the edges of the block.
We create the blocks by partitioning the L × L toric code into m × m blocks, where m divides L. We then use a small m × m surface-code ancilla block with 2m(m + 1) ancilla qubits. At the edges of the blocks, there are timelike boundaries as shown in Fig. 3(c).
In this picture, it is clear that we can reduce timelike edges by shifting the pattern of blocks. To simplify the shifting, we choose m = 3k for an integer k. At every time step, we shift the position of the blocks up and to the right by k as shown in Fig. 3(d). By construction, the error gadgets repeat every three steps, G t = G t+3 , and we can verify that d (t, t + 3) = (m). This enables us to achieve fault tolerance with |t i+1t i | = O(L/m).
We test our methods using numerical simulations as described in Ref. [40]. In Appendix B we include the raw data of the simulation used to determine the thresholds in [40]. We reproduce the details of the numerical method below for convenience. We also expand the simulations to consider the case with no ancilla-block error.
We study the circuit-level performance of our fault-tolerant error-correction schemes by Monte Carlo simulations. The X -and Z-syndrome extractions are applied alternatively. Our error model is parametrized by a single error parameter p and consists of three parts.
(i) Gate errors. With probability p, each two-qubit CNOT gate is followed by a Pauli error drawn uniformly at random from the set {I, X, Y, Z} ⊗2 \ {I ⊗ I}.
(ii) Measurement errors. With probability 2p/3, a measurement outcome in either the Z or X basis is flipped. (iii) Preparation errors. Ancilla preparation can lead to correlated errors that need to be removed through verification or syndrome measurement decoding. Here we assume a simple error model where the complicated ancilla blocks are generated perfectly and then each qubit undergoes an independent depolarizing channel with probability p 1 , which we set to either p or 0.
We further simplify by ignoring idling errors, which enables us to avoid complications due to scheduling. Comparison of these syndrome extraction methods for practical application would require a detailed multiparameter error model, a procedure for ancilla generation and verification, and the connectivity constraints of the quantum processor. To accelerate our simulation, instead of the standard MWPM decoding algorithm, we use a weighted variant of the union-find decoder [43,44]. For the surface code with bare ancilla, weighted union-find relative to MWPM decreases the threshold from 0.72% to 0.62% for a standard depolarizing error model with idling errors [44]. Tables I and II compare our block extraction schemes and Shor's and Steane's schemes for the two cases p 1 = p and p 1 = 0, respectively. In our noise model, the thresholds of transversal-gadget extraction is lower (upper) bounded by that of Shor's cat-state extraction (Steane's method). For block extraction, we fix the ancilla-block size m when L → ∞. In this case, we will still need O(L) rounds of extractions even if we offset the blocks. However, we observe that offsetting the blocks yields different threshold values than aligning them. This makes sense as the two strategies provide different decoder graph symmetries. When m gets larger, the offset version starts to yield higher threshold values. We also calculate the threshold of the conventional bare-ancilla extraction scheme [41] for a comparison.
An ideal fault-tolerant syndrome extraction circuit would have minimal interaction with the data, easy to prepare ancilla blocks, and require a small number of measurement rounds to make a decision. In this work, we have shown a family of extraction circuits that produces methods between Shor's [9] and Steane's [13] schemes. These circuits allow us to trade off the complexity of ancilla-block preparation for reduced interactions with the data. Furthermore, by shifting the choice of ancilla blocks in time, we can reduce the number of measurement rounds to achieve fault tolerance while maintaining constant ancilla-block complexity. Specifically for the toric code of distance L, we can use offset blocks of size O(m 2 ) to achieve fault tolerance in O(L/m) rounds, as presented in Ref. [40].
When ancilla postselections are allowed, we found that our error-correction schemes could yield higher thresholds for certain error models assuming negligible idling errors and independent ancilla errors. For a more realistic threshold estimation, we need to choose a specific ancilla preparation protocol. For the toric code example, the ancilla blocks inherit the toric code structure and one can use the bare-ancilla extraction circuit with postselections to prepare them [41]. There also exist protocols for preparing a general CSS stabilizer state by state distillations without leaving any correlated errors [39]. The detailed simulation of these preparation protocols is beyond the scope of this work and the utility strongly depends on the physical error model.
We have presented the toric code as an example because it is well studied and enables us to separate the advantages and disadvantages of our methods from advantages and disadvantages of new codes. The toric code allows for fault-tolerant syndrome extraction with bare ancilla on a nearest-neighbor two-dimensional lattice. Our methods are not a natural choice for the toric code, because the methods require the architecture to break out of two dimensions and also creates new challenges for generating ancilla blocks. On the other hand, we know that finite-rate quantum error-correction codes are not compatible with Euclidean two-dimensional architectures. We hope that our framework will enable the development of high-threshold fault-tolerant extraction circuits for these more qubit efficient codes.
There are a number of directions for further study. Codes that typically use Shor-style extraction, such as twodimensional color codes [30,45], can be decoded with ancilla blocks to improve the threshold. Concatenated codes that have high thresholds with postselected Knill or Steane schemes [15,46] also have high ancilla rejection rates and block methods can examine trading a reduced threshold for less ancilla verification. The non-fault-tolerant schemes developed here can be made fault tolerant using flag methods [17,18,30]. The time optimization and the choice of ancilla blocks can be analyzed using the framework recently applied to Shorstyle extraction [23,24]. Finally, these methods need to be tested in the face of more realistic errors as experimental systems approach the complexity capable of generating and utilizing large ancilla blocks. be used to detect Z (X ) errors on the ancilla block, which could propagate to the data block as weight-2 Z (X ) errors. We repeatedly execute the scheme B circuit until we observe a nontrivial outcome. As we have detected at least one error and we cannot correct any two errors for a distance-3 code, we can use the bare-ancilla circuit to extract the syndrome bits a Z , b Z , and c Z (a X , b X , and c X ), as shown in Fig. 4. We use Table III to decode the X errors based on the syndromes measured in the unflagged circuit when no flags were raised. However, if f 1,X ( f 1,Z ) is flagged and the syndrome a Z b Z c Z (a X b X c X ) is 001, the most probable error should be X 2 X 3 (Z 2 Z 3 ) instead of X 7 (Z 7 ). Similarly, if f 2,X ( f 2,Z ) is flagged, we need to change the correction for the syndrome 010 to X 3 X 4 (Z 3 Z 4 ). The flags tell us to expect correlations and decode appropriately.