Critical branching processes in memcomputing
Skip to main content
eScholarship
Open Access Publications from the University of California

Critical branching processes in memcomputing

  • Author(s): Bearden, Sean RB
  • Sheldon, Forrest C
  • Ventra, Massimiliano Di
  • et al.
Abstract

Memcomputing is a novel computing paradigm that employs time non-locality (memory) to solve combinatorial optimization problems. It can be realized in practice by means of non-linear dynamical systems whose point attractors represent the solutions of the original problem. It has been previously shown that during the solution search memcomputing machines go through a transient phase of avalanches (instantons) that promote dynamical long-range order. By employing mean-field arguments we predict that the distribution of the avalanche sizes follows a Borel distribution typical of critical branching processes with exponent $\tau= 3/2$. We corroborate this analysis by solving various random 3-SAT instances of the Boolean satisfiability problem. The numerical results indicate a power-law distribution with exponent $\tau = 1.51 \pm 0.02$, in very good agreement with the mean-field analysis. This indicates that memcomputing machines self-tune to a critical state in which avalanches are characterized by a branching process, and that this state persists across the majority of their evolution.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View