.

Noisy Computation in Boolean Functions - a Statistical Physics View

Noise is inherent in most forms of computing and its impact is more dramatic as the computing circuits become more complex and of large scale. The consequence of component failure is felt more strongly in areas where highly reliable circuits are required.

Equipment reliability can be restored, to some extent, by the use of standard error correction but also their ability is being jeopardised by physical limitations of hardware minimisation. Classical computing circuits suffer from thermal noise and production errors, quantum computers suffer from decoherence, whilst an understanding of the noisy processes, inherent in neural networks and biological systems, remains poorly understood.

Research figure 1 small

The relative computing power of these different architectures should be revisited to incorporate the limitations imposed by noise. This will be particularly relevant to future integrated circuits that rely on ever growing gate-densities, which give rise to higher noise levels and probability of production errors.

Von Neumann was the first to consider the problem of noisy computing, aiming to better understand biological neural networks. He studied the limitations imposed by faults in the fundamental elements of circuits and demonstrated a method to correct their result. His analysis was followed by more recent studies, which show that in the case of Boolean functions there exists a limit for the tolerable gate noise; and that increased noise tolerance requires circuits of greater depth.

We will use established methods of statistical mechanics as well as new tools in the study of noisy computation, which enable one to obtain typical results for whole large-scale Boolean functions comprising unreliable logical gates by mapping them onto the corresponding physical system. The new approach will extend existing worst-case and potentially loose bounds, derived using current methodology, which is typically based on the properties of local substructures. We therefore expect to obtain results that are more relevant and representative, and are of both theoretical and practical value.

Research figure 2 small






Project objectives

  • to formalise the relation between typical random Boolean functions and the theory and techniques of statistical mechanics;
  • derive the number of non-trivial Boolean functions in randomly constructed trees;
  • analyse the role of noise in random Boolean functions for both thermal noise and random production errors;
  • analyse asymptotic error-rates below the critical gate-noise limits;
  • and employ advanced message passing techniques to obtain improved, more robust, realisations in specific instances.

The principal investigator of this project is Prof David Saad

Research fellow: Dr Alexander Mozeika

Funding
  • Funding source: The Leverhulme Trust (F/00 250/H)
  • Funding amount: £ 135,111
  • Duration: 1/2009-12/2011

Achievements


Publications

Journal papers

  1. A. Mozeika, D. Saad and J. Raymond, “Computing with Noise - Phase Transitions in Boolean Formulas”, Phys. Rev. Lett. 103, 248701 (2009).
  2. A. Mozeika, D. Saad and J. Raymond, “Noisy Random Boolean Formulae - a Statistical Physics Perspective”, Phys. Rev. E    82, 041112 (2010).
  3. A. Mozeika and D. Saad, “Dynamics of Boolean Networks - an Exact Solution”, Phys. Rev. Lett. 106, 214101 (2011).
  4. A. Mozeika and D. Saad, “Phase Transitions and Memory Effects in the Dynamics of Boolean Networks”, Philosophical Magazine, 92, Issue 1-3, 210-229, (2012).
  5. D. Saad and A. Mozeika, “Islands of equilibrium in a dynamical world”, submitted (2012).
  6. A. Mozeika and D. Saad, “Growing Boolean functions in the presence of noise”, submitted (2012).

  7. A. Mozeika and D. Saad, “On the Computational Ability of Boolean Circuits”, in preparation (2011).

Conferences proceedings

  1. A. Mozeika, D. Saad and J. Raymond, On the Robustness of Random Boolean Formulae, Proceedings of the International Workshop on Statistical-Mechanical Informatics 2010 (IW-SMI2010), Journal of Physics: Conference Series 233 (2010) 012015.

Presentations - oral

  1. A. Mozeika, D. Saad and J. Raymond, Computing with noise - a statistical physics approach, Techniques and Challenges from Statistical Physics, Centre de Recerca Matematica Bellaterra, Spain, 14-16 October, 2009.
  2. A. Mozeika, D. Saad and J. Raymond, On the Robustness of Random Boolean Formulae, the International Workshop on statistical-Mechanical Informatics 2010 (IWSMI2010) March 7-10, 2010, Kyoto, Japan.*
  3. A. Mozeika, D. Saad and J. Raymond, Statistical Mechanics of Noisy Computation, Statistical physics of complexity, optimization and systems biology, 7-12 March 2010, School of theoretical physics, Les Houches, France.
  4. A. Mozeika, D. Saad and J. Raymond, Non-equilibrium statistical mechanics of Noisy Computing, Nonequilibrium Statistical physics of complex systems (Satellite Meeting of STATPHYS-24), 26-29 July 2010, Seoul, South Korea.
  5. A. Mozeika and D. Saad, Dynamics of Boolean Networks - an Exact Solution, Statistical physics of complexity, optimization, and systems biology ,14-18 February 2011 Bardonecchia, Italy. *
  6. A. Mozeika and D. Saad, Dynamics of Boolean Networks - a Generating Functional Analysis, Interdisciplinary Applications of Statistical Physics & Complex Networks,1 March- 1 April 2011 Beijing. *
  7. A. Mozeika and D. Saad, Dynamics of Boolean Networks - an exact solution, Miniconference on statistical mechanics of glassy and disordered systems, 23-24 May 2011, King’s College London.
  8. A. Mozeika and D. Saad, , Exact solution of Boolean dynamics with random connections, thermal noise and strong memory effects, SigmaPhi2011 International Conferenceon Statistical Physics, 11-15 July 2011, Larnaka, Cyprus. (2011).
  9. D.Saad and A. Mozeika, Islands of equilibrium in non-equilibrium systems, Biology and Physics of Information Processing, Nordita workshop, 16 April- 11 May 2012, Stockholm (2012).*
  10. A. Mozeika and D. Saad, On the existence of equilibrium domains in non-equilibrium systems, Statistical Mechanics of Unsatisfiability and Glasses, Mariehamn, Åland, Sweden (2012)
  11. D.Saad and A. Mozeika, Equilibrium-like domains in non-equilibrium systems, Machine Learning, August 29-31 2012, the International Center for Theoretical Physics in Trieste, Italy (2012).*
  12. A. Mozeika and D.Saad, Phase transitions and memory effects in the dynamics of noisy Boolean networks, Biology and Physics of Information Processing, Nordita workshop, 16 April- 11 May 2012, Stockholm (2012).
  13.  D.Saad and A. Mozeika, Equilibrium-like domains in non-equilibrium systems, Machine Learning, September 10-28 2012, The Max-Planck Institute for Complex Systems, Dresden, Germany (2012).*
 * - By invitation

Presentation - poster

  1. A. Mozeika, D. Saad and J. Raymond, Computing with Noise - Phase Transitions in Boolean Formulas, European Conference on Complex Systems’ 09, University of Warwick, 21-25 September, 2009.