Flag fault-tolerant error correction, measurement, and quantum computation for cyclic CSS codes
Theerapat Tansuwannont Christopher Chamberland Debbie Leung





ttansuwannont@uwaterloo.ca

    Institute for Quantum Computing and Department of Physics and Astronomy,
    University of Waterloo,
    Waterloo, Ontario, N2L 3G1, Canada
    

christopher.chamberland@ibm.com

   IBM T. J. Watson Research Center, Yorktown Heights, NY, 10598, United States
    

    Institute for Quantum Computing and Department of Physics and Astronomy,
    University of Waterloo,
    Waterloo, Ontario, N2L 3G1, Canada
    
    
    
wcleung@uwaterloo.ca

   Institute for Quantum Computing and Department of Combinatorics and Optimization,
    University of Waterloo,
    Waterloo, Ontario, N2L 3G1, Canada
    


Flag qubits have recently been proposed in syndrome extraction circuits to detect high-weight errors arising from fewer faults. The use of flag qubits allows the construction of fault-tolerant protocols with the fewest number of ancillas known to-date. In this work, we prove some critical properties of CSS codes constructed from classical cyclic codes that enable the construction of a flag fault-tolerant error correction scheme. We then develop fault-tolerant protocols as well as a family of circuits for flag fault-tolerant error correction and operator measurement, requiring only four ancilla qubits and applicable to cyclic CSS codes of distance 3. The measurement protocol can be further used for logical Clifford gate implementation via quantum gate teleportation. We also provide examples of cyclic CSS codes with large encoding rates.


03.67.Pp

Flag fault-tolerant error correction, measurement, and quantum computation 
 for cyclic CSS codes
    Debbie Leung
    
=================================================================================================





§ INTRODUCTION


Fault-tolerant quantum computation is an essential component in building a large scale quantum computer.  It enables arbitrarily low logical error rates, despite all operations (including those used to perform error correction) may be noisy, as long as the noise strength is below a constant but sufficiently small threshold value <cit.>. The value of the threshold depends on several factors, including the underlying quantum error correcting code, the design of the fault-tolerant gadgets and the error correction protocol, the speed of quantum measurements and classical processing of the error syndromes, and the underlying physical noise. Currently, the surface code appears to be a strong candidate for fault-tolerant quantum computation given its high threshold value as well as the geometric locality of the gates used in the syndrome extraction circuits <cit.>.

Meanwhile, low logical error rates requires large qubit and gate overheads <cit.>. Therefore, a fault-tolerant protocol that uses fewer ancilla qubits (and thus lower overheads) is easier to realize experimentally. A fault-tolerant protocol limits the number of physical errors in each code block arising from a single fault. Recently, Chao and Reichardt <cit.> showed that fault-tolerant error correction (FTEC) as well as fault-tolerant quantum computation can be achieved using only two extra ancilla qubits for perfect distance-3 codes. The idea is to use flag qubits to detect high-weight errors arising from a single fault. Furthermore, Reichardt showed that stabilizer measurements with flag qubits for the Steane code can be parallelized to reduce the circuit depths <cit.>. In <cit.>, FTEC protocol using very few flag qubits were developed for several families of stabilizer codes of arbitrary distance. For example, color codes with a hexagonal lattice and arbitrary distance require only four ancilla qubits in the FTEC scheme. The protocol in <cit.> can be used with LDPC (low density parity check) codes to achieve constant overhead <cit.>. Flag qubits were further used to fault-tolerantly prepare magic states with very low overhead compared to previous distillation schemes when Clifford gates are noisy <cit.>. Lastly in <cit.>, it was shown how flag qubits can be used to fault-tolerantly prepare GKP states.

The idea behind flag-FTEC <cit.> is that high-weight errors arising from a single fault have special structure. Despite their high weight, these errors can be alerted using few flag qubits and distinguished by subsequent syndrome measurements. However, there is no general theory what codes admit the flag technique. An interesting family of quantum codes consists of CSS codes constructed from classical cyclic codes. These codes have cyclic structures, each stabilizer generator is either X-type or Z-type, and some of these codes have high encoding rates. These properties make them a good choice for fault-tolerant quantum computation (see <ref>).

In this work, we generalize the flag technique to the family of cyclic CSS codes by exploiting the cyclic structure in the high-weight errors arising from a single fault. We build on the previous flag-FTEC schemes and obtain a new flag-FTEC scheme applicable to cyclic CSS codes of distance 3. In particular, we construct circuits for measuring the error syndromes using flag qubits which require only four ancilla qubits (see <ref>). The circuit uses a particular ordering of the CNOT gates which is independent of the underlying stabilizer code. Our work further expands the code families where flag-FTEC schemes can be used with very few ancilla qubits. Moreover, the number of required ancilla qubits is independent of the weights of the stabilizers being measured. Finally, we provide a flag fault-tolerant (flag-FT) operator measurement protocol for cyclic CSS codes, which can be further used for Clifford gate implementation and other applications.

The paper is organized as follows: In <ref> we review the basic properties of flag error correction and CSS codes. Key definitions which are used in several parts of the paper are introduced. We define the notion of distinguishable errors and consecutive error sets which are key components of our flag-FTEC scheme. We conclude the section by stating <ref>, an important building block for constructing our flag-FTEC scheme. In <ref> we review basic properties of classical cyclic codes, then state <ref>. Using the lemmas, we state and prove <ref> which is the final ingredient required to construct our flag-FTEC scheme for CSS codes constructed from classical cyclic codes. In <ref> we describe the syndrome extraction circuit used in our flag-FTEC protocol and proceed by describing the protocol in detail as well as explaining how it satisfies the fault-tolerance criteria. In <ref> we provide a flag-FT measurement protocol for Pauli operators, and its possible applications are discussed in <ref>. Examples of distance-3 cyclic CSS codes are given in <ref>. Lastly, we discuss our results and directions for future work in <ref>.



§ FLAG ERROR CORRECTION WITH CSS CODES



CSS codes form one of the most studied families of quantum codes since they have nice properties for fault-tolerant quantum computation. It has been shown recently that the technique of flag-FTEC can be applied to several families of codes <cit.>, but it remains open whether the techniques can also be applied to general CSS codes. In this section, we will analyze the idea behind flag techniques and provide the conditions which make CSS codes suitable for flag-FTEC in <ref>. This lemma will be a main ingredient for our theorem for cyclic CSS codes in the next section.

We first define CSS codes. They are constructed from classical binary linear codes <cit.> as follows: An [n,k,d] classical linear code C encodes k bits in n and has distance d (the minimum Hamming weight of the codewords). It corrects up to t = ⌊ (d-1)/2 ⌋ errors. The code is defined by the parity check matrix H which consists of n-k independent rows that are orthogonal to every codeword. The dual code C^⊥ of C consists of codewords that are orthogonal to all codewords in C. Note that C^⊥ is generated by H, that is, each codeword in C^⊥ is a linear combination of rows of H.  

A quantum n,k,d stabilizer code <cit.> encodes k logical qubits in n physical qubits. It is the simultaneous +1 eigenspace of n-k commuting, independent, Pauli operators. These Pauli operators multiplicatively generate a group called the stabilizer group for the code, and the Pauli operators are called the stabilizer generators. The code has distance d (see <cit.>) and it can correct errors acting on up to t = ⌊ (d-1)/2 ⌋ qubits. Let I,X,Y,Z denote the single-qubit Pauli operators. A Pauli operator P on n qubits, given by P=⊗_i=1^n X^x_i Z^z_i up to a phase, has a symplectic representation σ(P) which is the 2n-bit string σ(P)=(x_1, ⋯, x_n| z_1, ⋯, z_n). The symplectic representation of a stabilizer code is an (n-k) × 2n binary matrix where the i^th row is the symplectic representation of the i^th generator. The CSS codes first proposed in <cit.> can be defined in the stabilizer formalism as follows:

CSS code <cit.>
	
	An n,k,d stabilizer code is a CSS code if the generators can be chosen such that the code has symplectic representation
	
    [ A | 0; 0 | B ],

	
	where A is an r_x× n matrix and B is an r_z× n matrix for some r_x and r_z with r_x + r_z = n-k. A and B are called X and Z stabilizer matrices.

In other words, a CSS code is a stabilizer code whose generators can be chosen to be either tensor products of I and X or of I and Z. The generators of X-type and Z-type are called X and Z stabilizers, respectively. With this choice of generators, the X errors and Z errors can be detected separately.

CSS code construction <cit.>
	
	Let C_x be an [n,k_x,d_x] classical linear code with parity check matrix H_x and C_z be an [n,k_z,d_z] classical linear code with parity check matrix H_z. Suppose that H_x^T H_z = 0, or equivalently, C_x^⊥⊆ C_z. Then, the following binary matrix
	
    [ H_x   |   0;   0   | H_z ],

	
	is the symplectic representation of an n,k,d stabilizer code C with k=k_x + k_z - n and d≥min{d_x,d_z}. 


In an EC protocol, the syndrome measurement corresponds to the measurement of all stabilizer generators. Consider an n,k,d CSS code which can correct errors of maximum weight t =⌊ (d-1)/2 ⌋. Each generator is either X-type or Z-type stabilizer, and it acts non-trivially on m qubits where m ∈{1,⋯,n}. We can assume that, up to qubit permutations, the stabilizer being measured is of the form I^⊗ n-m⊗ X^⊗ m or I^⊗ n-m⊗ Z^⊗ m. The ideal circuits for measuring weight-m X stabilizers and weight-m Z stabilizers are shown in <ref>. 



However, the EC protocol involving the aforementioned circuit has a drawback. Suppose the circuit is not perfect, and each location (a state preparation step, a gate, or a measurement) can have a fault. Suppose that v ≤ t faults happen. In some cases, these v faults can result in an error of weight greater than t in the output state of the circuit, which may not be correctable anymore. This circuit spreads errors and is not generally suitable for building EC protocols with an important property called fault tolerance <cit.>, defined as follows:

Fault-tolerant error correction <cit.>
	
	For t = ⌊ (d-1)/2⌋, an error correction protocol using a distance-d stabilizer code C is t-fault-tolerant if the following two conditions are satisfied:
	
		
  * For an input codeword with error of weight v_1, if v_2 faults occur during the protocol with v_1 + v_2≤ t, ideally decoding the output state gives the same codeword as ideally decoding the input state.
		
  * For v faults during the protocol with v ≤ t, no matter how many errors are present in the input state, the output state differs from a codeword by an error of at most weight v.
	
	


An error on the input state might have weight > t, which means that it is incorrectable. Anyhow, if the number of faults is v≤ t, the second condition in <ref> requires that the state after correction must differ from any valid codeword by an error of weight ≤ v. (One possible way to construct a FTEC protocol satisfying both conditions in <ref> is using the minimal weight correction, defined later in <ref>.)

Ideally decoding is equivalent to performing fault-free error correction. The conditions above are simultaneously required in order to ensure that low-weight errors do not spread and become incorrectable as well as to prevent errors from accumulating between different error correction rounds. 

Generally, FTEC protocols may require a lot of ancilla qubits to avoid the spread of errors within a code block. Chao and Reichardt introduced the idea of flag qubits in <cit.> to reduce the number of ancilla qubits being used in FTEC. They also provided some circuit constructions to fault-tolerantly extract syndromes for various distance-3 perfect stabilizer codes using only two ancilla qubits. To see how the flag-FTEC works, let us examine the circuit shown in <ref> which is modified from the circuit in <ref>.


A flag qubit is introduced in <ref> to detect a fault that can lead to data error of weight >1. If any pair of higher-weight errors detected by the flag qubit are either equivalent (up to multiplication of some stabilizer) or have different syndromes, it is possible to construct a flag-FTEC protocol which corrects higher weight errors (that arise from a single fault) using information from the flag qubit and subsequent syndrome measurements.

The idea of flag-FTEC is further developed in <cit.>, and the general conditions for flag-FTEC applicable to stabilizer codes of arbitrary distance are provided. In particular, the flag-FTEC condition for a stabilizer code which can correct up to one error is as follows:
Flag-1 FTEC condition <cit.>
	
	Consider a stabilizer code generated by {g_1,…,g_n-k} which can correct up to one error. Let ℰ(g_i) be the set of all possible errors arising from any single fault that can cause a circuit for measuring g_i to flag. For every generator g_i, all pairs of errors in ℰ(g_i) must either have different syndromes or be equivalent up to multiplication of some stabilizer.
	

Showing that a code along with appropriate syndrome extraction circuits satisfy the general conditions for flag-FTEC can be quite challenging. Reference <cit.> provides a sufficient condition which implies the general flag-FTEC conditions, and a FTEC protocol using flag qubits and applicable to stabilizer codes of arbitrary distance satisfying such condition was developed. This sufficient condition can be much easier to verify, and several code families were shown to satisfy the general flag-FTEC conditions. However, not all CSS codes satisfy this sufficient condition.

As was shown in <cit.>, for codes which do not satisfy the sufficient condition in <cit.>, errors are spread in the measurement circuits in a way that depends on which stabilizer generators are measured, and also on the ordering of the CNOT gates used in the measurement circuits for these generators. Therefore, these specific designs in the protocol may affect the fulfillment of the flag-FTEC conditions. With an appropriate permutation of the CNOT gates of the syndrome extraction circuits, Chao and Reichardt proved that the family of 2^r-1,2^r-1-2r,3 quantum Hamming codes satisfied the flag-1 FTEC condition. In this work, we prove some properties of cyclic CSS codes and show that it is possible to construct syndrome extraction circuits which satisfy the flag-1 FTEC condition in <ref> for cyclic CSS codes of distance 3.

Reference <cit.> develops the notation of t-flag circuits and shows that any flag-FTEC protocol will require the use of them. We generalize their definition as follows:

t-flag circuit
	
	Let C be an n,k,d stabilizer code with generators g_1,g_2…,g_n-k, P be a weight-m Pauli operator which commutes with all g_i's, and C(P) be a circuit that implements a projective measurement of P in the absence of faults. We say that C(P) is a t-flag circuit if all of the following holds:
	
		
  * the circuit does not flag without faults, and 
		
  * the circuit flags whenever a set of v ≤ t faults in C(P) leads to an error E on the output with min_Q(wt(E Q)) > v where the minimization is over Q ∈⟨ P, g_1, ⋯, g_n-k⟩, the group generated multiplicatively by P and the stabilizer generators g_i's.
	
	


In this paper, we will use certain properties of cyclic CSS codes to develop a flag-FTEC protocol.  In particular, a single fault in the syndrome extraction circuits of CSS codes produces errors with special properties which allow us to distinguish consecutive errors. To proceed with the analysis, we introduce some useful definitions and lemmas. We start by the definition of distinguishable errors as follows:

Distinguishable errors
	
	Let C be an n,k,d stabilizer code and let E_1 and E_2 be n-qubit Pauli errors with syndromes s(E_1) and s(E_2). We say that E_1 and E_2 are distinguishable by C if s(E_1) ≠ s(E_2). Otherwise we say that they are indistinguishable. In addition, if any pair of errors from an error set ℰ are distinguishable by C, we says that ℰ is distinguishable by C.
	


The circuit in <ref> is a 1-flag circuit since it will flag (the flag-qubit measurement outcome is -1) if there is a single fault causing data error of weight >1. From the flag-FTEC condition in <ref>, our goal is to distinguish all possible higher-weight errors by subsequent stabilizer measurements. Note that the set of higher-weight errors depends on the choice of generators and the permutation of CNOT gates, and only some choices and permutations will lead to a distinguishable error set. Some CSS codes that satisfy the sufficient condition in <cit.> can be used in a flag-FTEC protocol[Note that for such codes, the order of the CNOT gates in a t-flag circuit is not important.]. However, whether flag-FTEC techniques can be applied to general CSS codes is still unknown. 

Observe that permuting the CNOT gates in the measurement circuit is equivalent to permuting columns of the stabilizer matrices. In order to find CSS code families such that flag-FTEC techniques can be used, we will consider fixing the CNOT gates of syndrome extraction circuits in the normal permutation, (i.e., applying CNOT gates from top to bottom as in <ref>)[Note that for some specific codes, it is certainly possible to find circuits with fewer ancilla qubits by choosing an appropriate permutation of the CNOT gates.]. Subsequently, we will find conditions that need to be satisfied by the X and Z stabilizer matrices.

Assume that a faulty CNOT gate can cause a 2-qubit error of the form P_1⊗ P_2 where P_1,P_2 ∈{ I,X,Y,Z } are Pauli errors on the control and the target qubits, respectively. Consider a circuit for measuring stabilizers of the form I^⊗ n-m⊗ Z^⊗ m with the normal permutation of CNOT gates as in <ref> where m∈{1,⋯,n}. A single fault at a CNOT location can result in the following types of errors:

	
  * If an error from a faulty CNOT gate is of the form P_1 ⊗ P_2 where P_1∈{I,X,Y,Z } and P_2 ∈{ I,X }, then the data error is of weight ≤ 1 and the flag outcome is +1. 
	
  * If an error from a faulty CNOT gate is P_1 ⊗ P_2 where P_1=I and P_2 ∈{ Y,Z }, the data error is of the form I^⊗ n-m+c⊗ Z^⊗ m-c where c∈{1,⋯,m}. In the cases where the data error has weight >1, the flag outcome is -1.
	
	
  * If an error from a faulty CNOT is P_1 ⊗ P_2 where P_1 ∈{ X,Y,Z } and P_2 ∈{ Y,Z }, the data error is of the form I^⊗ n-m+c-1⊗ P_1 ⊗ Z^⊗ m-c where c∈{1,⋯,m}. In the cases where the data error has weight >1, the flag outcome is -1.
	
 
Data errors of the form <ref> or <ref> arise due to the propagation of Z errors from the target to control qubit of CNOT gates. In addition, if a faulty CNOT gate causes the error Z⊗ Z, this can be viewed as an error I⊗ Z caused by the preceding CNOT gate. Let ℰ_+ and ℰ_- be sets of errors corresponding to the flag outcome +1 and -1, respectively. Consider an n,k,d CSS code C constructed from two classical codes C_x and C_z as in <ref>. It is obvious that ℰ_+ is distinguishable by C if d≥ 3. The distinguishability of errors of the form <ref> in ℰ_- depend on the classical code C_x. Also, any error of the form <ref> in ℰ_- can be considered as a product of an error of the form <ref> and a weight-1 X-type error. Therefore, if the distance of C_z is d_z≥ 3 and the code C_x can distinguish all errors in the the form <ref>, then ℰ_- is distinguishable by C. The same argument can also be applied to circuits for measuring X stabilizers. 

We can see that the ability of the code to distinguish errors of the form <ref> is crucial in a flag-FTEC protocol. In order to develop a flag-FTEC protocol for cyclic CSS codes, the following definitions will be very useful:

Left cyclic-shift
	
	Let P = P_1⊗⋯⊗ P_n be an n-qubit Pauli operator and l ∈{0,1,…,n-1}. The l-qubit left cyclic-shift of the operator P, denoted by ℒ(P,l), is defined as
	
    ℒ(P, 0)    = P, 
    ℒ(P, l)    = P_l+1⊗⋯⊗ P_n ⊗ P_1 ⊗⋯⊗ P_l   for   l≠ 0.

	


Consecutive error set
	
	Let n be the number of qubits and l ∈{0,1,…,n-1}. A consecutive-X error set ℰ^x_l,n and a consecutive-Z error set ℰ^z_l,n are sets of the form
	
    ℰ^x_l,n   =  {ℒ(I^⊗ n-p⊗ X^⊗ p,l): p ∈{0,1,…,n-1}}, 
    ℰ^z_l,n   =  {ℒ(I^⊗ n-p⊗ Z^⊗ p,l): p ∈{0,1,…,n-1}}.

	A consecutive error product set ℰ^P_l,n is defined as
	
    ℰ^P_l,n   =  {E_x · E_z: E_x ∈ℰ^x_l,n, E_z ∈ℰ^z_l,n}.

	


In order to distinguish all errors in each consecutive error set, the X and Z stabilizer matrices must satisfy the conditions in the following lemma:


	
	Let C be a CSS code constructed from the classical cyclic codes C_x and C_z following <ref> with parity check matrices H_x and H_z of the form
	
    H_x =[   x_1,1   x_1,2       …   x_1,n;   x_2,1   x_2,2       …   x_2,n;       …                       …; x_r_x,1 x_r_x,2       … x_r_x,n;         ],

	
    H_z =[   z_1,1   z_1,2       …   z_1,n;   z_2,1   z_2,2       …   z_2,n;       …                       …; z_r_z,1 z_r_z,2       … z_r_z,n;         ],

	and let ℰ^x_0,n, ℰ^z_0,n, and ℰ^P_0,n be consecutive-X error set, consecutive-Z error set, and consecutive error product set, respectively. Then, 
	
		
  * ℰ^z_0,n is distinguishable by C iff for all p,q∈{0,...,n-1} such that p>q, there exists i∈{1,…,r_x} such that x_i,n-p+1⊕…⊕ x_i,n-q=1.
		
  * ℰ^x_0,n is distinguishable by C iff for all p,q∈{0,...,n-1} such that p>q, there exists i∈{1,…,r_z} such that
		z_i,n-p+1⊕…⊕ z_i,n-q=1.
		
  * ℰ^P_0,n is distinguishable by C iff both ℰ^z_0,n and ℰ^x_0,n are distinguishable by C.
	
	


A proof of <ref> is given in <ref>.

Note that consecutive error sets in <ref> are defined on n qubits. In particular, consecutive error sets defined on m qubits are distinguishable iff the submatrices of H_x and H_z corresponding to measurements on m qubits satisfy similar conditions. In the next section, we will show that the cyclic symmetry of cyclic CSS codes can simplify the conditions in <ref>.



§ CYCLIC CSS CODES AND ERROR DISTINGUISHABILITY


In <ref>, the conditions for distinguishing errors in the consecutive error sets are given in <ref>. Notice that there are some sufficient conditions for distinguishability in  Statements 1 and 2 that are similar, different only by some qubit shift. It is possible to simplify <ref> if the CSS code has cyclic symmetry. In this section, we begin by stating the definition of classical cyclic codes and outlining some of their properties. Afterwards, <ref> will be given, and <ref> which is the main theorem in this work will be proved.

Classical cyclic code <cit.>

Let C be a classical binary linear code of length n. C is cyclic if any cyclic shift of a codeword is also a codeword, i.e., if (c_1,c_2,…,c_n) is in a codeword, then so is  (c_n,c_1,…,c_n-1). 



Let C be a classical cyclic code of length n. There exists a unique generator polynomial g(x)=∑_i=0^α g_ix^i which is also a unique monic polynomial of minimal degree in C such that C is generated by the generator matrix

    [   g_0   g_1   g_2     …   g_α     0     …     0;     0   g_0   g_1     … g_α-1   g_α     …     0;     …                                         …;     0     …   g_0     …                 …   g_α ].

The polynomial h(x) = (x^n-1)/g(x) = ∑_i=0^β h_ix^i is called the check polynomial of C. The parity check matrix of C is

    [   h_β h_β-1     …   h_1   h_0     0     …     0;     0   h_β     …   h_2   h_1   h_0     …     0;     …                                         …;     0     …   h_β     …                 …   h_0 ].


It is known that any classical Hamming code can be made cyclic <cit.>. Thus, a cyclic CSS code can be constructed from permuting columns of a quantum Hamming code's stabilizer matrices. In <cit.>, it was shown how to construct a cyclic CSS code from two classical cyclic codes.

By the symmetries of a cyclic code, we can show in the following lemma that the left cyclic-shift of operators in the generating set also generates the same code.


	
	Let C be a CSS code constructed from the classical cyclic codes C_x and C_z following <ref>. Suppose that the stabilizer group of C can be generated by {g_1,g_2,…,g_n-k}, then the stabilizer group of C can also be generated by {ℒ(g_1,l),ℒ(g_2,l),…,ℒ(g_n-k,l)} for any l ∈{0,1,…,n-1}.
	
	

The proof of <ref> is given in <ref>. 

In the previous section, <ref> gives sufficient and necessary conditions for a CSS code to be able to distinguish all errors in the consecutive error sets. The conditions can be simplified by using the symmetry of cyclic codes as follows:


	
	Let C be a CSS code constructed from the classical cyclic codes C_x and C_z (following <ref>) with parity check matrices H_x and H_z,
	
    H_x    =[   x_1,1   x_1,2       …   x_1,n;   x_2,1   x_2,2       …   x_2,n;       …                       …; x_r_x,1 x_r_x,2       … x_r_x,n;         ],
    
    	H_z    =[   z_1,1   z_1,2       …   z_1,n;   z_2,1   z_2,2       …   z_2,n;       …                       …; z_r_z,1 z_r_z,2       … z_r_z,n;         ].

	Let l ∈{0,1,…,n-1}, and let ℰ^x_l,n, ℰ^z_l,n, and ℰ^P_l,n be consecutive-X error set, consecutive-Z error set, and consecutive error product set, respectively. Then, 
	
		
  * ℰ^z_l,n is distinguishable by C iff for all u_x∈{2,…,n}, there exists i∈{1,…,r_x} such that x_i,u_x⊕…⊕ x_i,n=1.
		
  * ℰ^x_l,n is distinguishable by C iff for all u_z∈{2,…,n}, there exists i∈{1,…,r_z} such that z_i,u_z⊕…⊕ z_i,n=1.
		
  * ℰ^P_l,n is distinguishable by C iff both ℰ^z_l,n and ℰ^x_l,n are distinguishable by C.
	
	


The cyclic symmetry of C_x and C_z can simplify <ref>, resulting in fewer sufficient conditions for distinguishability in Statements 1 and 2; we can fix q in <ref> to be 0 and choose u = n-p+1. This reduces the number of error pairs in consecutive error sets to be distinguished. Moreover, all statements in <ref> can also be applied to consecutive error sets of any l ∈{0,1,…,n-1}. A proof of <ref> is given in <ref>.

Now we are ready to prove a main theorem in this work.


	
	Let C be an n,k,d CSS code constructed from the [n,k_x,d_x] classical cyclic code C_x and the [n,k_z,d_z] classical cyclic code C_z, l ∈{0,1,…,n-1}, and ℰ^P_l,n be a consecutive error product set. If both d_x, d_z ≥ 3, then ℰ^P_l,n is distinguishable by C.
	

	

	 
	
	
	Suppose by contradiction that ℰ_l,n^P is not distinguishable by C. Then, at least one of ℰ_l,n^z and ℰ_l,n^x is not distinguishable by C. Similar analysis applies to either case, so, suppose ℰ_l,n^z is not distinguishable by C. We next invoke <ref>, and to do so, let the cyclic code C_x has parity check matrix 
	
    H_x =[   x_1,1   x_1,2       …   x_1,n;   x_2,1   x_2,2       …   x_2,n;       …                       …; x_r_x,1 x_r_x,2       … x_r_x,n;         ],

	where x_i_1+1,(j+1) n=x_i_1,j for all i_1∈{1,…,r_x-1} and j∈{1,…,n}. 
	
	
	
	By Statement 1 of <ref>, we know that ℰ_l,n^z is indistinguishable by C iff there exists u_x ∈{2,3,...,n} such that x_i,u_x⊕…⊕ x_i,n=0 for all 
	i ∈{1, ⋯, r_x }; i.e., there exists a pair of errors in ℰ_l,n^z which cannot be distinguished by any generator of C.
	
	
	
	For i=1, we have 
	
    x_1,u_x⊕…⊕ x_1,n   =0  .

	
	Using <ref>, we obtain a new generating set for C where each generator is the 1-qubit left cyclic-shift of the old one.  
	Applying the above to the new generator set, we have
	
    x_1,u_x+1⊕…⊕ x_1,n⊕ x_1,1=0.

	
	Now repeating the left cyclic shifts gives 
	
	
    x_1,u_x+2⊕…⊕ x_1,n⊕ x_1,1⊕ x_1,2   =0, 
       ⋮
    
    	x_1,u_x-1⊕ x_1,1⊕…⊕ x_1,n-1   =0  .

	
	From <ref>, x_1,1=x_1,u_x; from <ref>, x_1,2=x_1,u_x+1, and so on, until we obtain x_1,n=x_1,u_x+(n-1)  n (in other words, x_1,j=x_1,(u_x-1+j) n for all j∈{1,…,n}).  
	
	Let w_x = GCD(u_x-1,n), the greatest common divisor of u_x-1 and n. The conditions become
	
    x_1,j=x_1,j+w_x=x_1,j+2w_x=...=x_1,j+n-w_x,

	for all j ∈{1,…,w_x}. Repeating the above steps for all i, we obtain
	
    x_i,j=x_i,j+w_x=x_i,j+2w_x=...=x_i,j+n-w_x,

	for all i ∈{1,…,r_x}, j∈{1,…,w_x}.
	
	From the above, we see that any error of the form Z_l_xZ_l_x+w_x (where l_x ∈{ 1, ⋯, n-w_x }) commutes with all stabilizer generators. Now let us consider two cases:
	
		
  * Case 1: At least one operator of the form  Z_l_xZ_l_x+w_x is not in the stabilizer.
		
		In this case, the distance d of the code C is at most two. Since d ≥min{d_x,d_z} (see <ref>), this contradicts our assumption that both d_x,d_z ≥ 3.
		
  * Case 2: All operators of the form Z_l_xZ_l_x+w_x are in the stabilizer.
		
		In this case,  there exists a set of coefficients a_1, ⋯, a_r_z∈{0,1 } such that (g^z_1)^a_1⋯ (g^z_r_z)^a_r_z = Z_l_xZ_l_x+w_x, where g^z_i is the Z-type generator corresponding to the ith row of H_z. This means that the Z-part of σ(Z_l_xZ_l_x+w_x) is a codeword in C_z^⊥. Since C_z^⊥⊆ C_x by the construction of CSS codes, we have that the Z-part of σ(Z_l_xZ_l_x+w_x) is a codeword in C_x. Because the distance of classical codes is given by the minimum Hamming weight of the codewords, we have that d_x≤ 2 which contradicts our assumption that d_x≥ 3.
	
	
	
	


Although consecutive error product set ℰ_l,n^P is distinguishable by any cyclic CSS code satisfying <ref>, we cannot  construct an FTEC protocol using the circuit in <ref> directly since the possible errors might not be in the consecutive form without qubit permutation. Moreover, permuting qubits will break the cyclic symmetry and ℰ_l,n^P might no longer be distinguishable. In the next section, we will use <ref> to find a 1-flag circuit for distance-3 cyclic CSS codes that can be used in a fault-tolerant protocol satisfying <ref>. We point out that since p,q in <ref> are chosen to be in the set { 0, ⋯, n-1 }, if a cyclic CSS code 
can correct errors of weight ≤ t, then the flag circuits should be designed such that if there are ≤ t faults during the FTEC protocol, an error of weight n cannot occur.



§ FAULT-TOLERANT ERROR CORRECTION PROTOCOL FOR DISTANCE-3 CYCLIC CSS CODES




Fault-tolerant error correction is one of the most important building blocks for fault-tolerant quantum computation. In this section, a flag-FTEC protocol for distance-3 cyclic CSS codes is developed [Note that our protocol and circuit can also be applied to higher distance codes if we only consider correcting errors introduced by at most one fault.]. A 1-flag circuit for cyclic CSS codes of distance 3 which is required for the flag-FTEC protocol is provided in <ref> (see <ref> for the definition of a t-flag circuit). Here we adapt the idea of localizing circuit faults from <cit.>.

Suppose that the stabilizer generator being measured is of the form 

    P = Z^⊗ a_1⊗ I^⊗ b_1⊗ Z^⊗ a_2⊗ I^⊗ b_2⊗⋯⊗ Z^⊗ a_m⊗ I^⊗ b_m,
 
where a_i>0 and b_i ≥ 0 are integers. The i^th sub-block consists of a_i qubits, which are from the ∑_j=1^i-1(a_j+b_j)+1'th qubit to the ∑_j=1^i-1(a_j+b_j)+a_i'th qubit.

Notice that the blue, green and orange CNOT gates in the circuit of <ref> always come in pairs. This is to ensure that when fault-free, the circuit implements a projective measurement of the stabilizer without flagging. In what follows, we will refer to the first blue, green or orange CNOT of a pair as an opening CNOT and the second blue, green or orange CNOT as a closing CNOT. Given these definitions, we have the following claim:


During the measurement of P = Z^⊗ a_1⊗ I^⊗ b_1⊗ Z^⊗ a_2⊗ I^⊗ b_2⊗⋯⊗ Z^⊗ a_m⊗ I^⊗ b_m using the circuit in <ref>, the following can occur:

    
     
  * If there are no faults, none of the f_i ancilla qubits will flag. 
     
  * A fault at a CNOT location resulting in a ZZ error is equivalent to the prior CNOT failing resulting in an IZ error (here Z acts on the target qubit).
     
  * Suppose that a fault occurs on one of the red CNOT's and causes a Z error on the ancilla m_0. If the fault occurs on sub-block a_i where i≥ 1, only the ancillas f_0 and f_i will flag.
     
  * Suppose that a fault occurs on a blue or green CNOT. Let the control qubit be the ancilla f_i. If it is the opening CNOT and causes a Z error on ancilla m_0, the ancillas f_0, f_i, and f_i-1 will flag. If it is the closing CNOT and causes a Z error on the ancilla m_0, the ancillas f_0 and f_i+1 will flag. However if the fault occurs on a blue or green CNOT's at the boundary [By boundary we are referring to either the first blue CNOT after the 1^th sub-block or the last green CNOT after the m^th sub-block.], if the opening CNOT of f_1 is faulty, f_0 and f_1 will flag, and if the closing CNOT of f_m is faulty, only f_0 will flag.
     
  * A fault occurring at an orange CNOT gate will not cause a data qubit error (since a Z spreading to all qubits is equivalent to the stabilizer being measured). Furthermore, only the ancilla f_0 can flag in this case (depending on whether the error was of the form IZ or ZZ and also whether it occurred on the opening or closing orange CNOT).    




From the above claim, one can verify that a single fault resulting in a data qubit error E with min_Q(wt(E Q)) > 1 where Q ∈⟨ P, g_1, ⋯, g_n-k⟩ will always cause at least one flag qubit to flag (see <ref>). Thus the circuit in <ref> is a 1-flag circuit. Note that an analogous claim can be made for X-type stabilizers.

Before describing the FTEC protocol, we require one more definition:
Minimum weight correction

Given the syndrome s=s(E) of an error E, we let E_min(s) be a minimal weight correction of E. 



Note that many errors can lead to the same syndrome. In particular, errors corresponding to the same syndrome differ by some multiplication of stabilizers or logical operators. If error E is correctable, applying E_min(s) can correct such error as we expected. However, if E is not correctable (i.e., wt(E) > t), applying E_min(s) will project the codeword back to the coding subspace, but the resulting codeword may differ from the original codeword by some logical operation. This property of minimal weight correction is required so that the FTEC protocol satisfy the second FTEC condition in <ref>.

Using <ref>, we now describe a FTEC protocol that satisfies <ref> for distance-3 cyclic CSS codes using a procedure adapted from <cit.>. In what follows, we define s^(r) = (s^(r)_x|s^(r)_z) to be the syndrome obtained during round r (either using flag or non-flag circuits), where s^(r)_x and s^(r)_z are the syndromes obtained from X-type and Z-type stabilizers, respectively.

FTEC Protocol: 

Let C be an n,k,d cyclic CSS code satisfying <ref> with stabilizer group S = ⟨ g_1 , ⋯ , g_n-k⟩. Let C(g_i) be the 1-flag circuit of <ref> for stabilizer g_i. Repeat the syndrome measurement (measurement of all stabilizer generators) using the 1-flag circuits until one of the following is satisfied:

        
  * If the syndrome is repeated twice in a row and there are no flags, apply E_min(s^(1)).
	
  * If there are no flags and the syndromes s^(1) and s^(2) differ, repeat the syndrome measurement using non-flagged circuits. Apply the correction E_min(s^(3)).
        
  * If f_0 does not flag but f_i flags (with i ≥ 1) during round one, stop. Repeat the syndrome measurement using non-flag circuits and apply E_min(s^(2)). If there are no flags in the first round but in round two f_i flags and f_0 does not flag, stop. Apply  E_min(s^(1)).	
	
  * If f_0 flags at round r anytime during the protocol, stop and do one of the following:
	
		
  * If f_i does not flag for all i≥1, repeat the syndrome measurement using non-flag circuits. Apply E_min(s^(r+1)).
		
  * If there is only one i such that f_i flags (with i ≥ 1), apply I^⊗ c⊗ Z^⊗ a_i+1⊗ I^⊗ b_i+1⊗⋯⊗ Z^⊗ a_m⊗ I^⊗ b_m to the data if the stabilizer being measured is a Z stabilizer or I^⊗ c⊗ X^⊗ a_i+1⊗ I^⊗ b_i+1⊗⋯⊗ X^⊗ a_m⊗ I^⊗ b_m if it is an X stabilizer, where c=∑_j=1^i (a_j+b_j). Repeat the syndrome measurement using non-flag circuits yielding syndrome s^(r+1) = (s^(r+1)_x|s^(r+1)_z). 
		
			
  * If the stabilizer being measured is a Z stabilizer and there is an element E_z in ℰ^z_l,n where l=n-c+b_i that satisfies s(E_z)=s^(r+1)_x, apply E_z followed by E_min(s^(r+1)_z). Otherwise, apply  E_min(s^(r+1)).
			
  * If the stabilizer being measured is an X stabilizer and there is an element E_x in ℰ^x_l,n where l=n-c+b_i that satisfies s(E_x)=s^(r+1)_z, apply E_x followed by E_min(s^(r+1)_x). Otherwise, apply  E_min(s^(r+1)).
		
		
  * If there is an i such that f_i and f_i+1 flag, perform the same sequence operations as in 4(b).
		


To see that the above protocol satisfies <ref>, we will assume that there is at most one fault during the protocol. If a fault in any of the CNOT gates introduces a Z error on ancilla m_0, then f_0 and at least one f_i (with i ≥ 1) will flag (unless the first orange CNOT introduces an error of the form ZZ or the last orange CNOT introduces an error of the form IZ which in both cases, there will be no data qubit error). If there is only one flag during round one, either f_0 or f_i, then the fault could either have been caused by a measurement error, idle qubit error on the ancilla f_0 or f_i, or an error on the control qubit of the CNOT gate interacting with f_0 or f_i. However in all three cases, the error could not have spread to the data. By repeating the syndrome measurement and applying E_min(s^(2)), both criteria of <ref> will be satisfied. Note that if f_i flags during round two, then the syndrome obtained during round one corresponds to the data qubit error (since there could not have been a measurement error giving the wrong syndrome during the first round), so correcting using s^(1) will again satisfy <ref>.

Next, let us consider the case where none of the f_i ancillas flag. By the circuit construction, a single fault can introduce an error E with wt(E) ≤ 1. If the same syndrome is repeated twice in a row, then applying E_min(s^(1)) can result in a data error of weight at most one. If s^(1)≠ s^(2), then a fault occurred in either the first or second round. Thus repeating the syndrome measurement a third time and applying E_min(s^(3)) will remove the data errors or project the code back to the coding subspace. 

Next we consider the case where a fault happens on a red CNOT introducing a Z error on the ancilla m_0 and a P error on the data qubit where P ∈{I,X,Y,Z}. If the fault occurs on the i^th sub-block, then f_0 will flag and there will be only one i ≥ 1 such that f_i flags. Applying I^⊗ c⊗ Z^⊗ a_i+1⊗ I^⊗ b_i+1⊗⋯⊗ Z^⊗ a_m⊗ I^⊗ b_m where c=∑_j=1^i (a_j+b_j) to the data if the stabilizer being measured is a Z stabilizer (or I^⊗ c⊗ X^⊗ a_i+1⊗ I^⊗ b_i+1⊗⋯⊗ X^⊗ a_m⊗ I^⊗ b_m if it is an X stabilizer) guarantees that the resulting error is a product of Z-type error from ℰ^z_l,n and an X-type error of weight at most 1 (or a product of X-type error from ℰ^x_l,n and a Z-type error of weight at most 1). By <ref>, errors in the set ℰ^z_l,n (or  ℰ^x_l,n) can be distinguished. Thus applying the correction in 4(b) of the protocol will remove the error if there are no input errors. However, if there is an input error, then applying E_min(s^(r+1)) will project the code back to the coding subspace.

Lastly, if a fault occurs on a blue or green CNOT, then from <ref> either the case in 4(b) or 4(c) will be satisfied. However in both cases, the Z error will spread to the data in the same way. Hence the correction proposed in 4(c) will satisfy the fault-tolerance criteria of <ref>.

A list of possible faults during the flag-FTEC protocol and corresponding correction procedures is given in <ref> in <ref>.



§ FAULT-TOLERANT MEASUREMENT PROTOCOL FOR DISTANCE-3 CYCLIC CSS CODES
 

Besides FTEC, there are other important components for fault-tolerant computation: FT state preparation, FT measurement, and FT quantum gate implementation. In this section, we provide a flag-FT measurement protocol for distance-3 cyclic CSS codes. The measurement protocol plays an important role in fault-tolerant quantum computation on cyclic CSS codes since it can also be used as a subroutine for FT state preparation, FT quantum gate implementation, and other techniques, described later in <ref>.

The flag-FT protocol provided in this section is similar to the flag-FTEC protocol in <ref> except that the idea of consecutive error correction is developed so that it is applicable not only to stabilizer measurements but also to measurements of any Pauli operator commuting with all generators. We begin by introducing the definition of fault-tolerant non-destructive measurement adapted from <cit.> as follows:

Fault-tolerant non-destructive measure- ment
	
	For t = ⌊ (d-1)/2⌋, a non-destructive measurement protocol using a distance-d stabilizer code C is t-fault-tolerant if the following two conditions are satisfied:
	
		
  * For an input codeword with error of weight v_1, if v_2 faults occur during the measurement protocol with v_1 + v_2≤ t, ideally decoding the output state after measurement gives the same state as ideally decoding the input state and then performing ideal non-destructive measurement. The result obtained from measuring the input codeword is the same as that of an ideal measurement on the ideally-decoded input state.
		
  * For an input codeword with error of weight v_1, if v_2 faults occur during the measurement protocol with v_1 + v_2≤ t, the output state differs from a codeword by an error of at most weight v_1+v_2.
	
	


(Here we need to modify <ref> from the usual definition of fault-tolerant (destructive) measurement since we would like to obtain both measurement result and post-measurement state. These ingredients are important in the applications discussed in <ref>.)

Suppose that the operator being measured P commutes with all generators and is of the form

    P = P_1^⊗ a_1⊗ I^⊗ b_1⊗ P_2^⊗ a_2⊗ I^⊗ b_2⊗⋯⊗ P_m^⊗ a_m⊗ I^⊗ b_m,

where a_i>0 and b_i ≥ 0 are integers and P_i ∈{X,Y,Z}. The i^th sub-block consists of a_i qubits acted on by P_i^⊗ a_i. A 1-flag circuit for operator measurement is similar to the circuit given in <ref>, while the measurements of Z, X, and Y operators correspond to CNOT gates, the gates shown in <ref>, and the gates shown in <ref>. With the slight modification where CNOT gates are replaced by the gates for measuring P_i ∈{X,Y,Z}, one can verify that <ref> is also applicable in this setting.



Using <ref> and <ref>, we now describe a flag-FT measurement protocol that satisfies <ref> for distance-3 cyclic CSS codes. Here we define m^(r_1) to be the measurement result obtained from operator measurement (using either flag or non-flag circuits) during round r_1, and define s^(r_2)=(s^(r_2)_x|s^(r_2)_z) to be the syndrome obtained from syndrome measurement (using either flag or non-flag circuits) during round r_2 of error correction. The protocol is as follows:

Flag-FT Operator Measurement Protocol:

Let C be an n,k,d cyclic CSS code satisfying <ref>. Let C(P) be the 1-flag circuit of <ref> for measuring a Pauli operator P of the form

    P = P_1^⊗ a_1⊗ I^⊗ b_1⊗ P_2^⊗ a_2⊗ I^⊗ b_2⊗⋯⊗ P_m^⊗ a_m⊗ I^⊗ b_m,
 
where P commutes with all generators of C. Repeat the operator measurement using the 1-flag circuits until one of the following is satisfied:


	
  * If first two operator measurement results coincide (m^(1) = m^(2)) and there are no flags, perform the syndrome measurement twice using 1-flag circuits for flag-FTEC.
	
		
  * If s^(1) = s^(2) = 0 and there are no flags during both syndrome measurement rounds, output m^(1).
		
		
  * If s^(1)≠ s^(2) or at least one flag qubit flags during the syndrome measurement, apply the correction described by the flag-FTEC protocol of <ref>, then output m^(1).
		
		
  * If s^(1) = s^(2)≠ 0 and there are no flags during the syndrome measurement, apply the correction E_min(s^(1)). Repeat the operator measurement using a non-flag circuit, then output m^(3). 
	
	
	
  * If m^(1)≠ m^(2) and there are no flags, perform one syndrome measurement round using non-flag circuits for error correction and apply E_min(s^(1)). Repeat the operator measurement using a non-flag circuit, then output m^(3). 
	
	
  * If f_0 does not flag but f_i flags (with i ≥ 1) during round one, stop. Repeat the operator measurement using a non-flag circuit then output m^(2). If there are no flags during round one but f_i flags and f_0 does not flag during round two, output m^(1).
	
	
  * If f_0 flags at round r_1 anytime during the protocol, stop and do one of the followings:
	
		
  * If f_i does not flag for all i ≥ 1, repeat the operator measurement using a non-flag circuit and output m^(r_1+1).
		
		
  * If there is only one i such that f_i flags (with i ≥ 1), apply I^⊗ c⊗ P_i+1^⊗ a_i+1⊗ I^⊗ b_i+1⊗⋯⊗ P_m^⊗ a_m⊗ I^⊗ b_m to the data, where c = ∑_j=1^i a_j+b_j. Perform the syndrome measurement using non-flag circuits for error correction yielding syndrome s^(r_2) = (s^(r_2)_x|s^(r_2)_z). 
		
			
  * If P_i=Z, apply E_z ∈ℰ^z_l,n that satisfies s(E_z) = s^(r_2)_x  where l=n-c+b_i, followed by E_min(s^(r_2)_z).
			
  * If P_i=X, apply E_x ∈ℰ^x_l,n that satisfies s(E_x) = s^(r_2)_z  where l=n-c+b_i, followed by E_min(s^(r_2)_x).
			
  * If P_i=Y, apply E ∈ℰ^P_l,n that satisfies s(E) = s^(r_2) where l=n-c+b_i.
		
		Afterwards, repeat the operator measurement using a non-flag circuit, then output m^(r_1+1).
		
		
  * If there is an i such that f_i and f_i+1 flag, perform the same sequence of operations as in 4(b).
	
	


To see that <ref> is satisfied, we will assume that the weight of an input error v_1 and the number of faults during the protocol  v_2 satisfy v_1+v_2 ≤ 1. Similar to the FTEC protocol, f_0 and at least one f_i (with i≥ 1) will flag whenever a fault in any CNOT gate causes Z error on m_0. If there is no flags, a single fault can introduce error of weight at most one. If the measurement result is repeated twice, then there is no fault in the circuits. However, the measurement result might be incorrect due to the input error. By performing full syndrome measurement twice with flag circuits, we can determine from s^(1) and s^(2) whether these is no input error, there is a fault during syndrome measurement, or there is an input error of weight 1. The procedure in 1(a), 1(b), and 1(c) can correct possible errors and output the right operator measurement result with corresponding codeword after projective measurement.

Now let us consider the case that there is no flags but m^(1)≠ m^(2). This is the case where a fault occurred in either the first or second round. Therefore, performing error correction and repeating the operator measurement can give the correct result.

Next, consider the case that there is only one flag, either f_0 or f_i with i≥ 1. The fault could be a measurement error, idle qubit error on the ancilla f_0 or f_i, or an error on the control qubit of the CNOT gate interacting with f_0 or f_i. Repeating the operator measurement can give the right result. Note that if f_i flags during round two, then the result obtained during round one corresponds to the right outcome.

Now let us consider the case where a fault happens on a red CNOT introducing a Z error on the ancilla m_0 and a P̃ error on the data qubit where P̃∈{I,X,Y,Z}. If the fault occurs on the i^th sub-block, then f_0 and only one f_i with i ≥ 1 will flag. Applying I^⊗ c⊗ P_i+1^⊗ a_i+1⊗ I^⊗ b_i+1⊗⋯⊗ P_m^⊗ a_m⊗ I^⊗ b_m to the data guarantees that the resulting error is in the form I^⊗ c-a_i-b_i⊗ I^⊗ c-1⊗P̃⊗ P_i^⊗ a_i-c⊗ I^⊗ b_i⊗ I^⊗ n-c (where c = ∑_j=1^i a_j+b_j). If P_i=Z (or P_i=X), the resulting error is a product of consecutive error in ℰ^z_l,n (or ℰ^x_l,n) and X-type error (or Z-type error) of weight one, where l=n-c+b_i. If P_i=Y, the resulting error is a consecutive error in ℰ^P_l,n. By <ref>, errors in  ℰ^x_l,n, ℰ^z_l,n, and ℰ^P_l,n are distinguishable. Therefore, performing a full syndrome measurement followed by appropriate error correction as in 4(b) will remove the error, and repeating the operator measurement gives the correct outcome. The case that a fault occurs on a blue or green CNOT corresponds to either 4(b) or 4(c), and the same correction procedure can be applied.

A list of possible faults during the flag-FT operator measurement protocol and corresponding correction procedures is given in <ref> in <ref>.

The flag-FT measurement protocol described above is for a measurement of an operator commuting with all generators which acts in one code block. Surprisingly, the protocol also works for an operator acting on two or more code blocks. The measurement of such operator can be done by treating parts of the operator acting on different code blocks as operators from different sub-blocks. For example, let C_p and C_q be cyclic CSS codes of distance 3 satisfying <ref>, and let P and Q be Pauli operators acting on C_p and C_q, respectively. The measurement of P⊗ Q on the code C_p⊗ C_q can be done by using a 1-flag circuit given in <ref>, where P and Q are treated as operators from the different sub-blocks. Observe that if f_0 flags and at least one f_i flags (the 4(b) or 4(c) case), the resulting error after appropriate operation will become a consecutive error on either first or second code blocks. Since C_p and C_q are both cyclic, we can determine the error by performing subsequent syndrome measurement on only C_p or C_q, depending on the sub-block in which the fault occurs. After that, the correct measurement result can be obtained by a subsequent operator measurement.




§ APPLICATIONS OF FAULT-TOLERANT OPERATOR MEASUREMENT PROTOCOL


A measurement of an operator commuting with all generators can be used as a subroutine in numerous quantum information processing techniques such as state preparation and quantum gate implementation. Since the fault-tolerant measurement protocol described in <ref> is applicable on two or more code blocks, information processing between code blocks is possible. In this section we briefly describe some important techniques which make fault-tolerant computation on cyclic CSS codes possible, including logical EPR state preparation, teleportation, and quantum computation on logical qubits.

Let us consider an EPR state |00⟩+|11⟩/√(2). This is a +1 eigenstate of operators X ⊗ X and Z ⊗ Z. Let C_p and C_q be n_1,k_1,d_1 and n_2,k_2,d_2 cyclic CSS codes satisfying <ref> with stabilizer generating sets {g_i_1^p} and {g_i_2^q}, respectively. Suppose that we want to prepare a state

    |0̅⟩_p,i|0̅⟩_q,j+|1̅⟩_p,i|1̅⟩_q,j/√(2),

which is an EPR state between the i^th logical qubit of C_p and the j^th logical qubit of C_q. This can be done by performing projective measurements with respect to stabilizer generators {g_i_1^p⊗ I, I ⊗ g_i_2^q} and logical operators X̅_p,i⊗X̅_q,j and Z̅_p,i⊗Z̅_q,j on a totally mixed state, where X̅_p,i and X̅_q,j (or Z̅_p,i and Z̅_q,j) are logical X (or logical Z) operators on i^th logical qubit of C_p and j^th logical qubit of C_q, respectively. Since the measurement protocol described in <ref> is a fault-tolerant protocol, the state in <ref> can be prepared fault-tolerantly.

In conventional quantum teleportation, an EPR state and Bell measurement are required. Here we will examine a process to fault-tolerantly perform quantum teleportation of logical data between two code blocks. The scheme for logical qubit teleportation is shown in <ref>. Suppose that we would like to teleport the i^th logical qubit of C_p to the j^th logical qubit of C_q, first an EPR state |0̅⟩_q,j|0̅⟩_q,j+|1̅⟩_q,j|1̅⟩_q,j/√(2) prepared on C_q⊗ C_q is required. The logical qubit teleportation can be done by performing a Bell measurement with respect to X̅_p,i⊗X̅_q,j and Z̅_p,i⊗Z̅_q,j between C_p and the first block of C_q. The teleported logical qubit can be obtained in the second block of C_q by operating an appropriate logical Pauli operator P̅_q,j depending on the Bell measurement result. Note that the Bell measurement can be done fault-tolerantly using the measurement protocol in <ref>, and logical Pauli operators are transversal (therefore, fault tolerant). Thus, fault-tolerant teleportation between two code blocks can be achieved.

Now let us consider fault-tolerant computation on cyclic CSS codes. It is known that for any error correcting code, by the Eastin-Knill theorem <cit.>, at least one logical gate in a universal gate set cannot be implemented transversely. For such gates, other fault-tolerant techniques must be performed, which can require a significant amount of resources. Fortunately, fault-tolerant implementations of logical Clifford gates on distance-3 cyclic CSS codes can be achieved via quantum gate teleportation (see <cit.> for the details of quantum gate teleportation). For example, suppose that we would like to perform a logical Hadamard gate H̅_i on the code C_p. This can be achieved by preparing a codeword which is an eigenstate of X̅_i⊗Z̅_i and Z̅_i⊗X̅_i on C_p ⊗ C_p, performing logical qubit teleportation, and operating a logical Pauli operator H̅_p,iP̅_p,iH̅_p,i depending on the result from the Bell measurement in qubit teleportation as illustrated in <ref>. Also, logical R_π/4 = diag(1,i) and logical CNOT gates on any logical qubits can be performed in a similar way. The Clifford group can be generated by {H,R_π/4,CNOT} <cit.>. Thus, our scheme is applicable to any Clifford operation. It is known that universal quantum computation can be achieved by Clifford gates and any other gate not in the Clifford group <cit.>. However, performing logical non-Clifford gates will require different techniques such as the ones presented in <cit.>.





§ EXAMPLES OF CYCLIC CSS CODES



In this section, some examples of cyclic CSS codes satisfying <ref> are given. A first example is the 7,1,3 quantum Hamming code. This code is constructed from a classical [7,4,3] Hamming code (with C_x=C_z). A check polynomial of the [7,4,3] Hamming code in cyclic form is

    h(x) = 1+x^2+x^3+x^4.


In fact, any classical Hamming code can be made cyclic <cit.>. Thus, any CSS code constructed from a classical [2^r-1,2^r-1-r,3] Hamming code with C_x=C_z satisfies <ref>, and can be used in the flag-FTEC protocol and the flag-FT measurement protocol described in this work. 

Another example of cyclic CSS codes satisfying <ref> is the 30,14,3 code constructed from a classical [30,22,3] cyclic code with a check polynomial 

    h(x) = 1+x^2+x^4+x^6+x^10+x^14+x^16+x^22.


The [30,22,3] code and other classical codes satisfying C^⊥⊆ C are given in Table 1 of <cit.>. (A method of finding the check polynomial of a classical cyclic code is discussed in <cit.>.) One possible choice of logical operators for the 30,14,3 code is given in <ref>. The advantages of the 30,14,3 code are that its encoding rate is high (k/n = 14/30), and the logical operators of the first ten logical qubits have a simple form, which make them easily accessible. 
 


§ DISCUSSION AND CONCLUSION


In this work we used the symmetries of CSS codes constructed from classical cyclic codes to prove that errors written in consecutive form (as in <ref>) can be distinguished. From these properties, we can obtain a 1-flag circuit along with a flag-FTEC protocol which satisfies the fault-tolerance criteria of <ref> when there is at most one fault. The 1-flag circuit requires only four ancilla qubits. This number does not grow as the block length gets larger, making our protocol advantageous in the implementation where resources are limited. We note that not all cyclic CSS codes are Hamming codes and therefore the methods in <cit.> (which apply to perfect codes) cannot be directly applied, thus providing further motivation for our work. 

In general, cyclic CSS codes do not satisfy the sufficient condition required for flag fault-tolerance presented in <cit.> (one example is the family of Hamming codes which can be made cyclic). Nevertheless, using the techniques presented in this paper, a flag-FTEC protocol can still be achieved.  

Furthermore, we have shown how logical Pauli operators of cyclic CSS codes can be fault-tolerantly measured using the flag techniques discussed in <ref>. The flag-FT operator measurement protocol satisfies the fault-tolerance criteria of <ref> when there is at most one fault. We then showed in <ref> how one can fault-tolerantly perform quantum gate teleportation to implement logical Clifford operators on any given logical qubit for codes which encode multiple logical qubits. Examples of cyclic CSS codes with large encoding rates are provided in <ref>.

Note that for all CSS codes, the stabilizer generators being measured are of the form I^⊗ n-m⊗ X^⊗ m or I^⊗ n-m⊗ Z^⊗ m up to qubit permutations. Thus data qubit errors arising from faulty CNOT gates will be expressed in consecutive form. The errors of this form are distinguishable iff the sub-matrices of the X and Z stabilizers  satisfy <ref>. In our work, we use the symmetry of the cyclic codes to simplify <ref> into <ref>. We believe that <ref> can be simplified by using symmetries found in other families of quantum codes. With appropriate t-flag circuits and operations depending on the flag measurement outcome, this may lead to new flag fault-tolerant protocols.

Another interesting avenue is finding non-cyclic quantum codes for which a version of <ref> can be applied. We note that for such codes, the same 1-flag circuit as in <ref> along with the flag-FTEC protocol of <ref> and the flag-FT measurement protocol of <ref> can be used. The reason is that the key property used by these schemes is based on the distinguishability of consecutive errors.

Note that there are quantum cyclic codes which are not CSS codes for which flag fault-tolerant schemes are still possible. For instance, a flag-FTEC protocol for the 5,1,3 code was devised in <cit.>. We believe that it could be interesting to generalize the ideas presented in this work to non-CSS cyclic quantum codes. However, we leave this problem for future work. 

The flag fault-tolerant protocols for cyclic CSS codes presented in this work are based on the assumption that the qubit measurement and state preparation must be fast since we reuse some flag qubits in the protocols (as we can see in <ref>). If we do not reuse flag qubits, however, the number of required ancillas will be m+2 for an operator being measured of the form P = P_1^⊗ a_1⊗ I^⊗ b_1⊗ P_2^⊗ a_2⊗ I^⊗ b_2⊗⋯⊗ P_m^⊗ a_m⊗ I^⊗ b_m instead of 4.

One important feature of flag fault-tolerant protocols is that the number of required ancillas is very small compared to other fault-tolerant schemes. We believe that if fewer ancillas are required, the accuracy threshold will increase since the number of locations will decrease in total. However, we should point out that subsequent syndrome measurements are also required in a flag fault-tolerant protocol and may increase the total number of locations in the protocol. The answer of whether the accuracy threshold for a flag fault-tolerant protocol is greater or smaller compared to other fault-tolerant schemes is still unknown.

Lastly, we point out that cyclic CSS codes which satisfy the condition in <ref> are not limited to distance-3 codes. Therefore, interesting future work would be to use the methods of <cit.> to obtain flag fault-tolerant schemes for higher-distance codes. In particular, the main challenge stems from finding t-flag circuits as in <ref> for t > 1.



§ ACKNOWLEDGEMENTS

T.T. acknowledges the support of The Queen Sirikit Scholarship under The Royal Patronage of Her Majesty Queen Sirikit of Thailand. C.C. acknowledges the support of NSERC through the PGS D scholarship. D.L. is supported by an NSERC Discovery grant and a CIFAR research grant via the Quantum Information Science program. 




ieeetr






§ PROOF OF THE LEMMAS



Proof of <ref>: We will prove that ℰ^z_0,n is distinguishable by C iff for all p,q∈{0,1,...,n-1} such that p>q, there exists i∈{1,…,r_x} such that x_i,n-p+1⊕…⊕ x_i,n-q=1. Consider errors E_p=I^⊗ n-p⊗ Z^⊗p and E_q=I^⊗ n-q⊗ Z^⊗q where p,q∈{0,1,…,n-1}, p>q. Let s(E_p),s(E_q)∈ℤ_2^r be error syndromes corresponding to errors E_p and E_q, respectively. By <ref>, E_p and E_q are distinguishable by C iff s(E_p)≠ s(E_q), i.e., there exists i ∈{1,2, ⋯, r_x } such that s(E_p)_i≠ s(E_q)_i (here i corresponds to the i^th component of s(E_p) and S(E_q)). From the parity check matrix H_x, the i^th component of s(E_p) and s(E_q) is given by 

    s(E_p)_i    = x_i,n-p+1⊕ x_i,n-p+2⊕⋯⊕ x_i,n, 
    
    
    s(E_q)_i    = x_i,n-q+1⊕ x_i,n-q+2⊕⋯⊕ x_i,n.


From <ref>, we have that

    s(E_p)_i≠ s(E_q)_i    ⇔ s(E_p)_i⊕ s(E_q)_i = 1 
       ⇔ x_i,n-p+1⊕⋯⊕ x_i,n-q=1.

Thus, ℰ^z_0,n is distinguishable by C iff for all p,q∈{0,1,...,n-1} such that p>q, there exists i ∈{ 1,2, ⋯, r_x } such that

    x_i,n-p+1⊕…⊕ x_i,n-q=1.


The proof of the statement for ℰ^x_0,n is similar.

Now we will proof that ℰ^P_0,n is distinguishable by C iff both ℰ^z_0,n and ℰ^x_0,n are distinguishable by C. Let X_p = I^⊗ n-p⊗ X^⊗ p and Z_q = I^⊗ n-q⊗ Z^⊗ q, where p,q ∈{0,…,n-1}. Observe that any element of ℰ^P_0,n is of the form E_p,q = X_p · Z_q where X_p ∈ℰ^x_0,n and Z_q ∈ℰ^z_0,n. The syndrome of E_p,q is s(E_p,q) = (s(X_p)|s(Z_q)). If ℰ^P_0,n is distinguishable by C, i.e., s(E_p_1,q_1) ≠ s(E_p_2,q_2) for all choices of p_1,p_2,q_1,q_2 such that (p_1,q_1) ≠ (p_2,q_2), then we have that any pair of X_p_1 and X_p_2 and any pair of Z_q_1 and Z_q_2 are distinguishable. Conversely, if any pair of X_p_1 and X_p_2 and any pair of Z_q_1 and Z_q_2 are distinguishable, then any pair of E_p_1,q_1 and E_p_2,q_2 will have different syndromes. This implies Statement 3.


Proof of <ref>: Suppose that the stabilizer group of C can be generated by {g_1,g_2,…,g_n-k}. Since C is a CSS code, we will first assume that the generators g_i's are either X-type or Z-type, denoted as g^x_i or g^z_i. Let H_x and H_z be X and Z stabilizer matrices of the code C in symplectic representation, and let C^⊥_x and C^⊥_z be the classical codes generated by H_x and H_z, respectively. Observe that any element of C in symplectic representation is of the form (x|z) where x ∈ C^⊥_x and z ∈ C^⊥_z. For any choice of l ∈{0,1,…,n-1}, let H̃_x (or H̃_z) be the parity check matrix corresponding to ℒ(g^x_i,l)'s (or ℒ(g^z_i,l)'s). We find that the code C̃_x^⊥ generated by H̃_x (or C̃_z^⊥ generated by H̃_z) differs from C_x^⊥ (or C_z^⊥) by an l-step left cyclic permutation. However, since C_x^⊥ and C_z^⊥ are cyclic codes, we have that C̃_x^⊥ = C_x^⊥ and C̃_z^⊥ = C_z^⊥. Therefore, {ℒ(g^x_1,l),…,ℒ(g^x_r_x,l),ℒ(g^z_1,l),…,ℒ(g^z_r_z,l)} and {g^x_1,…,g^x_r_x,g^z_1,…,g^z_r_z} generate the same stabilizer group for any l ∈{0,1,…,n-1}. 

In general, some generators of the stabilizer group of C might be neither X-type nor Z-type. The following transformations of the generators preserve the stabilizer group, and the last set of generators is the cyclic shifts of the original: (1) Transform the given generators to either X-type or Z-type. This corresponds to appropriate reversible row operations on the binary symplectic representation of C to obtain the block diagonal form,

    [ A | 0; 0 | B ].

(2) Cyclic shifts of these new generators also generate the same stabilizer group. (3) Reversing the transformation in step (1) (now applied to the generators after step (2)) preserves the stabilizer group. The resulting generators are cyclic shifts of the original.

Proof of <ref>: First we will prove that ℰ^z_0,n is distinguishable by C iff for all u_x∈{2,3,…,n}, there exists i∈{1,…,r_x} such that x_i,u_x⊕…⊕ x_i,n=1.
Applying <ref>, we would like to prove that for all p,q∈{0,...,n-1} such that p>q, there exists i ∈{ 1, ⋯, r_x } such that x_i,n-p+1⊕…⊕ x_i,n-q=1  iff for all u_x∈{2,3,…,n}, there exist i' ∈{1, ⋯ , r_x } such that x_i',u_x⊕…⊕ x_i',n=1.

(⇒) By choosing q=0 and p=n-u+1, the proof is trivial.

(⇐) Assume by contradiction that there exists a pair of p,q ∈{0,1,…,n-1} with p>q such that x_i,n-p+1⊕…⊕ x_i,n-q=0 for all i; i.e., there exists a pair of errors E_p=I^⊗ n-p⊗ Z^⊗ p and E_q=I^⊗ n-q⊗ Z^⊗ q which cannot be distinguished by any generator of C. Let C be generated by {g_1,…,g_r}. By <ref>, we can construct a new generator set {g̃_1,…,g̃_r} of C where g̃_i = ℒ(g_i,q) for all i. Let the X-part of σ(g̃_i) be  (x̃_i,1,…,x̃_i,n)=(x_i,q+1,…,x_i,n,x_i,1,…,x_i,q). Note that x̃_n-p+1=x_i,n-(p-q)+1 and x̃_n-q=x_i,n. The assumption implies that E_p and E_q cannot be distinguished by any g̃_i as well. This gives

    x̃_i,n-p+1⊕…⊕x̃_i,n-q   =0,

or equivalently,

    x_i,n-(p-q)+1⊕…⊕ x_i,n   =0.

Let u_x = n-(p-q)+1. Therefore, there exists u_x ∈{2,3,…,n} such that x_i,u_x⊕…⊕ x_i,n=0 for all i.

The proof of statement for ℰ^x_0,n is similar to the proof of statement for ℰ^z_0,n, while the proof of statement for ℰ^P_0,n is similar to the proof of Statement 3 in <ref>.




We already proved statements for ℰ^z_0,n, ℰ^x_0,n, and ℰ^P_0,n. We will generalize the statements to ℰ^z_l,n, ℰ^x_l,n, and ℰ^P_l,n for any l ∈{0,…,n-1}. Let C̃ by a cyclic CSS code generated by {ℒ(g^x_1,l),…,ℒ(g^x_r_x,l),ℒ(g^z_1,l),…,ℒ(g^z_r_z,l)}. Observe that by qubit reordering, ℰ^P_l,n is distinguishable by C̃ iff ℰ^P_0,n is distinguishable by C. Since C̃ and C are the same code by <ref>, we have that ℰ^P_l,n is distinguishable by C for any l ∈{0,…,n-1} iff ℰ^P_0,n is distinguishable by C. The proof is also applied to ℰ^z_l,n and ℰ^x_l,n.



§ LISTS OF POSSIBLE FAULTS DURING FTEC AND FT OPERATOR MEASUREMENT PROTOCOLS


The lists of possible faults during the flag-FTEC protocol (see <ref>) and the flag-FT operator measurement protocol (see <ref>) are given in <ref>, respectively. The corresponding correction procedure for each type of faults refers to the step of either flag-FTEC protocol or flag-FT operator measurement protocol. Here we assume that v_2 ≤ 1 in the flag-FTEC protocol and v_1+v_2 ≤ 1 in the flag-FT operator measurement protocol, where v_1 is the number of input errors and v_2 is the number of faults.



