Memcomputing: Leveraging memory and physics to compute efficiently

Abstract

It is well known that physical phenomena may be of great help in computing some difficult problems efficiently. A typical example is prime factorization that may be solved in polynomial time by exploiting quantum entanglement on a quantum computer. There are, however, other types of (non-quantum) physical properties that one may leverage to compute efficiently a wide range of hard problems. In this perspective we discuss how to employ one such property, memory (time non-locality), in a novel physics-based approach to computation: Memcomputing. In particular, we focus on digital memcomputing machines (DMMs) that are scalable. DMMs can be realized with non-linear dynamical systems with memory. The latter property allows the realization of a new type of Boolean logic, one that is self-organizing. Self-organizing logic gates are "terminal-agnostic", namely they do not distinguish between input and output terminals. When appropriately assembled to represent a given combinatorial/optimization problem, the corresponding self-organizing circuit converges to the equilibrium points that express the solutions of the problem at hand. In doing so, DMMs take advantage of the long-range order that develops during the transient dynamics. This collective dynamical behavior, reminiscent of a phase transition, or even the "edge of chaos", is mediated by families of classical trajectories (instantons) that connect critical points of increasing stability in the system's phase space. The topological character of the solution search renders DMMs robust against noise and structural disorder. Since DMMs are non-quantum systems described by ordinary differential equations, not only can they be built in hardware with available technology, they can also be simulated efficiently on modern classical computers. As an example, we will show the polynomial-time solution of the subset-sum problem for the worst...

References in corpus (26)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computing
• Circuit elements with memory: memristors, memcapacitors and meminductors
• Memory effects in complex materials and nanoscale systems
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Memcomputing: a computing paradigm to store and process information on the same physical platform
• Application of Quantum Annealing to Training of Deep Neural Networks
• Solving mazes with memristors: a massively-parallel approach
• Universal Memcomputing Machines
• The statistics of critical points of Gaussian fields on large-dimensional spaces
• On the physical properties of memristive, memcapacitive, and meminductive systems
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Self-organization and solution of shortest-path optimization problems with memristive networks
• Introduction to Supersymmetric Theory of Stochastics
• Dynamic Computing Random Access Memory
• Topological field theory and computing with instantons
• Absence of chaos in Digital Memcomputing Machines with solutions
• The complex dynamics of memristive circuits: analytical results and universal slow relaxation
• Scale-free networks as an epiphenomenon of memory
• Instantons in self-organizing logic gates
• On the Universality of Memcomputing Machines
• Memcomputing with membrane memcapacitive systems
• Memcomputing Numerical Inversion with Self-Organizing Logic Gates

Cited by in corpus (21)

• p-Bits for Probabilistic Spin Logic
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• The promise of spintronics for unconventional computing
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Logical gates embedding in Artificial Spin Ice
• Mode-Assisted Unsupervised Learning of Restricted Boltzmann Machines
• Directed percolation and numerical stability of simulations of digital memcomputing machines
• On the Universality of Memcomputing Machines
• Critical branching processes in digital memcomputing machines
• Nanomagnetic Self-Organizing Logic Gates
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Equation Planting: A Tool for Benchmarking Ising Machines
• Artificial Spin Ice Phase-Change Memory Resistors
• Ergodicity, lack thereof, and the performance of reservoir computing with memristive networks
• Thermoplasmonic Nanomagnetic Logic Gates
• Modelling charge transport in gold nanogranular films
• Sampling scheme for neuromorphic simulation of entangled quantum systems
• Can biological quantum networks solve NP-hard problems?
• Projective Embedding of Dynamical Systems: uniform mean field equations
• Memory-induced long-range order in dynamical systems