 |
Center for Nonlinear Studies |
Recent work on memristor based dynamical systems, known as digital memcomputing machines (DMMs), has shown advantages in the solution of a wide range of hard combinatorial optimization problems. The physical reason behind this power rests on the DMMs collective dynamics in the form of dynamical long-range order (DLRO), which allows the efficient navigation of the problem state space. In this talk I will first review work we have done to assess the capabilities of computing with DMMs on a variety of combinatorial optimization benchmarks. Using DMMs as a guide, I will then propose a phenomenological model which captures the essential features of the dynamics in a simplified context and for a well-known problem: finding the ground state of an Ising spin glass. The model proceeds towards the ground state via a series of transitions which display correlations extending across the entire lattice, clearly supporting DLRO. I will then show that a full implementation of a DMM exhibits superior scaling compared to other methods when tested on the same problem class. These results further reinforce the advantages of computational approaches based on collective dynamics.
Host: Francesco Caravelli