Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Better gates can make fault-tolerant computation impossible

RSS-Feed




Revision #1
Authors: Falk Unger
Accepted on: 4th November 2010 20:55
Downloads: 2793
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
Downloads: 3190
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 $\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.



ISSN 1433-8092 | Imprint