Critical branching processes in digital memcomputing machines

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 $\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.

5 pages, 3 figures

References in corpus (8)

• Self-Organized Branching Processes: A Mean-Field Theory for Avalanches
• Memcomputing: a computing paradigm to store and process information on the same physical platform
• Memcomputing: Leveraging memory and physics to compute efficiently
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Growing Critical: Self-Organized Criticality in a Developing Neural System
• A simple unified view of branching process statistics: random walks in balanced logarithmic potentials
• Topological field theory and computing with instantons
• Instantons in self-organizing logic gates

Cited by in corpus (5)

• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Mode-Assisted Unsupervised Learning of Restricted Boltzmann Machines
• Directed percolation and numerical stability of simulations of digital memcomputing machines
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Brain-like features of MemComputing machines