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 , and approximations to the Max-SAT beyond the inapproximability gap  using polynomial resources and self-organizing logic gates, namely gates that self-organize to satisfy their logical proposition . 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 . 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/).
 F. L. Traversa and M. Di Ventra, Universal Memcomputing Machines, IEEE Transactions on Neural Networks and Learning Systems 26, 2702 (2015).
 M. Di Ventra and Y.V. Pershin, Computing: the Parallel Approach, Nature Physics 9, 200 (2013).
 M. Di Ventra and Y.V. Pershin, Just add memory, Scientific American 312, 56 (2015).
 M. Di Ventra and F.L. Traversa, Memcomputing: leveraging memory and physics to compute efficiently, J. Appl. Phys. 123, 180901 (2018).
 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).
 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).
 M. Di Ventra, F. L. Traversa and I.V. Ovchinnikov, Topological field theory and computing with instantons, Annalen der Physik 529,1700123 (2017).