X25.00006. Critical branching processes in digital memcomputing machines

Presented by: Sean Bearden


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 digital 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 τ=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 τ=1.51±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. [1] [1] S.R.B. Bearden, et al, 2019, EPL 127, 30005 *Work supported in part by CMRR, DARPA, NSF Graduate Reasearch Fellowship, and the Alfred P. Sloan Foundation.

Authors

  • Sean Bearden
  • Forrest C Sheldon
  • Massimiliano Di Ventra


Comments

Powered by Q-CTRL

© 2020 Virtual APS March Meeting. All rights reserved.