REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR10-164 | 4th November 2010 20:55

#### Better gates can make fault-tolerant computation impossible

Revision #1
Authors: Falk Unger
Accepted on: 4th November 2010 20:55
Keywords:

Abstract:

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least $\beta_2=(3-\sqrt{7})/4\approx 8.856\%$, fault-tolerant computation is not possible. On the other hand, if all gates fail with probability $\epsilon<\beta_2$ and $\epsilon$ is the same for all gates, then fault-tolerant computation is possible. The assumption that all gates fail with *exactly* the same probability is pretty strong and unrealistic in real-world scenarios. Furthermore, one might be tempted to think that it can be removed easily, since making gates better'' should not hurt. Surprisingly, this is not the case, as we show in this work: there is a constant $\alpha_2<\beta_2$ such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range $[0,\alpha_2]$.
Hence, while a hardware manufacturer who consistently produces bad gates with noise rate $\alpha_2$ can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most $\alpha_2$ cannot.

Changes to previous version:

LaTeX errors in abstract on ECCC website corrected

### Paper:

TR10-164 | 4th November 2010 19:14

#### Better gates can make fault-tolerant computation impossible

TR10-164
Authors: Falk Unger
Publication: 4th November 2010 20:41
We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least $\e=(3-\sqrt{7})/4\approx 8.856\%$, fault-tolerant computation is not possible. On the other hand, if all gates fail with probability $\epsilon<\e$ and $\epsilon$ is the same for all gates, then fault-tolerant computation is possible. The assumption that all gates fail with \emph{exactly} the same probability is pretty strong and unrealistic in real-world scenarios. Furthermore, one might be tempted to think that it can be removed easily, since making gates better'' should not hurt. Surprisingly, this is not the case, as we show in this work: there is a constant $\alpha_2<\e$ such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range $[0,\alpha_2]$.
Hence, while a hardware manufacturer who consistently produces bad gates with noise rate $\alpha_2$ can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most $\alpha_2$ cannot.