For quantum circuits, once the gate error is below a threshold, the error probability of an entire computation can be driven exponentially small with polylog costs in time and space:
http://arxiv.org/pdf/quant-ph/9611025v2.pdf
The classical version should be entirely analogous, and was presumably proven long before the quantum case. Who proved the classical version?