Noise Threshold for Universality of Two-Input Gates

DOI10.1109/TIT.2008.926459MaRDI QIDQ3604790zbMATH OpenFDO

Authors Falk Unger

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.0351

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Analytic circuit theory (94C05)

Abstract: Evans and Pippenger showed in 1998 that noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability epsilon and epsilon<theta, where theta is roughly 8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least theta cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is theta. We conjecture that the same threshold also holds for circuits.

Recommendations

• On the maximum tolerable noise for reliable computation by formulas
• Can large fanin circuits perform reliable computations in the presence of faults?
• On the maximum tolerable noise for reliable computation by formulas
• Reliable computation by formulas in the presence of noise
• Upper bounds on the noise threshold for fault-tolerant quantum computing

Cited in

(4)

• scientific article; zbMATH DE number 5320399 (Why is no real title available?)
• Reliable computation by formulas in the presence of noise
• Dual-code quantum computation model
• On the maximum tolerable noise for reliable computation by formulas

This page was built for publication: Noise Threshold for Universality of Two-Input Gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3604790)