Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1206.4851

On reliable computation by noisy random Boolean formulas

Alexander Mozeika, David Saad

Published Jan 1, 2012• 0 citations
arXivHTMLPDF

Abstract

We study noisy computation in randomly generated k-ary Boolean formulas. We establish bounds on the noise level above which the results of computation by random formulas are not reliable. This bound is saturated by formulas constructed from a single majority-like gates. We show that these gates can be used to compute any Boolean function reliably below the noise bound.

DOI
10.13140/rg.2.1.1191.0645

Related papers

Reliable Computation by Large-Alphabet Formulas in the Presence of Noise

Andrew K. Tan, Matthew H. Ho, Isaac L. Chuang

We present two new positive results for reliable computation using formulas over physical alphabets of size$q \gt 2$. First, we show that for logical alphabets of size$\ell = q$the threshold for denoising using gates subject to q-ary symmetric noise with error probability$\varepsilon $is strictly larger than that for Boolean computation, and we show that reliable computation is possible as long as signals remain distinguishable, i.e.$\epsilon \lt (q - 1) / q$, in the limit of large fan-in$k \rightarrow \infty $. We also determine the point at which generalized majority gates with bounded fan-in fail, and show in particular that reliable computation is possible for$\epsilon \lt (q - 1) / (q (q + 1))$in the case of q prime and fan-in$k = 3$. Secondly, we provide an example where$\ell \lt q$, showing that reliable Boolean computation,$\ell = 2$, can be performed using 2-input ternary,$q = 3$, logic gates subject to symmetric ternary noise of strength$\varepsilon \lt 1/6$by using the additional alphabet element for error signaling.

arXiv:2306.13262•IEEE Transactions on Information Theory•Nov 1, 2024•0 citations

Lower bounds for the complexity of reliable Boolean circuits with noisy gates

Anna Gál

It is proved that the reliable computation of any Boolean function with, sensitivity s requires Omega (s log s) gates if the gates of the circuit fail independently with a fixed positive probability. The Omega (s log s) bound holds even if s is the block sensitivity instead of the sensitivity of the Boolean function. Some open problems are mentioned.>

Annual Symposium on Foundations of Computer Science•Dec 9, 2002•22 citations

Better gates can make fault-tolerant computation impossible.

Falk Unger

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 β2 = (3− √ 7)/4 ≈ 8.856%, faulttolerant computation is not possible. On the other hand, if all gates fail with probability < β2 and 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 α2 < β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, α2]. Hence, while a hardware manufacturer who consistently produces bad gates with noise rate α2 can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most α2 cannot.

Electronic colloquium on computational complexity•Jan 1, 2010•4 citations

Quantum Formulas: A Lower Bound and Simulation

Vwani Roychowdhury, Farrokh Vatan

We show that Nechiporuk's method [I. Wegener, The Complexity of Boolean Functions, Teubner-Wiley, New York, 1987] for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an $\Omega(n^2/\log^2 n)$ lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas [A. Yao, Proceedings of 34th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 352--361] states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.

arXiv:quant-ph/0104053•SIAM Journal on Computing•Jan 1, 2001•5 citations

Lower bounds for noisy Boolean decision trees

William Evans, Nicholas J. Pippenger

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1996•84 citations

Average-Case Lower Bounds for Noisy Boolean Decision Trees

William Evans, Nicholas J. Pippenger

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.

SIAM Journal on Computing•Jan 1, 1998•17 citations
We study noisy computation in randomly generated k-ary Boolean formulas. We establish bounds on the noise level above which the results of computation by random formulas are not reliable. This bound is saturated by formulas constructed from a single majority-like gates. We show that these gates can be used to compute any Boolean function reliably below the noise bound.
We present two new positive results for reliable computation using formulas over physical alphabets of sizeq>2q \gt 2q>2. First, we show that for logical alphabets of sizeℓ=q\ell = qℓ=qthe threshold for denoising using gates subject to q-ary symmetric noise with error probability$\varepsilon isstrictlylargerthanthatforBooleancomputation,andweshowthatreliablecomputationispossibleaslongassignalsremaindistinguishable,i.e.is strictly larger than that for Boolean computation, and we show that reliable computation is possible as long as signals remain distinguishable, i.e.isstrictlylargerthanthatforBooleancomputation,andweshowthatreliablecomputationispossibleaslongassignalsremaindistinguishable,i.e.\epsilon \lt (q - 1) / q,inthelimitoflargefan−in, in the limit of large fan-in,inthelimitoflargefan−ink \rightarrow \infty .Wealsodeterminethepointatwhichgeneralizedmajoritygateswithboundedfan−infail,andshowinparticularthatreliablecomputationispossiblefor. We also determine the point at which generalized majority gates with bounded fan-in fail, and show in particular that reliable computation is possible for.Wealsodeterminethepointatwhichgeneralizedmajoritygateswithboundedfan−infail,andshowinparticularthatreliablecomputationispossiblefor\epsilon \lt (q - 1) / (q (q + 1))inthecaseofqprimeandfan−inin the case of q prime and fan-ininthecaseofqprimeandfan−ink = 3.Secondly,weprovideanexamplewhere. Secondly, we provide an example where.Secondly,weprovideanexamplewhere\ell \lt q,showingthatreliableBooleancomputation,, showing that reliable Boolean computation,,showingthatreliableBooleancomputation,\ell = 2,canbeperformedusing2−inputternary,, can be performed using 2-input ternary,,canbeperformedusing2−inputternary,q = 3,logicgatessubjecttosymmetricternarynoiseofstrength, logic gates subject to symmetric ternary noise of strength,logicgatessubjecttosymmetricternarynoiseofstrength\varepsilon \lt 1/6$by using the additional alphabet element for error signaling.
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 β2 = (3− √ 7)/4 ≈ 8.856%, faulttolerant computation is not possible. On the other hand, if all gates fail with probability < β2 and 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 α2 < β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, α2]. Hence, while a hardware manufacturer who consistently produces bad gates with noise rate α2 can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most α2 cannot.
We show that Nechiporuk's method [I. Wegener, The Complexity of Boolean Functions, Teubner-Wiley, New York, 1987] for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an Ω(n2/log⁡2n)\Omega(n^2/\log^2 n)Ω(n2/log2n) lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas [A. Yao, Proceedings of 34th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 352--361] states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.