For unreliable classical computation there is an error threshold theorem due to von Neumann analogous to the quantum error threshold theorem that shows that even if gates produce the wrong result at some rate, as long as this rate is below a certain threshold the total error probability can be reduced arbitrarily by adding some polynomial overhead.

For the quantum threshold there is a lot of active research trying to pin down bounds, but are there any corresponding results for classical computation error thresholds?

The best bound I know of on the polynomial overhead is from (Spielman 1996): a computation taking time $T$ on $N$ error-prone processors can be run using $N \log^{O(1)}(N)$ processors in time $T \log^{O(1)}(N)$ with failure probability at most $t \exp(-N^{1/4})$. But are there known values of the O(1) constants? And there is no explicit estimate of the threshold error rate.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.