text:
# Of overlapping Cantor sets and earthquakes: Analysis of the discrete Chakrabarti-Stinchcombe model

## 1 Introduction

Earthquakes are outcomes of fault dynamics in the lithosphere. A geological fault is comprised of two rock surfaces in contact, created by a fracture in the rock layers. The two sides of the fault are in slow relative motion which causes the surfaces to slide. However, owing to friction the surfaces tend to stick and stress develops in the regions of contact. When the accumulated stress exceeds the resistance due to friction, the fault surfaces slip. The potential energy of the strain is thereby released, causing an earthquake. The slip is eventually stopped by friction and stress development resumes. Strain continues to develop till the fault surfaces slip again. This intermittent stick-slip process is the essential feature of fault dynamics. The overall distribution of earthquakes, including main shocks, foreshocks and aftershocks, is given by the Gutenberg-Richter law :

$$\mathrm{log}_{10}\mathrm{Nr}(>M)=abM$$
(1)
where, $`\mathrm{Nr}(>M)`$ denotes the number (or, the frequency) of earthquakes of magnitudes $``$ that are greater than a certain value $`M`$. The constant $`a`$ represents the total number of earthquakes of all magnitudes: $`a=\mathrm{log}_{10}\mathrm{Nr}(>0)`$ and the value of the coefficient $`b1`$ is presumed to be universal. In an alternative form, the Gutenberg-Richter law is expressed as a relation for the number (or, the frequency) of earthquakes in which the energy released $``$ is greater than a certain value $`E`$:

$$\mathrm{Nr}(>E)E^{b/\beta }$$
(2)
where $`\beta 3/2`$ is the coefficient in the energy-magnitude relation .

One class of models for simulating earthquakes is based on the collective motion of an assembly of connected elements that are driven slowly, of which the block-spring model due to Burridge and Knopoff  is the prototype. The Burridge-Knopoff model and its variants  have the stick-slip dynamics necessary to produce earthquakes. The underlying principle in this class of models is self-organized criticality .

Another class of models for simulating earthquakes is based on overlapping fractals. These models are motivated by the observation that a fault surface is a fractal object . Consequently a fault may be viewed as a pair of overlapping fractals. Fractional Brownian profiles have been commonly used as models of fault surfaces . In that case the dynamics of a fault is represented by one Brownian profile drifting on another and each intersection of the two profiles corresponds to an earthquake . However the simplest possible model of a fault $``$ from the fractal point of view $``$ was proposed by Chakrabarti and Stinchcombe . This model is a schematic representation of a fault by a pair of dynamically overlapping Cantor sets. It is not realistic but, as a system of overlapping fractals, it has the essential feature. Since the Cantor set is a fractal with a simple construction procedure, it allows us to study in detail the statistics of the overlap of one fractal object on another.

In this paper we study the outcome of discrete dynamics in the Chakrabarti-Stinchcombe model. Our first aim is to construct the time-series of overlaps of the $`n`$-th generation of the regular Cantor set on its replica with periodic boundary conditions, where one set shifts on the other in discrete steps. We use a finite generation of the Cantor set since self-similarity in natural objects extends only over a finite range. In this model the overlap magnitudes and their logarithms correspond to the energies released and the magnitudes of earthquakes respectively. Our second aim is to obtain the statistics of the overlap magnitudes. From the time-series we derive the exact frequency distribution of the overlap magnitudes. For the $`n`$-th generation of the Cantor set the probability distribution of the logarithm of overlap magnitudes is found to assume the form of a binomial distribution for $`n`$ Bernoulli trials and not an exponential law or a power law of the forms expressed in Eqs. (1) and (2). As the Cantor set is approached through successive generations, the most probable overlap magnitude is found to approach the cube-root of the maximum overlap magnitude. Our third aim is to determine whether it is possible to predict the occurrence of an overlap of a particular magnitude after a certain interval of time from an overlap that is known to have occurred. For this purpose we apply the theory of conditional probability. We consider the simplest case, that of two consecutive overlaps in the time-series, where the magnitude of the earlier overlap is preassigned and using this we calculate the probabilities of all possible magnitudes of the later overlap. Each conditional probability is found to follow a binomial distribution for a certain number of Bernoulli trials that is determined by the magnitude of the earlier overlap. The asymptotic form of the most probable magnitude of the later overlap is found to be inversely proportional to the square-root of the magnitude of the earlier overlap. We use the expression for the conditional probability to study three important cases: where the magnitude of the later overlap is less than that of the earlier one, where it is the converse of the previous case and where the magnitude of the two overlaps are equal. On the basis of the fractal overlap analogy between a pair of fault surfaces and a pair of overlapping Cantor sets, our results indicate that, from the knowledge of earthquakes recorded in the past it is possible to predict, with a probability, the magnitude of earthquakes at least for a short term in the future.

## 2 The model: Two dynamically overlapping Cantor sets

We consider a discrete form of the model of fault dynamics proposed by Chakrabarti and Stinchcombe . The construction of the model requires two identical generations of the regular Cantor set. The procedure of constructing a regular Cantor set begins with a line segment of unit length, called the ‘initiator’. This line segment is divided into three equal parts and the middle part is removed to obtain the first generation; that serves as the ‘generator’ of the Cantor set . The procedure is repeated for each of the two line segments of the first generation to obtain the second generation and so on. Therefore the $`n`$-th generation of the Cantor set is a finite set of $`2^n`$ line segments, each of length $`1/3^n`$. If this procedure is repeated an infinite number of times the remainder set of discrete points is called the regular Cantor set. In the rest of this paper the term Cantor set will always mean the regular Cantor set that we have just described. It is an exact self-similar fractal of dimension $`\mathrm{log}_32`$. The construction of the first few generations is shown in Fig. 1. Since it is practically impossible to generate the regular Cantor set exactly, we use the set of line segments obtained after a finite number of generations. It is reasonable to work with a finite generation of the Cantor set since in all naturally occurring fractals the notion of self-similarity only applies between a lower and an upper cutoff length .

The model is defined in terms of two dynamically overlapping fractals which are represented by the $`n`$-th generation of the Cantor set and its replica. The sequences of line segments in the two finite sets of the $`n`$-th generation are considered as a schematic representation of the fractal profiles of the two surfaces of the fault. The magnitude of the overlap of one fault surface on the other is measured in this model as the number of line segments of one set that overlap exactly on line segments of the other set and we denote it by $`Y_n`$ for the $`n`$-th generation sets. The motion of the fault surfaces is simulated by shifting one of the sets relative to the other in the following manner. We assume that initially the $`n`$-th generation of the Cantor set and its replica overlap completely, i.e., every line segment of one set overlaps exactly on the corresponding line segment of the other set. Then we shift one of the two finite sets relative to the other in one particular direction in uniform discrete steps of length $`1/3^n`$, that is the length of a line segment in the $`n`$-th generation. The length of a step is chosen to be $`1/3^n`$ in order to ensure that each line segment of one set either overlaps exactly on one of the other set or does not overlap at all. The overlap magnitude $`Y_n`$ after every step is given by the number of overlapping segments. Consequently it is convenient to define time $`t`$ for this dynamical process as a discrete variable and measure its value as the number of uni-directional steps by which one set has shifted from its initial position relative to the other. The time-series of overlaps is given by the sequence $`\{Y_n(t)\}`$. Due to the discrete nature of the shifting process the magnitude of the overlap has discrete values. Further the structure of the $`n`$-th generation allows the number of overlapping segments to be in powers of 2 only: $`Y_n=2^{nk}`$, $`k=0,\mathrm{},n`$. We shall write the magnitude of overlap as $`2^{nk}`$ in order to indicate the generation $`n`$ to which it belongs. We use periodic boundary conditions which produces a periodicity in the time-series. In Fig. 3 we plot the time-series of overlap for the first few generations of the Cantor set. These plots show that the time-series has the appearance of a self-affine profile.

## 3 Construction of the time-series

In the following we construct the time-series of overlaps $`Y_n(t)`$ of the $`n`$-th generation of the Cantor set on its replica by determining all of its structural features. We assume that periodic boundary conditions are assigned to the finite sets. The structural features of the time-series consist of a periodicity, a symmetry and a set of distinct temporal sequences of overlap magnitudes. The most important are the sequences of constant magnitude overlaps. The complete time-series is derived by superposing the constant overlap sequences of all possible overlap magnitudes.

(i) Since the initial condition is chosen as the complete overlap of the two sets, the initial overlap is maximum and its magnitude is given by:

$$Y_n(0)=\mathrm{max}Y_n=2^n.$$
(3)
(ii) Since the length of each line segment in the $`n`$-th generation of the Cantor set is $`1/3^n`$ and the boundary conditions are periodic, the time-series of the overlap for the generation $`n`$ repeats itself after every $`3^n`$ time-steps:

$$Y_n(t)=Y_n\left(t+3^n\right).$$
(4)
Subsequently whenever we shall refer to the variable $`t`$ and its values it will mean

$$tt\mathrm{mod}\mathrm{\hspace{0.25em}3}^n,$$
(5)
such that we shall study the time-series within the period $`0t<3^n`$.

(iii) Since the structure of all generations of the Cantor set is symmetric about its center and the boundary conditions are periodic, the time-series of the overlap in the period $`0t<3^n`$ (i.e., in all periods of the kind $`k3^nt<(k+1)3^n`$, $`k=0,1,2,\mathrm{}`$) has a symmetric form:

$$Y_n(t)=Y_n\left(3^nt\right),0t<3^n.$$
(6)
Therefore, for every sequence of overlaps occurring at time-steps $`\{t\}`$ within a period of the time-series, we have a complementary sequence of overlaps occurring at the time-steps $`\{3^nt\}`$ within the same period.

(iv) After the first $`3^{n1}`$ time-steps of shifting one $`n`$-th generation set relative to the other, the overlapping region is similar to the generation $`n1`$ of the Cantor set. Consequently the next $`3^{n1}`$ time-steps forms a period of the time-series of overlap of two sets of generation $`n1`$. Within this period of $`3^{n1}`$ time-steps, after the first $`3^{n2}`$ time-steps the overlapping region is similar to the generation $`n2`$ of the Cantor set and therefore the next $`3^{n2}`$ time-steps form a period of the time-series of overlap of two sets of generation $`n2`$. This process occurs recursively and therefore a period of the time-series of the generation-$`n`$ overlap is a nested structure of the periods of the time-series of the overlaps of all the preceding generations, for example, after $`3^{n1}+3^{n2}+\mathrm{}+3^{nk}`$ time-steps the overlapping region is similar to generation $`nk`$ of the Cantor set, for which, following Eq.(3), the magnitude of overlap is given by:

$$Y_n\left(\underset{r=1}{\overset{k}{}}3^{nr}\right)=2^{nk};k=1,\mathrm{},n.$$
(7)
The sequence of overlaps generated by Eq. (7) and the complementary sequence obtained by the symmetry property of Eq. (6), along with the initial condition (Eq. 3), forms the skeleton of the entire time-series (illustrated in part (a) of Fig. 2). The self-affine profile of the time-series observed in Fig. 3 is due to this property of the overlap. However it does not provide any more detail of the time-series.

(v) If the generation-$`n`$ of a Cantor set is shifted by a single time-step relative to another, the resulting overlap is just a unit line segment – owing to the periodic boundary conditions the last line segment of the former set overlaps on the first line segment of the latter set. This overlapping segment is similar to the initiator of the Cantor set (i.e., generation zero) with respect to the ratio $`1/3^n`$. Similarly, after a shift by three time-steps, the last two line segments of the former set overlaps on first two line segments of the latter set and the overlapping region is similar to the first generation of the Cantor set with respect to the ratio $`1/3^{n1}`$. In general, owing to the periodic boundary conditions, a shift of $`3^k`$ time-steps ($`0kn`$) from the initial position results in the overlapping of the last $`2^k`$ line segments of one set on the first $`2^k`$ segments of the other set and the overlapping region is similar to the generation-$`k`$ of the Cantor set with respect to the ratio $`1/3^{nk}`$. Therefore, beginning with a unit overlap resulting after a unit time-step, a sequence of shifts (time-steps) that are in geometric progression with $`\mathrm{common}\mathrm{ratio}=3`$ produce a sequence of overlaps with magnitudes that are in geometric progression with $`\mathrm{common}\mathrm{ratio}=2`$:

$$Y_n\left(3^k\right)=2^k;k=0,\mathrm{},n.$$
(8)
This structural feature is illustrated in part (b) of Fig. 2. The same geometric progression of overlap magnitudes also occur for a geometric progression of time-steps beginning with a unit overlap after the fifth time-step:

$$Y_n\left(5\times 3^k\right)=2^k;k=0,\mathrm{},n.$$
(9)
For each of the sequences given by Eqs. (8) and (9) the complementary sequence is obtained by the symmetry property of Eq. (6).

(vi) Since the $`n`$-th generation of the Cantor set contains $`2^n`$ line segments that are arranged by the generator in a self-similar manner, the magnitude of the overlaps, beginning from the maximum, form a geometric progression of descending powers of 2. As the magnitude of the maximum overlap is $`2^n`$ (observed at $`t=0`$), the magnitude of the next largest overlap is $`2^{n1}`$, i.e., a half of the maximum. A pair of nearest line segments form a doublet and the generation-$`n`$ of the Cantor set has $`2^{n1}`$ such doublets. Within a doublet, each of the two line segments are two steps away from the other. Therefore, if one of the sets is shifted from its initial position by two time-steps relative to the other, only one of the segments of every doublet of the former set will overlap on the other segment of the corresponding doublet of the latter set, thus resulting in an overlap of magnitude $`2^{n1}`$. An overlap of $`2^{n1}`$ also occurs if we consider quartets formed of pairs of nearest doublets and shift one set from its initial position by $`2\times 3`$ time-steps relative to the other. Similarly, in the case of octets formed of pairs of nearest quartets, a shift of $`2\times 3^2`$ time-steps is required to produce an overlap of $`2^{n1}`$. Considering pairs of blocks of $`2^{r_1}`$ nearest segments ($`r_1n1`$), an overlap of magnitude $`2^{n1}`$ occurs for a shift of $`2\times 3^{r_1}`$ time-steps:

$$Y_n\left(2\times 3^{r_1}\right)=2^{n1};r_1=0,\mathrm{},n1.$$
(10)
The complementary sequence is obtained as usual by the symmetry property of Eq. (6). An illustration of this constant overlap sequence is given in part (c) of Fig. 2.

Because of the self-similar structure of the Cantor set the line of argument used to derive Eq. (10) will work recursively for overlaps of all consecutive magnitudes. For example, the next overlap magnitude is $`2^{n2}`$, i.e., a quarter of the maximum. For each time-step $`t_1`$ at which an overlap of $`2^{n1}`$ segments occur, there are two subsequences of overlaps of $`2^{n2}`$ segments that are mutually symmetric with respect to $`t_1`$; one of the subsequences precedes $`t_1`$, the other succeeds $`t_1`$. Therefore the sequence of $`t`$ values at which an overlap of $`2^{n2}`$ segments occurs is determined by the sum of two terms, one from each of two geometric progressions, one nested within the other:

$$Y_n\left(2\left[3^{r_1}\pm 3^{r_2}\right]\right)=2^{n2};$$
(11)
$`r_1`$ $`=`$ $`1,\mathrm{},n1;`$
$`r_2`$ $`=`$ $`0,\mathrm{},r_11.`$
The first term belongs to the geometric progression that determines the sequence of $`t`$ values appearing in equation Eq. (10) for the overlaps of $`2^{n1}`$ segments, while the second term belongs to a geometric progression nested within the first. The symmetry property of Eq. (6) provides the complementary sequence.

In general the sequence of time-step values at which an overlap of $`2^{nk}`$ segments ($`1kn`$) occurs is determined by the sum of $`k`$ terms, one from each of $`k`$ geometric progressions, nested in succession:

$$Y_n\left(2\left[3^{r_1}\pm 3^{r_2}\pm \mathrm{}\pm 3^{r_{k1}}\pm 3^{r_k}\right]\right)=2^{nk};$$
(12)
$`k=1,\mathrm{},n`$ ;
$`r_1`$ $`=`$ $`k1,\mathrm{},n1;`$
$`r_2`$ $`=`$ $`k2,\mathrm{},r_11;`$
$`\mathrm{}`$ $`\mathrm{}`$
$`r_{k1}`$ $`=`$ $`1,\mathrm{},r_{k2}1;`$
$`r_k`$ $`=`$ $`0,\mathrm{},r_{k1}1.`$
For each value of $`k`$ in the above equation there is a complementary sequence due to the symmetry property of Eq. (6). Eq. (12) along with Eqs. (3), (4) and (6) determine the entire time-series of overlaps of the $`n`$-th generation of the Cantor set on its replica. Assuming that the initial overlap is given by Eq. (3), the time-series is the superposition of the sequences of constant magnitude overlaps given by Eq. (12) for all possible overlap magnitudes.

Now we consider the special case of unit overlaps, i.e., when the overlap is only on a unit segment. We shall write the magnitude of a unit overlap for the $`n`$-th generation of the Cantor set as $`2^{nn}`$ in order to indicate the generation index explicitly. A unit overlap occurs when $`k=n`$ in Eq. (12). The sequence of $`t`$ values at which these occur is given by:

$$Y_n\left(2\left[3^{n1}\pm 3^{n2}\pm \mathrm{}\pm 3^1\pm 3^0\right]\right)=2^{nn}=1.$$
(13)
The above equation shows $`2^{n1}`$ occurrences of the unit overlap. The same number of unit overlaps also occur in the complementary sequence obtained by using Eq. (6). Therefore, in a period of the time-series for the $`n`$-th generation, there are altogether $`2^n`$ unit overlaps.

## 4 Analysis of the time-series

The analysis of the complete time-series determined by Eqs. (3), (4), (6) and Eq. (12) is carried out in two parts. First we systematically derive the exact number of overlaps of any magnitude $`Y_n`$ in a period of the time-series. Next we apply probability theory. The probability of occurrence of an overlap of magnitude $`Y_n`$ after any arbitrary time-step is obtained directly from its frequency. We then derive the conditional probability of the occurrence of an overlap of magnitude $`Y_n^{}`$ if it is given that the preceding overlap in the time-series has magnitude $`Y_n`$.

### 4.1 Frequency of overlap magnitudes

In the following $`\mathrm{Nr}(Y_n)`$ denotes the frequency of overlaps of magnitude $`Y_n`$, i.e., the number of times an overlap of $`Y_n`$ segments occurs in a period of the time-series for $`n`$-th generation of the Cantor set. From the sequences defined by Eqs. (3), (10) and (11) and their complementary parts, we get respectively:

$$\mathrm{Nr}\left(2^n\right)=1,$$
(14)
$$\mathrm{Nr}\left(2^{n1}\right)=2n$$
(15)
and

$$\mathrm{Nr}\left(2^{n2}\right)=2\underset{r_1=1}{\overset{n1}{}}2r_1=2n(n1).$$
(16)
Similarly we can calculate the frequency of overlaps of all magnitudes. For example,

$`\mathrm{Nr}\left(2^{n3}\right)`$ $`=`$ $`2{\displaystyle \underset{r_1=2}{\overset{n1}{}}}2{\displaystyle \underset{r_2=1}{\overset{r_11}{}}}2r_2`$ (17)
$`=`$ $`{\displaystyle \frac{4}{3}}n(n1)(n2),`$
$`\mathrm{Nr}\left(2^{n4}\right)`$ $`=`$ $`2{\displaystyle \underset{r_1=3}{\overset{n1}{}}}2{\displaystyle \underset{r_2=2}{\overset{r_11}{}}}2{\displaystyle \underset{r_3=1}{\overset{r_21}{}}}2r_3`$ (18)
$`=`$ $`{\displaystyle \frac{2}{3}}n(n1)(n2)(n3),`$
$`\mathrm{Nr}\left(2^{n5}\right)`$ $`=`$ $`2{\displaystyle \underset{r_1=4}{\overset{n1}{}}}2{\displaystyle \underset{r_2=3}{\overset{r_11}{}}}2{\displaystyle \underset{r_3=2}{\overset{r_21}{}}}2{\displaystyle \underset{r_4=1}{\overset{r_31}{}}}2r_4`$ (19)
$`=`$ $`{\displaystyle \frac{4}{15}}n(n1)(n2)(n3)(n4).`$
In general, from Eq. (12) the frequency of overlaps of magnitude $`Y_n=2^{nk}`$ is given by:

$`\mathrm{Nr}\left(2^{nk}\right)`$ $`=`$ $`2{\displaystyle \underset{r_1=k1}{\overset{n1}{}}}2{\displaystyle \underset{r_2=k2}{\overset{r_11}{}}}\mathrm{}\mathrm{\hspace{0.25em}2}{\displaystyle \underset{r_{k1}=1}{\overset{r_{k2}1}{}}}2r_{k1}`$ (20)
$`=`$ $`C_kn(n1)(n2)\mathrm{}(nk+1)`$
$`=`$ $`C_k{\displaystyle \frac{n!}{(nk)!}}.`$
The value of the constant $`C_k`$ is determined from the case of unit overlaps in the following way. In the above equation we keep the index $`k`$ constant and choose the generation index $`n=k`$. As a result we get the frequency of unit overlaps for the $`k`$-th generation:

$$\mathrm{Nr}\left(2^{kk}\right)=C_kk!.$$
(21)
(We have followed the notation explained before Eq. (13) that the magnitude of the unit overlap for the $`k`$-th generation of the Cantor set is written as $`2^{kk}`$ in order to indicate the generation index.) On the other hand, we get the frequency of the unit overlap for the $`k`$-th generation from the sequence defined in Eq. (13) by replacing the index $`n`$ by $`k`$:

$$\mathrm{Nr}\left(2^{kk}\right)=2^k.$$
(22)
Comparing Eqs. (21) and (22) we get the value of the constant:

$$C_k=\frac{2^k}{k!}.$$
(23)
Now we have the complete formula for the frequency of overlaps of magnitude $`Y_n=2^{nk}`$ in the time-series for the $`n`$-th generation of the Cantor set:

$`\mathrm{Nr}\left(2^{nk}\right)`$ $`=`$ $`{\displaystyle \frac{2^k}{k!}}{\displaystyle \frac{n!}{(nk)!}}`$ (26)
$`=`$ $`2^k\left(\begin{array}{c}n\\ k\end{array}\right),k=0,\mathrm{},n`$
where $`\left(\begin{array}{c}n\\ k\end{array}\right)`$ denotes the binomial coefficient. The frequency distribution $`\mathrm{Nr}(Y_n)`$ obtained in Eq. (26) above for the overlap magnitudes $`Y_n=2^{nk}`$, $`k=0,\mathrm{},n`$, is exact. It is our central result and all subsequent results in this paper will be derived from it. It differs from the earlier claims  that the frequency distribution follows a power law; possible reason for this difference will be mentioned in the discussion.

Using the binomial theorem, we have for the entire period:

$$\underset{k=0}{\overset{n}{}}\mathrm{Nr}\left(2^{nk}\right)=\underset{k=0}{\overset{n}{}}2^k\left(\begin{array}{c}n\\ k\end{array}\right)=3^n,$$
(27)
since there are $`3^n`$ time-steps in a period of the time-series. From Eq. (26) we can calculate the cumulative frequency of overlaps with magnitudes that are greater than a preassigned value, say, $`2^{nk}`$, by a partial sum of binomial terms:

$$\mathrm{Nr}\left(Y_n2^{nk}\right)=\underset{r=0}{\overset{k}{}}\mathrm{Nr}\left(2^{nr}\right)=\underset{r=0}{\overset{k}{}}2^r\left(\begin{array}{c}n\\ r\end{array}\right),$$
(28)
which does not have a closed form. Fig. 4 shows the frequency distribution and cumulative distribution of overlap magnitudes for three consecutive generations. For large overlap magnitudes, which is realized for large values of $`n`$ and $`kn`$, Eq. (26) reduces to the following asymptotic form:

$$\mathrm{Nr}\left(2^{nk}\right)\frac{2^kn^k}{k!}.$$
(29)
This is evident from the expressions for $`k=0,\mathrm{},5`$ in Eqs. (14)–(19). Using the notations $`Y_n=2^{nk}`$ and $`\mathrm{max}Y_n=2^n`$, Eq. (29) for the $`n`$-th generation may be written as:

$$\mathrm{Nr}\left(Y_n\right)\left(\frac{\mathrm{max}Y_n}{Y_n}\right)^{1+\mathrm{log}_2n}\frac{1}{\left(\mathrm{log}_2\left[(\mathrm{max}Y_n)/Y_n\right]\right)!}$$
(30)
which shows that the factor $`1/Y_n`$, which was the one obtained in , is overwhelmed by the factor $`1/Y_n^{\mathrm{log}_2n}`$ in the expression for $`\mathrm{Nr}\left(Y_n\right)`$ for large $`n`$ and small $`k`$.

### 4.2 Prediction probability of overlap magnitudes

We now analyze the time-series of overlap from the point of view of probability theory. The treatment by probability theory is necessary to determine whether the occurrence of an overlap of a certain magnitude can be predicted from the knowledge of the magnitude of an overlap that has already occurred. We continue to consider the case of the $`n`$-th generation of the Cantor set overlapping on its replica. Let $`\mathrm{Pr}(Y_n)`$ denote the probability that after any arbitrary time-step $`t`$ we get an overlap of $`Y_n`$ segments. For the general case, $`Y_n=2^{nk}`$, $`k=0,\mathrm{},n`$, it is given by:

$`\mathrm{Pr}\left(2^{nk}\right)`$ $`=`$ $`{\displaystyle \frac{\mathrm{Nr}\left(2^{nk}\right)}{_{k=0}^n\mathrm{Nr}\left(2^{nk}\right)}}`$ (33)
$`=`$ $`{\displaystyle \frac{2^k}{3^n}}\left(\begin{array}{c}n\\ k\end{array}\right)`$
$`=`$ $`\left(\begin{array}{c}n\\ nk\end{array}\right)\left({\displaystyle \frac{1}{3}}\right)^{nk}\left({\displaystyle \frac{2}{3}}\right)^k.`$ (36)
The final expression in the above equation has the form of the binomial distribution for $`n`$ Bernoulli trials  with probability $`1/3`$ for the success of each trial and therefore $`\mathrm{Pr}\left(Y_n\right)`$ stands for the probability of the case where the number of successes is given by $`\mathrm{log}_2Y_n`$. Since $`\mathrm{Pr}\left(2^{nk}\right)`$ is maximum for $`k=2(n+1)/3`$ (and also for $`k=2(n+1)/31`$ when $`n+1`$ is a multiple of 3), the most probable overlap magnitude in general is given by:

$$\widehat{Y}_n=2^{n2(n+1)/3}$$
(37)
where the floor function $`x`$ is defined as the greatest integer less than or equal to $`x`$ . Since $`\mathrm{max}Y_n=2^n`$, we get the following asymptotic relation for large values of the generation index $`n`$:

$$\widehat{Y}_n\left(\mathrm{max}Y_n\right)^{1/3}.$$
(38)
Next we consider the conditional probability that an overlap of magnitude $`Y_n^{}`$ occurs after the time-step $`t+1`$ if it is known that an overlap of magnitude $`Y_n`$ has occurred after the previous time-step $`t`$, for any arbitrary $`t`$. The conditional probability is given by:

$$\mathrm{Pr}\left(Y_n^{}|Y_n\right)=\frac{\mathrm{Nr}(Y_n,Y_n^{})}{\mathrm{Nr}\left(Y_n\right)}$$
(39)
where $`\mathrm{Nr}(Y_n,Y_n^{})`$ is the number of ordered pairs of consecutive overlaps $`(Y_n,Y_n^{})`$ occurring in a period of the time-series for the $`n`$-th generation. It follows from Eq. (12) that overlaps of magnitude $`2^{nk}`$ in the time-series are immediately succeeded (i.e., after the next time-step) by overlaps of magnitude $`2^r`$, $`0rk`$ only and never by an overlap of magnitude greater than $`2^k`$. For $`Y_n=2^{nk}`$ and $`Y_n^{}=2^r,r=0,\mathrm{},k`$ we have:

$$\mathrm{Nr}(2^{nk},2^r)=\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}k\\ r\end{array}\right).$$
(40)
Therefore, from Eqs. (26), (39) and (40) we get:

$`\mathrm{Pr}\left(2^r|2^{nk}\right)`$ $`=`$ $`{\displaystyle \frac{1}{2^k}}\left(\begin{array}{c}k\\ r\end{array}\right);\begin{array}{c}k=0,\mathrm{},n\\ r=0,\mathrm{},k\end{array}`$ (45)
$`=`$ $`\left(\begin{array}{c}k\\ r\end{array}\right)\left({\displaystyle \frac{1}{2}}\right)^r\left({\displaystyle \frac{1}{2}}\right)^{kr}.`$ (48)
Here we find that the conditional probability follows the binomial distribution for $`k`$ Bernoulli trials with probability $`1/2`$ for the success of each trial. Eq. (48) shows that the expression of $`\mathrm{Pr}(2^r|2^{nk})`$ is independent of the generation index $`n`$. Therefore, for fixed $`k`$ and $`r`$, it has the same value for all generations $`n`$, provided that $`0rkn`$. Since the conditional probability $`\mathrm{Pr}(2^r|2^{nk})`$ is maximum when $`r=(k+1)/2`$ (and also for $`r=(k+1)/21`$ when $`k+1`$ is a multiple of 2), the most probable overlap magnitude $`\widehat{Y}_n^{}`$ to occur next to an overlap of magnitude $`Y_n=2^{nk}`$ is given by:

$$\widehat{Y}_n^{}=2^{(k+1)/2}.$$
(49)
For large values of the generation index $`n`$ and large $`k`$, $`kn`$, from the above equation we get the following asymptotic relation:

$$\widehat{Y}_n^{}\sqrt{\frac{\mathrm{max}Y_n}{Y_n}}.$$
(50)
We consider three applications of Eq. (48) assuming in each case that $`Y_n=2^{nk}`$ and $`Y_n^{}`$ is the overlap magnitude occurring next to $`Y_n`$ in the time-series. First, we find that

$`\mathrm{Pr}(Y_n^{}Y_n|Y_n)`$ $`=`$ $`{\displaystyle \underset{r=0}{\overset{k}{}}}\mathrm{Pr}\left(2^r|2^{nk}\right)`$ (51)
$`=`$ $`1\mathrm{for}0k{\displaystyle \frac{n}{2}}.`$
This implies that, for $`kn/2`$, an overlap of magnitude $`Y_n=2^{nk}`$ is always followed by an overlap of equal or less magnitude $`Y_n^{}`$. Consequently the case of an overlap of magnitude greater than that of the preceding one (i.e., $`Y_n^{}>Y_n`$) appears only for $`k>n/2`$. Second, we have

$`\mathrm{Pr}(Y_n^{}Y_n|Y_n)`$ $`=`$ $`{\displaystyle \underset{r=nk}{\overset{k}{}}}\mathrm{Pr}\left(2^r|2^{nk}\right)`$ (54)
$`=`$ $`{\displaystyle \frac{1}{2^k}}{\displaystyle \underset{r=nk}{\overset{k}{}}}\left(\begin{array}{c}k\\ r\end{array}\right)\mathrm{for}{\displaystyle \frac{n}{2}}kn.`$
Since the final expression in the above equation involves a partial sum of binomial coefficients, it does not have a closed form, except for the trivial case $`k=n`$ and a few other special cases. Therefore it must be calculated numerically for specific values of $`n`$ and $`k`$. Third, if the magnitude of overlap after a certain time-step is $`Y_n=2^{nk}`$, the probability that an overlap of the same magnitude also occurs after the next time-step is given by:

$`\mathrm{Pr}\left(Y_n^{}=Y_n|Y_n\right)`$ $`=`$ $`\mathrm{Pr}\left(2^{nk}|2^{nk}\right)`$ (59)
$`=`$ $`\{\begin{array}{cc}0,& 0k<n/2\\ \frac{1}{2^k}\left(\begin{array}{c}k\\ nk\end{array}\right),& n/2kn\end{array}.`$
In this way we can derive the probability of various cases where $`Y_n^{}`$ is specifically related to $`Y_n`$.

## 5 Discussion

In this paper we have reported the construction and analysis of the time-series of overlaps for the discrete Chakrabarti-Stinchcombe model where the $`n`$-th generation of the Cantor set shifts on its replica, with periodic boundary conditions, in discrete uniform steps. The $`n`$-th generation of the Cantor set is effectively a fractal for lengths between $`1`$ and $`1/3^n`$ (or, between $`1`$ and $`3^n`$, if the length of a line segment in the $`n`$-th generation is taken as the unit) and therefore it has no characteristic scale within this range; this is also reflected in the structure of the time-series within a period. However the frequencies and the corresponding probabilities of the binary logarithm of overlap magnitudes follow a binomial distribution, which has a characteristic scale given by the most probable overlap magnitude. The existence of a most probable value in the frequency distribution creates the possibility of predicting overlap magnitudes in the time-series. We have shown the utility of this simple model in predicting an event from the knowledge of the preceding event. Though it is believed that earthquakes cannot be predicted , the analysis presented in the previous section indicates that the overlapping fractal structure of faults ought to admit probabilistic predictions of earthquake magnitudes. It is left to be explored how the probability of predicting an overlap magnitude in this model increases with the width of the preceding interval of time-steps within which all the overlap magnitudes are known.

The Chakrabarti-Stinchcombe model, proposed for studying the mechanism of earthquakes, is by far the simplest model containing the rudiments of the overlapping structure of a geological fault. The authors of the original model  analysed, using renormalization group argument, the case of the Cantor set shifting continuously over its replica with open boundary conditions and reported that the density of the overlap magnitudes $`Y`$, in the infinite generation limit ($`n\mathrm{}`$), was in the form of a continuous power law: $`\rho (Y)1/Y`$. However the discrete form of the model defined for finite generations of the Cantor set with periodic boundary conditions – the subject of this paper – has a binomial distribution of the binary logarithm of overlap magnitudes (Eq. 26 or Eq. 36). If, instead of periodic boundary conditions, open boundary conditions are used, the time-series will be of finite duration, consisting of $`3^n`$ time-steps; with the initial condition given by the position of maximum overlap at $`t=0`$, as stated in Eq. (3), there will be no overlapping line segments of the two $`n`$-th generation sets for all odd values of $`t`$ and the frequency of each overlap magnitude, except the maximum, will be only half of the value given by Eq. (26). For large generation indices the asymptotic form of the binomial distribution is given by the continuous normal approximation , but it never acquires the form of a power law. The difference in the results of Ref.  and this paper is apparently due to the difference in the nature of the shifting process which is continuous in the former and discrete in the latter (with the size of each discrete step being equal to the length of the line segment in the finite generation). The authors of Ref.  also report that their result is valid for all types of Cantor sets and in fractals of higher dimensions, e.g., in the case of two overlapping Sierpinsky carpets. Though the discrete forms of these cases are yet to be studied, it has been reported in  that for two spanning clusters at the percolation threshold on a square lattice – where each cluster is a random fractal embedded in two dimensions – the overlap magnitudes follow a normal distribution.

Finally we consider a variant of the Chakrabarti-Stinchcombe model defined as the $`n`$-th generation of the Cantor set overlapping on its complement in the unit line segment; the complement of the $`n`$-th generation set is obtained by replacing each line segment (of length $`1/3^n`$) in the latter by an empty segment and each empty segment by a line segment. The overlap magnitudes in this variant model are given by $`Y_n=2^n2^k`$, $`k=0,\mathrm{},n`$. The time-series of overlaps can be directly derived from Eq. (12) by replacing each overlap magnitude $`2^{nk}`$ in the time-series of the original model with an overlap magnitude $`2^n2^{nk}`$. Consequently the frequency distribution of overlap magnitudes is given by $`\mathrm{Nr}\left(2^n2^k\right)=2^{nk}\left(\begin{array}{c}n\\ k\end{array}\right)`$. The variant appears to be more realistic than the original model since each of the two parts of a fractured rock is complementary to the other. However, in both cases the frequency of overlap magnitudes are found to follow binomial distributions.

## Acknowledgment

I am grateful to Bikas K. Chakrabarti and Robin B. Stinchcombe for their comments on the manuscript.


format: text

text:
# Scalable Quantum Computation in the Presence of Large Detected-Error Rates

## I Introduction

One of the most significant obstacles to realizing scalable quantum computation is physical noise that can quickly destroy the information contained in the computational state. It is now known that, provided the physical noise is sufficiently weak and local in space and time, scalable quantum computation is possible by means of fault-tolerant encodings of quantum information Shor (1996); Kitaev (1997); Knill and Laflamme (1996); Aharonov and Ben-Or (1996, 1999); Knill et al. (1998a, b); Gottesman (1998); Preskill (1998). Therefore, in studying a proposed physical implementation, a key question is whether the noise in the implementation is sufficiently low for scalability to be possible in principle. More importantly, is it feasible in practice? Answers to these questions depend significantly on the specific noise in the implementation, as well as on the way in which the quantum operations necessary for computation are realized. Nevertheless, the current consensus is that the error should be below an error rate of $`10^4`$ per operation Gottesman and Preskill (1999); Panel (2002). There have been numerous suggestions that $`10^4`$ is a pessimistic estimate of the error threshold (below which scalable quantum computation is possible) and certainly does not apply uniformly to all needed quantum operations Zalka (1996); Aharonov (2002); Dür and Briegel (2003); Steane (2003). Steane Steane (2003) makes it clear that thresholds are at least an order of magnitude higher under reasonable assumptions.

If the nature of the errors is constrained, then the maximum tolerable error rate can be much higher. A notable example of this is in efficient linear optics quantum computation (eLOQC Knill et al. (2001)) where, by design, the errors are dominated by unintentional but detected measurements of $`\sigma _z`$. For this error model, any error rate below $`0.5`$ is tolerable Knill et al. (2000); Knill (2001); not . That the tolerable error rate is so high is due to the great advantages of being able to detect errors before attempting correction. Here it is shown that these advantages also apply to the erasure error model. In this model, errors are detected but otherwise unknown. Another way of thinking about this error model is to imagine that the only error is loss of qubits, and whether or not a qubit is present can easily be determined without affecting the qubit’s state. The main result of this paper is that the maximum tolerable erasure error rate can be as high as $`0.292`$ per operation, given otherwise standard (though not necessarily practical) scalability assumptions. Interestingly, the only operations that have to meet this error probability are those needed for storing a qubit for one time-step, and Bell measurements. Other operations need have only a non-zero probability of success. If qubit memory is perfect, any probability of erasure below $`1/2`$ during a Bell measurement can be tolerated.

To establish a bound on threshold erasure error rates, the techniques used in Knill et al. (2001) are adapted to the general setting. Basically, all computational operations with error correction are combined into a single, very flexible teleportation step. The ideas that make this possible can be found in Steane (1999); Gottesman and Chuang (1999); Steane (2003, 2002); Steane and Ibinson (2003). Which operation is applied and the means for error correction are determined by which state is prepared for use in the teleportation step. This is where error detection can be used to advantage: The prepared state can be guaranteed to be error-free at the time it is brought into the computation. Specifically, one can configure the computation so that all states that may be needed are manufactured in large quantities at a state factory, with any states for which errors are detected being discarded before use. Although this is extremely inefficient, it means that for theoretical scalability, only errors in the implementation of the teleportation process itself are relevant.

The techniques described here reduce the problem of fault-tolerant quantum computation to the problem of preparing certain states with sufficiently low error rates. Assuming that storage and Bell measurement errors are small enough, this analysis shows that depolarizing error rates below $`0.1`$ per qubit are tolerable in the prepared states. How this affects the maximum tolerable depolarizing error at the level of individual quantum gates depends crucially on how the states can be prepared. For example, if there is a sufficiently fault-tolerant way of preparing the states with about 100 gates contributing to the final error in each qubit, then one would expect that a depolarizing error rate of $`10^3`$ can be tolerated, which is comparable to the thresholds shown in Steane (2003). There is hope that fault-tolerant state preparation can be accomplished with sufficiently low overhead, for example by adapting and generalizing protocols for entanglement purification Dür et al. (2003).

## II Error Models

Threshold error rates depend in subtle ways on the details of the error model adopted and how it is tied to the universal gate set used for computation. For pure detected-error models, each gate or other operation is error-free if no error is detected. In the erasure error model, a detected error implies complete loss of the state of the qubits involved. This is the model focused on in this paper. The error rate is determined by the probabilities of detected error for the various operations. For simplicity, all operations are assumed to take the same amount of time (“one time-step”) and are synchronously clocked on the qubits. It is assumed that classical computations are instantaneous and error-free, and that operations can be applied to any pair of qubits without communication delays. In other words, there is no communication or classical computation latency. Classical computation latency can be a problem if the algorithms for calculating the necessary error-correction steps depending on measurement outcomes are too complex. Quantum communication latency occurs when distant qubits need to be coupled. If classical computation latency is negligible, quantum communication latency can be significantly reduced by using teleportation methods Brennen et al. (2003).

It is assumed that the probabilities of detected error are strictly less than 1. The following detected-error probabilities will be used:

* $`e_m`$, the probability of detected error for the “memory” operation, which involves storing the state of a qubit for one time-step.
* $`e_b`$, the probability of detected error in implementing a Bell measurement on two qubits.

Interestingly, probabilities of detected errors for other operations do not affect the threshold if the methods described below are used. It is assumed that errors are independent between different operations.

A reasonable model for unknown errors that are not detected is the depolarizing error model. For a one-qubit operation, the state is randomly affected by $`\sigma _x`$, $`\sigma _y`$ or $`\sigma _z`$. The probability that one of the Pauli operators “occurs” as an error is the error probability. For two-qubit operations the interpretation of the model varies. One can assume that each of the possible non-identity Pauli products occurs with equal probability, but in this work only storage and Bell-measurement errors will play a significant role. For storage errors, let $`d_m`$ be the probability that one of the non-identity Pauli matrices occurs. For Bell-measurement errors, the effect is as if the correct measurement is physically applied, but sometimes a random incorrect answer is learned. Let $`d_b`$ be the probability of getting an incorrect answer in a Bell measurement.

## III Stabilizer Codes

Here is a brief review of the relevant stabilizer code theory. Stabilizer codes for qubits are defined as a common eigenspace of a set of commuting products of Pauli operators. Let $`n`$ be the length of the code, that is, the number of qubits used. It is convenient to specify a product of Pauli operators (“Pauli products”) by a pair of length-$`n`$ binary (row) vectors $`𝐬=(𝐚,𝐛)`$, $`𝐚=(a_i)_{i=1}^n,𝐛=(b_i)_{i=1}^n`$. For example, consider $`(a_1,a_2,a_3)=(1,0,1)`$ and $`(b_1,b_2,b_3)=(0,1,1)`$. For brevity, one can omit commas and use square brackets as follows: $`(a_1,a_2,a_3)=[a_1a_2a_3]=(1,0,1)=[101]`$. The product of Pauli operators associated with $`𝐬`$ is given by

$$P(𝐬)=P(𝐚,𝐛)=\underset{j=1}{\overset{n}{}}\{\begin{array}{cc}\sigma _{x}^{}{}_{}{}^{(𝗃)}\hfill & \text{if }a_j=1\text{ and }b_j=0\hfill \\ \sigma _{z}^{}{}_{}{}^{(𝗃)}\hfill & \text{if }a_j=0\text{ and }b_j=1\hfill \\ \sigma _{x}^{}{}_{}{}^{(𝗃)}\sigma _{z}^{}{}_{}{}^{(𝗃)}=i\sigma _{y}^{}{}_{}{}^{(𝗃)}\hfill & \text{if }a_j=1\text{ and }b_j=1\hfill \end{array}.$$
(1)
Here, parenthesized superscripts denote the label of the qubit on which the given operator acts. Let $`𝐭=(𝐜,𝐝)`$ be another pair of length-$`n`$ binary vectors. All computations involving vectors and matrices are performed modulo 2, with one exception pointed out below. $`P(𝐬)`$ commutes with $`P(𝐭)`$ if $`\mathrm{𝐚𝐝}^T\mathrm{𝐛𝐜}^T=0`$, and anticommutes otherwise. (Although the minus sign in the identity has no effect because arithmetic is modulo 2, it is retained for consistency with the theory of non-binary stabilizer codes.) Explicitly, $`P(𝐬)P(𝐭)=(1)^{\mathrm{𝐚𝐝}^T\mathrm{𝐛𝐜}^T}P(𝐭)P(𝐬)`$. One can consider pairs of $`n`$-dimensional row vectors such as $`𝐬`$ as $`2n`$-dimensional row vectors. To maintain the association with qubit positions, it is convenient to merge the two $`n`$-dimensional vectors. That is, by definition, $`𝐬=(𝐚,𝐛)=[a_1b_1a_2b_2\mathrm{}]`$. With the example above, one can write $`𝐬=[100111]`$. To make the association with Pauli matrices, the abbreviations $`I=00`$, $`X=10`$, $`Z=01`$ and $`Y=11`$ are convenient. Thus $`[100111]=[XZY]`$. Note the factor of $`i`$ in the Pauli operator associated with $`Y`$.

Let $`𝕊_l`$ and $`𝕊`$ be the $`2n\times 2n`$ block-diagonal matrices

$$𝕊_l=\left(\begin{array}{ccccc}0& 0& 0& 0& \mathrm{}\\ 1& 0& 0& 0& \mathrm{}\\ 0& 0& 0& 0& \mathrm{}\\ 0& 0& 1& 0& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right),𝕊=𝕊_l𝕊_l^T=\left(\begin{array}{ccccc}0& 1& 0& 0& \mathrm{}\\ 1& 0& 0& 0& \mathrm{}\\ 0& 0& 0& 1& \mathrm{}\\ 0& 0& 1& 0& \mathrm{}\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\end{array}\right).$$
(2)
Then $`P(𝐬)`$ commutes with $`P(𝐭)`$ if $`𝐬𝕊𝐭^T=0`$ and anticommutes otherwise. Specifically,

$$P(𝐬)P(𝐭)=(1)^{𝐬𝕊𝐭^T}P(𝐭)P(𝐬).$$
(3)
More generally, the multiplication rule is

$$P(𝐬)P(𝐭)=(1)^{𝐬𝕊_l𝐭^T}P(𝐬+𝐭).$$
(4)
Consider $`l`$ independent $`2n`$-dimensional binary vectors $`𝐬_i`$ describing Pauli products as explained above. Let $`Q`$ be the matrix whose rows are the $`𝐬_i`$. If the $`P(𝐬_i)`$ commute, then the state space of $`n`$ qubits decomposes into $`2^l`$ disjoint common eigenspaces of the $`P(𝐬_i)`$, each of dimension $`2^{nl}`$. The eigenspaces are characterized by their syndromes, that is, by the eigenvalues of the $`P(𝐬_i)`$. To standardize the eigenvalues in terms of binary vectors requires introducing the function $`\nu (𝐬)=i^{𝐬𝕊_l𝐬^T}`$, where expressions in the exponent of $`i`$ are not reduced modulo $`2`$ (they can be reduced modulo $`4`$). Note that $`𝐬𝕊_l𝐬^T`$ counts the number of $`Y`$’s in $`𝐬`$, and each $`Y`$ contributes factors of $`i`$ to the eigenvalues. With this definition, $`\nu ([X])=\nu ([Z])=1`$, and $`\nu ([Y])=i`$. Each syndrome is described by an $`l`$-dimensional binary (row) vector $`𝐞`$ and relates to the eigenvalues as follows: If $`|||\psi `$ is in the eigenspace with syndrome $`𝐞=(e_i)_{i=1}^l`$, then $`P(𝐬_i)|||\psi =(1)^{e_i}\nu (𝐬_i)|||\psi `$. If $`𝐬`$ is in the row span of $`Q`$, that is, $`𝐬=𝐱Q`$, then the eigenvalue of $`P(𝐬)`$ for this syndrome is expressible as

$`P(𝐬)|||\psi `$ $`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}(1)^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}{\displaystyle \underset{i}{}}\nu (𝐬_i)^{x_i}|||\psi `$ (5)
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}(1)^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}i^{_ix_i𝐬_i𝕊_l𝐬_i^T}|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}(1)^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}i^{_ix_i𝐬_i𝕊_l𝐬_i^T}i^{𝐬𝕊_l𝐬^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}(1)^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}i^{_ix_ix_i𝐬_i𝕊_l𝐬_i^T}i^{_{ij}x_ix_j𝐬_i𝕊_l𝐬_j^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}(1)^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}i^{_{ij}x_ix_j𝐬_i𝕊_l𝐬_j^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}i^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}i^{_{i>j}x_ix_j𝐬_i𝕊_l𝐬_j^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}i^{_{i<j}x_ix_j𝐬_i𝕊_l𝐬_j^T}i^{_{i>j}x_ix_j𝐬_i𝕊_l𝐬_j^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}i^{_{i<j}x_ix_j𝐬_i(𝕊_l𝕊_l^T)𝐬_j^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}i^{_{i<j}x_ix_j𝐬_i𝕊𝐬_j^T}\nu (𝐬)|||\psi `$
$`=`$ $`(1)^{\mathrm{𝐱𝐞}^T}i^{𝐱\text{ut}(Q𝕊Q^T)𝐱^T}\nu (𝐬)|||\psi ,`$
where $`\text{ut}(Y)`$ is the strictly upper-triangular part of $`Y`$. The projection operator onto the eigenspace with syndrome $`𝐞`$ is given by

$$\mathrm{\Pi }(Q,𝐞)=\underset{i}{}\frac{1}{2}(1\mathrm{l}+(1)^{e_i}\overline{\nu }(𝐬_i)P(𝐬_i)).$$
(6)
If it is necessary to emphasize the dependence of the syndrome on $`Q`$, it will be referred to as the $`Q`$-syndrome. The eigenspaces are the stabilizer codes associated with $`Q`$. For $`𝐬`$ in the row span of $`Q`$, $`P(𝐬)`$ stabilizes the states of these stabilizer codes up to a phase. Such Pauli products form the stabilizer of the codes. Write $`\mathrm{\Pi }(Q)=\mathrm{\Pi }(Q,0)`$ and consider this to be the fundamental stabilizer code associated with $`Q`$. The word “fundamental” will be omitted whenever possible. Furthermore, $`\mathrm{\Pi }(Q)`$ is used to refer both to the projection operator and to the code as a subspace: The intended meaning will be clear from the context.

It is important to understand the effects of Pauli products on states in a stabilizer code. One can verify that $`P(𝐬)\mathrm{\Pi }(Q,𝐞)P(𝐬)^{}=\mathrm{\Pi }(Q,𝐞^{})`$, where $`𝐞^{}=𝐞+𝐬𝕊Q^T`$. This implies that if $`|||\psi `$ has syndrome $`𝐞`$, so that $`\mathrm{\Pi }(Q,𝐞)|||\psi =|||\psi `$, then $`P(𝐬)|||\psi `$ has syndrome $`𝐞+𝐬𝕊Q^T`$. To see this, compute $`P(𝐬)|||\psi =P(𝐬)\mathrm{\Pi }(Q,𝐞)|||\psi =\mathrm{\Pi }(Q,𝐞+𝐬𝕊Q^T)P(𝐬)|||\psi `$.

Let $`C=C(Q)`$ be the row span of $`Q`$. $`C`$ is a classical binary code. If $`Q^{}`$ has the same row span as $`Q`$, then $`C(Q^{})=C(Q)`$, and the set of stabilizer codes associated with $`Q^{}`$ is the same as that associated with $`Q`$. For understanding the error-correcting properties of stabilizer codes, one has to look at $`C^{}`$, the set of vectors $`𝐱`$ such that $`𝐱𝕊Q^T=0`$, or, equivalently, such that $`P(𝐱)`$ commutes with all of the $`P(𝐬_𝐢)`$. For $`𝐭C^{}`$ but not in $`C`$, $`P(𝐭)`$ preserves each stabilizer code associated with $`Q`$ but acts nontrivially in each code. Consequently, the quantum minimum distance of these codes is the minimum distance of the set $`C^{}C`$. Here, minimum distance is defined as the weight of the smallest-weight (non-zero) vector in $`C^{}C`$. The weight of $`𝐱`$ is the number of qubits on which $`P(𝐱)`$ acts nontrivially.

When working with stabilizer codes and syndrome measurements, it is helpful to be able to determine the new stabilizer of a state after making a syndrome measurement for a different code. Let $`Q`$ be as above. Suppose that the initial state $`|||\psi `$ is an arbitrary state of $`\mathrm{\Pi }(Q,𝐞)`$ and that one measures the $`R`$-syndrome with outcome $`𝐟`$. What Pauli products are guaranteed to stabilize the resulting state $`|||\varphi `$? $`P(𝐫)`$ stabilizes $`|||\varphi `$ if $`𝐫`$ is in $`C(R)`$ or in $`C(Q)C(R)^{}`$. The latter set consists of the Pauli operators guaranteed to stabilize the initial state that commute with the measurement. In general, the only Pauli products guaranteed to stabilize $`|||\varphi `$ are products of the above. One can construct an independent set of such products from $`Q`$ and $`R`$ by the usual linear-algebra methods modulo 2. The eigenvalues can be determined using the formulas introduced earlier.

It is not the case that minimum distance completely determines whether $`\mathrm{\Pi }(Q)`$ is a stabilizer code with good error-correction properties for typical independent error models. That is, provided that the number of low-weight elements of $`C^{}C`$ is sufficiently small, it is still possible to correct most errors. Suppose that $`|||\psi `$ is encoded as $`|||\psi __𝖫`$ in $`\mathrm{\Pi }(Q)`$. For any error model, the effect of the errors on $`|||\psi __𝖫`$ can be thought of as a probabilistic mixture of the states $`A_k|||\psi __𝖫`$, where $`(A_k)`$ are the operators in the operator sum representation of the errors and satisfy $`_kA_k^{}A_k=1\mathrm{l}`$. The probability of $`A_k|||\psi __𝖫`$ is $`{}_{}{}^{𝖫}\psi |||A_k^{}A_k|||\psi __𝖫`$. Because Pauli products form a complete operator basis, $`A_k=_𝐬\alpha _{k𝐬}P(𝐬)`$. To correct the errors one can measure the $`Q`$-syndrome of the noisy state. Suppose that the measured syndrome is $`𝐞`$. Then the state $`A_k|||\psi __𝖫`$ is projected to $`_{𝐬:𝐬𝕊Q^T=𝐞}\alpha _{k𝐬}P(𝐬)|||\psi __𝖫`$. The sum is over a set $`C^{}+𝐬_0`$. A good code for the error model has the property that, with high probability, all dominant amplitudes among the $`\alpha _{k𝐬}`$ satisfy the condition that $`𝐬`$ is in the same set $`C+𝐬^{}C^{}+𝐬_0`$, independent of which $`A_k`$ occurred. If that is true, then a decoding algorithm can determine the dominant amplitude’s coset $`C+𝐬^{}`$ and apply $`P(𝐬^{})^{}`$ to restore $`|||\psi __𝖫`$. A practical code also has the property that there is an efficient decoding algorithm that has a high probability of successfully inferring $`C+𝐬^{}`$.

The discussion of the previous paragraph assumes that nothing is known about the error locations. Suppose that it is known that the errors occurred on a given set $`S`$ of $`m`$ qubits. If the errors are erasures, without loss of generality, reset the erased qubit to $`0`$ (replacing it with a fresh qubit if necessary). Suppose that after this, the measured syndrome is $`𝐞`$. The possible Pauli products appearing in the new state $`|||\varphi =_{𝐬:𝐬𝕊Q^T=𝐞}\alpha _{k𝐬}P(𝐬)|||\psi __𝖫`$ satisfy the condition that $`𝐬`$ has non-zero entries only for qubits in $`S`$ and $`𝐬C^{}+𝐬_\mathrm{𝟎}`$ for some $`𝐬_\mathrm{𝟎}`$. Suppose that $`C^{}C`$ contains no $`𝐬`$ with non-zero entries only for qubits in $`S`$. Then all $`𝐬`$ appearing in the sum for $`|||\varphi `$ are in the same set $`C+𝐬^{}`$ for some $`𝐬^{}`$. Applying $`P(𝐬^{})`$ corrects the error. Note that a suitable $`𝐬^{}`$ can be computed efficiently given $`𝐞`$ and $`S`$: It suffices to solve $`𝐬𝕊Q^T=e`$ subject to the condition that $`𝐬`$ is zero for positions associated with qubits outside of $`S`$. This is a set of linear equations modulo $`2`$.

Because of the argument of the previous paragraph, an erasure code for $`S`$ is defined as a code $`C`$ such that $`C^{}C`$ contains no $`𝐬`$ with nonzero entries only for qubits in $`S`$. It follows that a code of minimum distance $`d`$ is an erasure code for all $`S`$ of cardinality at most $`d1`$. A useful property of erasure codes when all errors are detected is that if an error combination cannot be corrected, then this is known. This is because given $`S`$ it is possible to determine whether the code is an erasure code for $`S`$. If an error combination cannot be corrected, this becomes a detected error for the encoded information. In particular, for the erasure error model, the encoded information is also subject to erasure errors (hopefully at a much lower rate). In other words, the error model is preserved by encoding.

In addition to being able to correct errors with high probability, a good stabilizer code should be able to encode a large number of qubits. For the present purposes, analysis is simplified by encoding one qubit at a time. However, efficiency can be improved substantially by encoding more and the basic techniques that are used are still applicable. Let $`Q`$ be a matrix with $`n1`$ rows defining a two-dimensional stabilizer code. A qubit can be encoded in a way consistent with the stabilizer formalism by choosing two row vectors $`𝐭_x`$ and $`𝐭_z`$ with the property that $`𝐭_x𝕊Q^T=\mathrm{𝟎}`$, $`𝐭_z𝕊Q^T=\mathrm{𝟎}`$ and $`𝐭_x𝕊𝐭_z^T=1`$. Then $`P(𝐭_x)`$ and $`P(𝐭_z)`$ relate to each other as $`X`$ and $`Z`$ and can therefore serve as encoded $`X`$ and $`Z`$ observables. Note that if $`Q`$ is extended by $`𝐭_x`$, $`𝐭_z`$ or $`𝐭_y=𝐭_x+𝐭_z`$, then one-dimensional stabilizer codes are obtained whose states are encoded $`X`$, $`Z`$ and $`Y`$ eigenstates.

## IV Error Correction by Teleportation

Let $`Q`$ be the $`l\times 2n`$ matrix defining a stabilizer code for encoding $`k=nl`$ qubits with good error-correction properties. Consider $`n`$ qubits carrying a state encoded in the stabilizer code for $`Q`$ that has been affected by errors. An effective way of correcting errors in this state is to teleport each of the qubits using $`n`$ pairs of qubits prepared as follows: First place each pair in the standard Bell state $`(|||00+|||11)/\sqrt{2}`$. Use a $`Q`$-syndrome measurement on the $`n`$ second members of each pair to project them into one of the stabilizer codes associated with $`Q`$. Finally, apply identical Pauli matrices to both members of pairs in such a way as to reset the syndrome to $`0`$. The result is that the $`n`$ pairs are in a state where the first and second members are in a maximally entangled state of the stabilizer code for $`Q`$. Teleportation in the absence of errors transfers the state of the input qubits to the output qubits. In the presence of errors, the Bell measurements used for teleportation reveal syndrome information that can be used to correct some errors. The remainder of this section is dedicated to establishing the details of this procedure.

The standard quantum teleportation protocol begins with an arbitrary state $`|||\psi __\mathrm{𝟣}`$ in qubit $`\mathrm{𝟣}`$ and the Bell state $`(|||00_{_{\mathrm{𝟤𝟥}}}+|||11_{_{\mathrm{𝟤𝟥}}})/\sqrt{2}`$ on qubits $`\mathrm{𝟤},\mathrm{𝟥}`$. The initial state can be viewed as $`|||\psi `$ encoded in the stabilizer code generated by $`𝐛_1=[001010]=[IXX]`$ and $`𝐛_2=[000101]=[IZZ]`$. Let $`B^{(\mathrm{𝟤𝟥})}`$ be the matrix whose rows are the $`𝐛_i`$. The stabilizer consists of the Pauli products $`1\mathrm{l},\sigma _{x}^{}{}_{}{}^{(\mathrm{𝟤})}\sigma _{x}^{}{}_{}{}^{(\mathrm{𝟥})},\sigma _{y}^{}{}_{}{}^{(\mathrm{𝟤})}\sigma _{y}^{}{}_{}{}^{(\mathrm{𝟥})}`$ and $`\sigma _{z}^{}{}_{}{}^{(\mathrm{𝟤})}\sigma _{z}^{}{}_{}{}^{(\mathrm{𝟥})}`$. To teleport, one makes a Bell-basis measurement on the first two qubits. This is equivalent to making a $`B^{(\mathrm{𝟣𝟤})}`$-syndrome measurement, where $`B^{(\mathrm{𝟣𝟤})}`$ has as rows $`[101000]=[XXI]`$ and $`[010100]=[ZZI]`$. This is identical to $`B^{(\mathrm{𝟤𝟥})}`$ with qubits $`\mathrm{𝟤},\mathrm{𝟥}`$ exchanged for qubits $`\mathrm{𝟣},\mathrm{𝟤}`$. Depending on the syndrome $`𝐞`$ that results from the measurement, one applies correcting Pauli matrices to qubit $`\mathrm{𝟥}`$ to restore $`|||\psi `$ in qubit $`\mathrm{𝟥}`$.

One way to determine the required corrections is to follow the procedure for $`|||\psi __\mathrm{𝟣}`$ being eigenstates of $`\sigma _x`$ and $`\sigma _z`$ and to check which Pauli operators stabilize the final state and what their eigenvalues are. Formally, start with a one-dimensional stabilizer code generated by $`B([ab])`$ whose rows are $`[001010],[000101],[ab0000]`$. Define $`𝐱=[ab]`$. The initial syndrome and $`𝐱`$ determine the input state on the first qubit. Suppose that the initial state has $`B(𝐱)`$-syndrome $`𝐞=[00e]`$. Measure the $`B^{(\mathrm{𝟣𝟤})}`$-syndrome, obtaining syndrome $`𝐟=[f_1f_2]`$. Among the stabilizers of the new state is $`P(𝐬)`$ with $`𝐬=a[001010]+b[000101]+[ab0000]+a[101000]+b[010100]=[0000ab]`$. The first three terms are in the row span of $`B(𝐱)`$ and yield a Pauli product commuting with the measurement. The last two terms are in the row span of $`B^{(\mathrm{𝟣𝟤})}`$. Thus the new state has the same stabilizer on qubit $`\mathrm{𝟥}`$ as the original state had on qubit $`\mathrm{𝟣}`$. However, the eigenvalue may be different. It is given by $`(1)^{e+𝐟[ab]^T}i^{ab}`$ (the exponent of $`i`$ is the product of $`a`$ and $`b`$.) To restore the original eigenvalue, it suffices to apply $`P(𝐟𝕊)`$ to qubit $`\mathrm{𝟥}`$.

The protocol for error correction by teleportation has $`n`$ qubits in a state that initially was stabilized by $`Q`$ with syndrome $`\mathrm{𝟎}`$. The goal is to measure the $`Q`$-syndrome of the noisy state $`|||\psi `$ and obtain a corrected state at the teleportation destination. Label the $`n`$ qubits by $`\mathrm{𝟣},\mathrm{},𝗇`$. Adjoin $`2n`$ qubits labeled $`𝗇+\mathrm{𝟣},\mathrm{},\mathrm{𝟥}𝗇`$. These qubits are prepared as follows: Initialize qubits $`𝗇+𝗄`$ and $`\mathrm{𝟤}𝗇+𝗄`$ in the Bell state (stabilizer $`B^{((𝗇+𝗄)(\mathrm{𝟤}𝗇+𝗄))}`$). Measure the $`Q`$-syndrome on qubits $`\mathrm{𝟤}𝗇+\mathrm{𝟣},\mathrm{},\mathrm{𝟥}𝗇`$. Make this syndrome identically $`0`$ by applying a Pauli product to these qubits after the measurement. Apply the same Pauli product to the corresponding qubits $`𝗇+\mathrm{𝟣},\mathrm{},\mathrm{𝟤}𝗇`$. The state of qubits $`𝗇+\mathrm{𝟣},\mathrm{},\mathrm{𝟥}𝗇`$ is stabilized by $`[\mathrm{𝟎}𝐬_i]`$ for the rows $`𝐬_i`$ of $`Q`$ and by $`[\mathrm{𝐫𝐫}]`$ for $`𝗋C(Q)^{}`$. (Here, the square bracket notation has been adapted to denote concatenation of row vectors.) Note that because $`C(Q)C(Q)^{}`$, the stabilizer also contains $`[𝐬_i\mathrm{𝟎}]`$, so an equivalent state could have been prepared by measuring the qubits $`𝗇+\mathrm{𝟣},\mathrm{},\mathrm{𝟤}𝗇`$. Finally, teleport qubits $`𝗆`$ to $`\mathrm{𝟤}𝗇+𝗆`$ using the Bell measurement of qubits $`𝗆`$ and $`𝗇+𝗆`$. The claim is that the Bell measurement results $`𝐟_m`$ are constrained in a way that determines the $`Q`$-syndrome of the input state. The output state on qubits $`\mathrm{𝟤}𝗇+\mathrm{𝟣},\mathrm{}\mathrm{𝟥}𝗇`$ is the result obtained after measuring the $`Q`$-syndrome of the input state on qubits $`\mathrm{𝟣},\mathrm{},𝗇`$. Let $`P(𝐠)`$ be the Pauli-product correction applied to qubits $`\mathrm{𝟤}𝗇+\mathrm{𝟣},\mathrm{},\mathrm{𝟥}𝗇`$ as part of the protocol. The proof of the claim is presented pictorially in Fig. IV. It shows that the $`Q`$-syndrome $`𝐞`$ is determined by the measurement outcomes according to $`𝐞=𝐠𝕊Q^T`$.

FIG. 1: Teleporting with an encoded entangled state is equivalent to a syndrome measurement. The principle is as explained in Gottesman and Chuang (1999). In this case, a stabilizer projection on the destination qubits before teleportation is equivalent to a projection after teleportation, where the syndrome associated with the projection is modified by the correction Pauli product used during teleportation. The equivalence is shown with a transformation of quantum networks in three steps. The gray lines are the time lines of $`n`$ qubits. The boxes denote various operations. The Bell-state preparation on corresponding pairs of qubits in two sets of $`n`$ qubits is depicted with a box angled to the right and labeled “Bell”. The prepared state is the state obtained by projecting the destination qubits with $`\mathrm{\Pi }(Q,0)`$. Projection operators are shown with boxes angled both ways with the operator written in the box. To bypass the problem that a projection operator cannot be applied with certainty, the Bell-state measurement followed by the projection may be implemented by a suitable stabilizer code encoding procedure or the procedure described in the text. The Bell-state measurement is depicted with a box angled to the left. The measurement outcome is carried by the darker, classical line exiting at the bottom of the box. The Pauli-product correction operator is controlled by the classical line. The conclusion is that the $`Q`$-syndrome can be determined from the Pauli-product correction $`P(𝐠)`$ by computing $`𝐠𝕊Q^T`$.

It does not matter which projection $`\mathrm{\Pi }(Q,𝐭)`$ is applied after the Bell-state preparation. Provided $`𝐭`$ is known, this affects only the deduced $`Q`$-syndrome for the input state, which is now computed as $`𝐠𝕊Q^T+𝐭`$. As a result, one can prepare the state needed for teleportation by measuring the $`Q`$-syndrome of the destination qubits before teleporting, and recording the outcome without compensating for it.

To use the above procedure for error correction, it suffices to modify the Pauli products needed for completing the teleportation step by multiplying with the Pauli products that are needed to compensate for error according to the syndrome. Suppose that the quantum information of interest was encoded with syndrome $`\mathrm{𝟎}`$ before errors. Suppose that the true error is (close to) $`P(𝐝_t)`$ If the Bell measurements are error-free, then the syndrome after errors is $`𝐠𝕊Q^T`$ and the optimal correction can be determined from this, usually by finding a low weight $`𝐡`$ such that $`𝐡𝕊Q^T=𝐠𝕊Q^T`$. For good codes, $`𝐡=𝐝_t`$ with high probability. Suppose that there are errors in the Bell measurement and instead of the error-free $`𝐠`$, $`𝐠^{}`$ is used for correction. Assuming independence, the errors are still local, and one expects $`𝐝=𝐠^{}𝐠`$ to have low weight. Because the teleportation correction is incorrect, an additional error $`P(𝐝)`$ has been introduced. That is, the new error is $`P(𝐝+𝐝_t)`$. Fortunately, the computed syndrome $`𝐠^{}𝕊Q^T`$ reflects this error, and the inferred correction will work provided that the code is good for the combination of the pre-Bell-measurement error process and the errors in the Bell measurement.

It appears that erasure errors cause a problem because for cases where such errors occurred the Bell measurement outcomes are unknown. The argument of the previous paragraph shows that the way in which the teleportation correction is “filled in” does not affect the outcome of the procedure. The correct state is reproduced at the teleportation output in each case.

It is worth making a few simplifications to reduce the gate overhead. One is to omit the Pauli products needed for teleportation and error correction by using classical bookkeeping to keep track of the current syndrome and the current “Pauli frame” for the encoded information. One can reduce the bookkeeping problem by deferring the Pauli correction (for both teleportation and errors) to the state prepared for the next teleportation operation.

## V Combining Operations with Error Correction

Operations can now be integrated into the error-correction process using the techniques described in Gottesman and Chuang (1999). The basic idea is to apply the desired encoded operation to the destination qubits of the entangled state (or states) to be used for teleportation. If the operation is in the so-called Clifford group, the teleportation protocol results in the desired operation being applied, except that the Pauli products needed to correct the state are modified. To achieve universality, an additional operation that has the property of conjugating Pauli products to elements of the Clifford group is required. One such operation is the $`45^{}`$ rotation $`e^{i\sigma _x\pi /8}`$. Again, it is applied in encoded form to the destination qubits of the prepared state used for teleportation. After teleportation, the necessary correction may be a Clifford-group element not of the form of a Pauli product. If that is the case, this Clifford-group element is applied in the next teleportation step.

Note that for applying Clifford-group elements such as the controlled-not, the teleportation step has to act on two encoded qubits and the error-correction aspects of the teleportation step for the two qubits have to be implemented on both at the same time.

## VI Measurement

The same teleportation step used for computation can also be used for measurement, except that in this case the destination qubits are redundant. That is, if one prepares an encoded state on the source qubits with the encoded qubits in logical zero, the Bell measurement will reveal not just the syndrome of the code, but also the measurement outcome. Errors can be classically corrected to reveal the true measurement outcome.

## VII Thresholds

The sequential implementation of the scheme in the context of a computation is shown in Fig. VII.

FIG. 2: Sequence of computational steps. Each step consists of a teleportation with integrated operations and error correction. The steps required for correction determine the prepared state used in the next step. That is, a state that has the appropriate operations pre-applied to the destination qubit is used. Any such state is assumed to be available at the “state preparation factory” at the next step. Zero communication and classical computation delays are assumed. The prepared states have been checked for errors, with no errors detected just before it is used. Errors in the computation are therefore due only to the Bell measurement and the storage time for the destination qubits used during the Bell measurement.

In order to obtain a lower bound on the erasure error threshold and discussing the depolarizing error threshold, observe that the efficiency with which the needed states are prepared has no effect on the threshold. It is necessary only to determine for what error rates it is possible to make the error per step in the encoded (logical) qubits arbitrarily small. Consider the erasure error model. In this case, the error model for the logical qubits is also independent erasures. If the rate of erasures is sufficiently small, then according to the known threshold theorems, we can use the logical qubits to efficiently implement arbitrarily accurate quantum computations. Efficiency in these theorems requires only that the cost of each elementary step of the computation is bounded by a constant independent of the length of the computation. Here, this constant depends on the length of the code needed to achieve an encoded error below the general threshold, for which there are known lower bounds. Here, the effort required to prepare the states for the teleportation steps only adds to the constant. In particular, the states can be prepared naively, by attempting to implement a quantum network that prepares them, and discarding any unsuccessful attempts. It is known that any one-qubit state encoded in a stabilizer code of length $`n`$ requires at most $`O(n^2)`$ quantum gates Cleve and Gottesman (1997). Because each succeeds only with probability $`s<1`$, the expected number of attempts for each state to be prepared is bounded by $`e^{O(n^2)}`$. Although this is superexponential, it contributes “only” a constant overhead to the implementation of each encoded operation. A similar argument can be made for the depolarizing error model, except that the final analysis may be affected by the residual (undetected) errors in the prepared states. In conclusion, it is possible to invoke the general threshold theorems to show that state preparation overhead can be ignored for the purpose of establishing lower bounds on the threshold by the methods used here. Nevertheless, a self-contained proof not relying on the general threshold theorems of scalability is given in Sect. VIII.

Suppose that we use a one-qubit erasure code for which the probability of an uncorrectable erasure is $`f(e)`$, given that the probability of erasure of each qubit is $`e`$. The error probability of a quantum computation using the scheme of Fig. VII is determined by the probability that the Pauli product correction to restore the state in the destination qubits is incorrectly inferred. By the time this correction is inferred, the destination qubits that now carry the desired state are of course already corrupted. However, any errors that have occurred are removed in the next step and therefore ignored in this analysis. The probability of detected error is given by $`e_m+(1e_m)e_b`$. The first term comes from detected error in the storage period of the destination qubits. The second comes from the Bell measurement, which is applied only to qubits with no previously detected error. The probability of erasure of the encoded qubit is therefore $`f(e_m+(1e_m)e_b)`$. Because the prepared states are error-free at the instant when they are used, this erasure probability also applies to each qubit independently in teleported two-qubit operations. It remains to determine for what error rates there exist one-qubit erasure stabilizer codes with arbitrarily small probability of encoded erasure. If the supremum of these error rates is $`e_{\text{max}}`$, then the threshold for $`e_m`$ and $`e_b`$ is determined by the curve $`e_{\text{max}}=e_m+(1e_m)e_b`$. The value of $`e_{\text{max}}`$ is determined in Bennett et al. (1997) and is given by $`e_{\text{max}}=1/2`$. Fig. VII shows the region for $`e_m`$ and $`e_b`$ where scalable computation for the detected-error model is possible.

FIG. 3: Region for which scalable computation for the detected-error model is possible. Tolerable error rates are in the gray region, strictly below the upper boundary. If memory and Bell measurement error are equal, then any error-rate below $`0.292`$ is tolerable. The point on the boundary corresponding to this value is shown. If memory errors are negligible, then Bell-measurement error rates close to $`1/2`$ are tolerable.

## VIII State-Preparation Inefficiency

It is possible to prove that state preparation can be done with polynomial overhead directly instead of relying on the general threshold theorems. This is done here to make the paper more self contained and to show that two levels of concatenation suffice for the erasure error model. Let $`n`$ be the final length of the (concatenated) code for each logical qubit. The code is constructed by concatenating two erasure codes of length $`l_1`$ and $`l_2`$ with $`l_1l_2=n`$ and $`l_1<\sqrt{n}`$. State preparation through the first level of encoding is handled by the naive method of repeated attempts. At the second level of encoding, the methods of the previous sections are used to improve the probability of successful state preparation.

To see that one level of encoding with the naive state-preparation method is insufficient, consider the following: The goal is to implement a computation of $`N`$ elementary operations with polynomial overhead. In order for the computation to have a probability $`1ϵ`$ of success with logical qubits and no further error correction, the logical qubits must be subject to an error rate of $`ϵ/N`$ per operation. (Erasure errors add probabilistically.) Given that $`e_m`$ and $`e_b`$ are in the scalability region, the error rate as a function of code length $`n`$ for the best codes goes as $`e^{cn}`$ (asymptotically) for some constant $`c`$ depending on $`e_m`$ and $`e_b`$. One should therefore choose $`n>\mathrm{ln}(N/ϵ)/c`$. Typically, the state-preparation networks for these codes have at least $`c^{}n^2`$ gates for some constant $`c^{}>0`$. The naive state preparation therefore requires resources of order $`e^{c^{\prime \prime }n^2}`$. Substituting the lower bound for $`n`$ gives a superpolynomial function of $`N/ϵ`$.

To eliminate the superpolynomial overhead, choose a first level code that reduces the error rate to $`e^{cl_1}`$. Choose a second level code that can correct any combination of at most $`l_2/6`$ erasures (such stabilizer codes exist by using random coding Bennett et al. (1996); Calderbank et al. (1997)). The concatenation of the two codes results in logical qubits with an error rate bounded by $`\left(\genfrac{}{}{0pt}{}{l_2}{l_2/6}\right)(e^{cl_1})^{l_2/6}e^{c^{}n}`$ for some constant $`c^{}>0`$ and sufficiently large $`l_1,l_2`$. Choose $`n>\mathrm{ln}(N/ϵ)/c^{}`$. The naive state-preparation method for computations with qubits encoded in the first-level code requires an overhead of $`e^{c^{\prime \prime }l_1^2}e^{dn}`$ for some constant $`d`$. Computations at the next level are implemented using the teleportation techniques discussed above. The probability of success of one step is at least $`1e^{c^{\prime \prime \prime }l_1}`$ for some constant $`c^{\prime \prime \prime }`$ (different from $`c^{}`$ because a step involves both storage and Bell measurements). The probability of success of a state-preparation network for states needed by the second level code is at least $`1c^{}l_2^2e^{c^{\prime \prime \prime }l_1}>1/2`$ for sufficiently large $`n`$. The total overhead for the concatenated state preparation is bounded by $`2c^{}l_2^2e^{dn}<e^{d^{}\mathrm{ln}(N/ϵ)}=\mathrm{poly}(N/ϵ)`$.

An obvious way to improve the efficiency of this state-preparation scheme is to choose the size of the first level code to better balance the overheads between the two levels. In particular, the first level code need have length only of order $`\mathrm{log}(n)`$ for the probability of success of the second-level state preparation to exceed a constant. This reduces the overhead to polylogarithmic in $`N/ϵ`$, comparable to overheads in the standard threshold theorems based on concatenation.

## IX Application to other error models

The techniques discussed above can be used with any error model provided that it is possible to prepare the requisite state such that the final error in the state is sufficiently well controlled. For example, consider the depolarizing error model. Here, there are probabilities for complete, undetected depolarization for the various operations. The probability of a depolarizing error is the probability that some non-identity Pauli operator affects a qubit. Suppose that the probability of a depolarizing error for a memory operation is $`d_m`$ and that the probability of a random incorrect Bell measurement outcome is $`d_b`$. Suppose also that encoded states can be prepared such that they are as intended except for independent depolarizing errors on each qubit with probability of error $`d_p`$. Assume also that this probability does not depend on the code used in a family of codes of interest. Such a family of codes could be the bipartite graph codes for which local purification is possible using the techniques of Dür et al. (2003). In this case, the error in the destination qubits from preparation is propagated forward to the next teleportation step. An upper bound on the error rate that the code needs to handle is given by $`e_t=2d_p+d_m+d_b`$. If one computes the error rate exactly, taking into consideration canceling errors, one gets

$$1e_t=\begin{array}{ccc}& (1d_p)(1d_m)(1d_p)(1d_b)\hfill & \text{(no error anywhere)}\hfill \\ +& d_p(d_m/3)(1d_p)(1d_b)\hfill & \text{(storage error cancels preparation error}\hfill \\ & & \text{on original qubit)}\hfill \\ +& (1d_p)(1d_m)d_p(d_b/3)\hfill & \text{(Bell-measurement error compensates}\hfill \\ & & \text{for preparation error in}\hfill \\ & & \text{newly prepared qubit)}\hfill \\ +& (d_p(1d_m/3)+(1d_p)d_m)(1d_p)(d_b/3)\hfill & \text{(Bell-measurement error compensates}\hfill \\ & & \text{for total error on the original qubit)}\hfill \end{array}$$
(7)
If the supremum of the error rates for which the family of codes in question has arbitrarily small error probability for the encoded qubit is $`e_{\text{max}}`$, then a bound on the threshold boundary is determined by $`e_{\text{max}}=e_t`$. The currently best lower bound on $`e_{\text{max}}`$ for stabilizer codes is $`e_{\text{max}}0.19`$ DiVincenzo et al. (1998). According to this estimate, the region for which scalable computation is possible given balanced $`d_m=d_b`$ is shown in Fig. IX.

FIG. 4: Region for which scalable computation for depolarizing errors is possible. Tolerable error rates are in the gray region, strictly below the upper boundary. For small memory and Bell-measurement error rates, preparation errors close to $`0.1`$ per qubit can be tolerated. Since preparation errors are likely to dominate because of the higher number of operations required to deliver the state, this is the regime that is likely to be relevant.

## X Discussion

The work reported here shows that the maximum tolerable error rates depend strongly on the error model. If the errors are constrained, then they can be tolerated much better than depolarizing errors. In particular, if errors can be detected, tolerable error rates for computation are above $`20\%`$. This should be strong motivation to build in error detection when engineering quantum devices and designing error-correction strategies.

The use of teleportation demonstrates yet again the now well-known versatility of this basic quantum communication protocol. It is worth noting that frequent use of teleportation in a computation implicitly solves the leakage problem. This is the problem where qubits are lost from the computation without the event being detected, either by physical loss of the underlying particles, or by the particle’s state leaving the qubit-defining subspace. In every teleportation step, the destination qubits are fresh, and any previously leaked qubits contribute only to errors in the Bell measurements. These errors can be treated just like other errors.

Further work is required to determine the applicability of this work to practical quantum computation. For example, the scalability assumptions include massive parallelism in manipulating quantum bits, but no communication or classical processing latencies. It may be possible to reduce the latencies to a constant for relatively slow quantum computers with measurement times comparable to unitary gate times, but the necessary architectures that achieve this need to be further investigated. Realistically, it is necessary to consider the actual overheads required for implementing fault-tolerant computation. In general, experience shows that the overheads grow very rapidly as the maximum tolerable error rates are approached. As a result, it is a good idea to engineer computational devices to have error-rates that are substantially lower. In the case of the techniques used in this paper, the overheads are dominated by the complexity of state preparation. Little attempt has been made to prepare the states more efficiently than by the rejection method: Any time an error is detected, discard the state and start from scratch. Since theoretical scalability permits any polynomial overhead, further optimization is not considered here. As a result, overheads can be extremely large. Future investigations may yield significant improvements in efficiency without large decreases in tolerated error rates.

###### Acknowledgements.

Portions of this work were done at Los Alamos National Laboratory. This work was supported by the Department of Energy (DOE contract W-7405-ENG-36) and the U.S. National Security Agency. This paper is a contribution of the National Institute of Standards and Technology, an agency of the U.S. government, and is not subject to U.S. copyright.