Which features make the brain such a powerful and energy-efficient computing machine? Can we reproduce them in the solid state, and if so, what type of computing paradigm would we obtain? I will show that a machine that uses memory to both process and store information, like our brain, and is endowed with intrinsic parallelism and information overhead - namely takes advantage, via its collective state, of the network topology related to the problem - has a computational power far beyond our standard digital computers [1]. We have named this novel computing paradigm “memcomputing” [2, 3, 4]. As examples, I will show the polynomial-time solution of prime factorization, the search version of the subset-sum problem [5], and approximations to the Max- SAT beyond the inapproximability gap [6] using polynomial resources and self-organizing logic gates, namely gates that self-organize to satisfy their logical proposition [5]. I will also show that these machines are described by a topological field theory, and they compute via an instantonic phase, implying that they are robust against noise and disorder [7]. The digital memcomputing machines we propose can be efficiently simulated, are scalable and can be easily realized with available nanotechnology components. Work supported in part by MemComputing, Inc. (http://memcpu.com/).
[1] F. L. Traversa and M. Di Ventra,
Universal Memcomputing Machines,
IEEE Transactions on Neural
Networks and Learning Systems 26, 2702 (2015).
[2] M. Di Ventra and Y.V. Pershin,
Computing: the Parallel Approach,
Nature Physics 9, 200 (2013).
[3] M. Di Ventra and Y.V. Pershin,
Just add memory,
Scientific American 312, 56 (2015).
[4] M. Di Ventra and F.L. Traversa,
Memcomputing: leveraging memory and physics to compute efficiently,
J. Appl. Phys. (in press), arXiv:1802.06928.
[5] 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).
[6] F. L. Traversa, P. Cicotti, F. Sheldon, and M. Di Ventra,
Evidence of an exponential speed-up in the solution of hard optimization problems,
arXiv:1710.09278.
[7] M. Di Ventra, F. L. Traversa and I.V. Ovchinnikov,
Topological field theory and computing with instantons,
Annalen der Physik 1700123 (2017).
