MemComputing: leveraging memory and physics to compute efficiently

In this talk I will discuss how to employ memory (time non-locality), in a novel physics-based approach to computation: Memcomputing [1, 2, 3]. As examples, I will show the polynomial-time solution of prime factorization, the search version of the subset-sum problem [4], and approximations to the Max-SAT beyond the inapproximability gap [5], using polynomial resources and self-organizing logic gates, namely gates that self-organize to satisfy their logical proposition [4]. I will also show that these machines are described by a Witten-type topological field theory, and they compute via an instantonic phase, implying that they are robust against noise and disorder [6]. The digital memcomputing machines we propose can be efficiently simulated, are scalable and can be easily realized with available nanotechnology components.

[1] M. Di Ventra and Y.V. Pershin, Computing: the Parallel Approach, Nature Physics 9, 200 (2013).
[2] F. L. Traversa and M. Di Ventra, Universal Memcomputing Machines, IEEE Transactions on Neural Networks and Learning Systems 26, 2702 (2015).
[3] M. Di Ventra and F.L. Traversa, Memcomputing: leveraging memory and physics to compute efficiently, J. Appl. Phys. 123, 180901 (2018).
[4] F. L. Traversa and M. Di Ventra, Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines, Chaos: An Interdisciplinary Journal of Nonlinear Science 27, 023107 (2017).
[5] F. L. Traversa, P. Cicotti, F. Sheldon, and M. Di Ventra, Evidence of an exponential speed-up in the solution of hard optimization problems, Complexity 2018, 7982851 (2018).
[6] M. Di Ventra, F. L. Traversa and I.V. Ovchinnikov, Topological field theory and computing with instantons, Annalen der Physik 529,1700123 (2017).