UC San Diego

This dissertation aims to address the dual goals of (1) proposing practical computing devices that meet a growing need for alternatives to von Neumann architecture, and (2) leveraging these to build new connections between computation and physics. As an avenue towards the former, I have focused on dynamical systems inspired by the digital memcomputing machines (DMMs) proposed by M. Di Ventra and F. Traversa. These are continuous dynamical systems, embeddable directly in hardware, which can be utilized to solve discrete combinatorial problems. Through several benchmarking studies, we have established that this approach to combinatorial optimization can outperform standard algorithmic methods, both in time to solution, and in scaling. In many cases we are able to show that the time to solution of a digital memcomputing machine scales polynomially in instance size when other approaches scale exponentially. This indicates that the unique niche occupied by DMMs as deterministic, continuous dynamical systems solvers, possesses features not present in traditional approaches. As an avenue towards uncovering these features, we have worked to construct simplified models of DMMs that would facilitate theoretical work to rigorously establish their capabilities. In navigating their configuration space, these devices manifest a form of dynamical long-range order in which widely separated variables transition between states collectively. The structure of the equations borrowed from a DMM combined with the ‘heuristic’ requirement of long-range order allows us to construct a set of equations that reproduce several features of the DMM dynamics and that are able to solve a set of problems derived from spin-glasses. The form of these equations clarifies the essential role of continuity in the dynamics of the solver and the role of memory in DMMs.