Computing with Noise: Phase Transitions in Boolean Formulas

Computing circuits composed of noisy logical gates and their ability to represent arbitrary Boolean functions with a given level of error are investigated within a statistical mechanics setting. Existing bounds on their performance are straightforwardly retrieved, generalized, and identified as the corresponding typical-case phase transitions. Results on error rates, function depth, and sensitivity, and their dependence on the gate-type and noise model used are also obtained.

Figure 1

The model of two coupled systems with identical topology and different inverse temperatures $\beta$ and $\widehat{\beta }\to \infty$. Gates are indicated by squares, $S^I$ and input nodes by circles. Blue (dark gray) indicates noiseless gates, red (gray) indicates noisy gates.

Figure 2

Properties of MAJ-3 gate-based formulas: (a) Magnetization $m$ and output error $\delta$ as a function of gate noise $ϵ$. (b) Sensitivity of $\Delta (\ell )$ to input mismatch $\Delta (0)$ for $m(0)=0$. (c) Phase diagram for gate noise $ϵ$ at layer $L$. For the MAJ-7 function, we plot the evolution, in layers ($l$), of (d) magnetization $m$ and (e) output error $\delta$.