Time: Tuesday, October 9th, 15:00
Speaker: Massimiliano DI VENTRA, UCSD
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 talk I will discuss how to employ one such property, memory (time non-locality), in a novel physics-based approach to computation: Memcomputing [1, 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 Witten-type 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. 123, 180901 (2018).
[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, Complexity 2018, 7982851 (2018).
[7] M. Di Ventra, F. L. Traversa and I.V. Ovchinnikov, Topological field theory and computing with instantons, Annalen der Physik 529,1700123 (2017).