MemComputing is a new physics-based approach to computation that employs time non-locality (memory) to both process and store information on the same physical location [1]. Its digital version is designed to solve combinatorial optimization problems. A practical realization of digital memcomputing machines (DMMs) can be accomplished via circuits of non-linear dynamical systems with memory engineered so that periodic orbits and chaos can be avoided. A given logic (or algebraic) problem is first mapped into this type of dynamical system whose point attractors represent the solutions of the original problem. A DMM then finds the solution via a succession of elementary avalanches (instantons) whose role is to eliminate configurations of logical inconsistency ("logical defects") from the circuit. I will discuss the physics behind MemComputing and show many examples of its applicability to various combinatorial optimization problems, Machine Learning, and Quantum Mechanics, demonstrating its advantages over traditional approaches and even quantum computing. Work supported by DARPA, DOE, NSF, CMRR, and MemComputing, Inc. (http://memcpu.com/).

Many optimization problems can be cast into the maximum satisfiability (MAX-SAT) form, and many solvers have been developed for tackling such problems. To evaluate a MAXSAT solver, it is convenient to generate hard MAX-SAT instances with known solutions. Here, we propose a method of generating weighted MAX-2-SAT instances inspired by the frustrated-loop algorithm used by the quantum annealing community. We extend the algorithm for instances of general bipartite couplings, with the associated optimization problem being the minimization of the restricted Boltzmann machine (RBM) energy over the nodal values, which is useful for effectively pre-training the RBM. The hardness of the generated instances can be tuned through a central parameter known as the frustration index. Two versions of the algorithm are presented: the random- and structured-loop algorithms. For the random-loop algorithm, we provide a thorough theoretical and empirical analysis on its mathematical properties from the perspective of frustration, and observe empirically a double phase transition behavior in the hardness scaling behavior driven by the frustration index. For the structured-loop algorithm, we show that it offers an improvement in hardness over the random-loop algorithm in the regime of high loop density, with the variation of hardness tunable through the concentration of frustrated weights.

Memcomputing is a novel computing paradigm that employs time non-local dynamical systems to compute with and in memory. The digital version of these machines [digital memcomputing machines or (DMMs)] is scalable, and is particularly suited to solve combinatorial optimization problems. One of its possible realizations is by means of standard electronic circuits, with and without memory. Since these elements are non-quantum, they can be described by ordinary differential equations. Therefore, the circuit representation of DMMs can also be simulated efficiently on our traditional computers. We have indeed previously shown that these simulations only require time and memory resources that scale linearly with the problem size when applied to finding a good approximation to the optimum of hard instances of the maximum-satisfiability problem. The state-of-the-art algorithms, instead, require exponential resources for the same instances. However, in that work, we did not push the simulations to the limit of the processor used. Since linear scalability at smaller problem sizes cannot guarantee linear scalability at much larger sizes, we have extended these results in a stress-test up to $64\times 10^{6}$ variables (corresponding to about 1 billion literals), namely the largest case that we could fit on a single core of an Intel Xeon E5-2860 with 128 GB of dynamic random-access memory (DRAM). For this test, we have employed a commercial simulator, Falcon of MemComputing, Inc. We find that the simulations of DMMs still scale linearly in both time and memory up to these very large problem sizes versus the exponential requirements of the state-of-the-art solvers. These results further reinforce the advantages of the physics-based memcomputing approach compared with traditional ones.

Innovative and new computing paradigms must be considered as we reach the limits of von Neumann computing caused by the growth in necessary data processing. This paper provides an introduction to three emerging computing models that have established themselves as likely post-CMOS and post-von Neumann solutions. The first of these ideas is quantum computing, for which we discuss the challenges and potential of quantum computer architectures. Next, a computational system using intrinsic oscillators is introduced and an example is provided which shows its superiority in comparison to a typical von Neumann computational system. Finally, digital memcomputing using self-organizing logic gates is explained and then discussed as a method for optimization problems and machine learning.

Universal memcomputing machines (UMMs) represent a novel computational model in which memory (time nonlocality) accomplishes both tasks of storing and processing of information. UMMs have been shown to be Turing-complete, namely, they can simulate any Turing machine. In this paper, we first introduce a novel set theory approach to compare different computational models and use it to recover the previous results on Turing-completeness of UMMs. We then relate UMMs directly to liquid-state machines (or "reservoir-computing") and quantum machines ("quantum computing"). We show that UMMs can simulate both types of machines, hence they are both "liquid-" or "reservoir-complete" and "quantum-complete." Of course, these statements pertain only to the type of problems these machines can solve and not to the amount of resources required for such simulations. Nonetheless, the set-theoretic method presented here provides a general framework which describes the relationship between any computational models.

We propose to use digital memcomputing machines (DMMs), implemented with self-organizing logic gates (SOLGs), to solve the problem of numerical inversion. Starting from fixed-point scalar inversion, we describe the generalization to solving linear systems and matrix inversion. This method, when realized in hardware, will output the result in only one computational step. As an example, we perform simulations of the scalar case using a 5-bit logic circuit made of SOLGs, and show that the circuit successfully performs the inversion. Our method can be extended efficiently to any level of precision, since we prove that producing -bit precision in the output requires extending the circuit by at most bits. This type of numerical inversion can be implemented by DMM units in hardware; it is scalable, and thus of great benefit to any real-time computing application.

We introduce the notion of universal memcomputing machines (UMMs): a class of brain-inspired general-purpose computing machines based on systems with memory, whereby processing and storing of information occur on the same physical location. We analytically prove that the memory properties of UMMs endow them with universal computing power (they are Turing-complete), intrinsic parallelism, functional polymorphism, and information overhead, namely, their collective states can support exponential data compression directly in memory. We also demonstrate that a UMM has the same computational power as a nondeterministic Turing machine, namely, it can solve nondeterministic polynomial (NP)-complete problems in polynomial time. However, by virtue of its information overhead, a UMM needs only an amount of memory cells (memprocessors) that grows polynomially with the problem size. As an example, we provide the polynomial-time solution of the subset-sum problem and a simple hardware implementation of the same. Even though these results do not prove the statement NP = P within the Turing paradigm, the practical realization of these UMMs would represent a paradigm shift from the present von Neumann architectures, bringing us closer to brain-like neural computation.

In this paper we propose CMOS-compatible Memristive-Biosensors as label-free, highly sensitive sensors for in-air detection of Vascular Endothelial Growth Factor (VEGF) molecules. The memristive behavior of the fabricated devices is strongly affected by molecules in proximity of the wire surface. In this paper, we demonstrate the reproducibility of the measurement based on the memristive voltage gap. We also show the successful sensing of femto-molar amounts of VEGF. Specifically, we demonstrate a correlation between the decreasing behavior of the voltage gap and the increasing concentrations of VEGF. The voltage gap dependence on the pH of the initial solution is also shown as a further proof of the ionic interactions occurring at the SiNW surface. All measurements are performed in air, under controlled humidity; this makes our approach more sensitive thanks to the lowered Debye screening effect of counterions.

We discuss the implementation of a novel approach to computing named memcomputing using memelements - in particular memcapacitive systems. It is shown that solid-state memcapacitive systems are ideal to implement such a concept since they support information processing and storage at the same physical location at low-energy cost. This feature can be used to perform boolean logic functions “on demand” directly in memory. In this paper, we develop the idea of a memcapacitive dynamic computing random access memory introducing a novel computing scheme based on Voltage Sense Amplifiers, and discussing some features of information storage in internal states of memcapacitive systems in the presence of leakage currents.

Adaptive response to varying environment is a common feature of biological organisms. Reproducing such features in electronic systems and circuits is of great importance for a variety of applications. We consider memory models inspired by an intriguing ability of slime molds to both memorize the period of temperature and humidity variations and anticipate the next variations to come, when appropriately trained. Effective circuit models of such behavior are designed using: 1) a set of LC contours with memristive damping and 2) a single memcapacitive system-based adaptive contour with memristive damping. We consider these two approaches in detail by comparing their results and predictions. Finally, possible biological experiments that would discriminate between the models are discussed. In this paper, we also introduce an effective description of certain memory circuit elements.

Fast and low-cost DNA sequencing methods would revolutionize medicine: a person could have his/her full genome sequenced so that drugs could be tailored to his/her specific illnesses; doctors could know in advance patients' likelihood to develop a given ailment; cures to major diseases could be found faster [1]. However, this goal of “personalized medicine” is hampered today by the high cost and slow speed of DNA sequencing methods. We will discuss the sequencing protocol we suggest which requires the measurement of the distributions of transverse currents during the translocation of single-stranded DNA into nanopores [2–6]. We will support our conclusions with a combination of molecular dynamics simulations coupled to quantum mechanical calculations of electrical current in experimentally realizable systems [2–6]. We will also discuss recent experiments that support these theoretical predictions. In addition, we will show how this relatively unexplored area of research at the interface between solids, liquids, and biomolecules at the nanometer length scale is a fertile ground to study quantum phenomena that have a classical counterpart, such as ionic quasi-particles and ionic “quantized” conductance [7,8].

Memory effects are ubiquitous in nature and the class of memory circuit elements—which includes memristive, memcapacitive, and meminductive systems—shows great potential to understand and simulate the associated physical processes. Here, we show that such elements can also be used in electronic schemes mimicking biologically inspired computer architectures, performing digital logic and arithmetic operations, and can expand the capabilities of certain quantum computation schemes. In particular, we will discuss some examples where the concept of memory elements is relevant to the realization of associative memory in neuronal circuits, spike-timing-dependent plasticity (STDP) of synapses, and digital and field-programmable quantum computing.

We extend the notion of memristive systems to capacitive and inductive elements, namely, capacitors and inductors whose properties depend on the state and history of the system. All these elements typically show pinched hysteretic loops in the two constitutive variables that define them: current-voltage for thememristor,charge-voltage for thememcapacitor,and current-flux for thememinductor. We argue that these devices are common at the nanoscale, where the dynamical properties of electrons and ions are likely to depend on the history of the system, at least within certain time scales. These elements and their combination in circuits open up new functionalities in electronics and are likely to find applications in neuromorphic devices to simulate learning, adaptive, and spontaneous behavior.