Noise Threshold for Universality of Two-Input Gates

DOI10.1109/TIT.2008.926459zbMATH Open1322.68028arXiv0711.0351MaRDI QIDQ3604790FDOQ3604790

Authors: Falk Unger 

Publication date: 24 February 2009

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

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.

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

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

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)

Cited In (4)

• Reliable computation by formulas in the presence of noise
• Dual-code quantum computation model
• On the maximum tolerable noise for reliable computation by formulas
• Title not available (Why is that?)

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)