Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks

Digital memcomputing machines (DMMs) are a new class of computing machines that employ non-quantum dynamical systems with memory to solve combinatorial optimization problems. Here, we show that the time to solution (TTS) of DMMs follows an inverse Gaussian distribution, with the TTS self-averaging with increasing problem size, irrespective of the problem they solve. We provide both an analytical understanding of this phenomenon and numerical evidence by solving instances of t...

Decades of exponential scaling in high performance computing (HPC) efficiency is coming to an end. Transistor based logic in complementary metal-oxide semiconductor (CMOS) technology is approaching physical limits beyond which further miniaturization will be impossible. Future HPC efficiency gains will necessarily rely on new technologies and paradigms of compute. The Ising model shows particular promise as a future framework for highly energy efficient computation. Ising sys...

Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet...

An Ising machine is any hardware specifically designed for finding the ground state of the Ising model. Relevant examples are coherent Ising machines and quantum annealers. In this paper, we propose a new machine learning model that is based on the Ising structure and can be efficiently trained using gradient descent. We provide a mathematical characterization of the training process, which is based upon optimizing a loss function whose partial derivatives are not explicitly ...

Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to additional applications of larger scale. We present a straightforward and effective method for solving larger-than-QPU lattice-structured Ising optimization problems. Performance is compared against simulated annealing with promising results, and improvement is shown as a function of the generation of D-Wave Q...

Recent years have witnessed an unprecedented increase in experiments and hybrid simulations involving quantum computers. In particular, quantum annealers. Although quantum supremacy has not been established thus far, there exist a plethora of algorithms promising to outperform classical computers in the near-term future. Here, we propose a parallel in time approach to simulate dynamical systems designed to be executed already on present-day quantum annealers. In essence, pure...

The development of physical simulators, called Ising machines, that sample from low energy states of the Ising Hamiltonian has the potential to drastically transform our ability to understand and control complex systems. However, most of the physical implementations of such machines have been based on a similar concept that is closely related to relaxational dynamics such as in simulated, mean-field, chaotic, and quantum annealing. We show that nonrelaxational dynamics that i...

Combinatorial optimization problems can be mapped onto Ising models, and their ground state is generally difficult to find. A lot of heuristics for these problems have been proposed, and one promising approach is to use continuous variables. In recent years, one such algorithm has been implemented by using parametric oscillators known as coherent Ising machines. Although these algorithms have been confirmed to have high performance through many experiments, unlike other famil...

Disordered many-body systems exhibit a wide range of emergent phenomena across different scales. These complex behaviors can be utilized for various information processing tasks such as error correction, learning, and optimization. Despite the empirical success of utilizing these systems for intelligent tasks, the underlying principles that govern their emergent intelligent behaviors remain largely unknown. In this thesis, we aim to characterize such emergent intelligence in ...

We propose an Ising machine made of microelectromechanical systems (MEMS), where the annealing process is automatically executed by a dissipation mechanism. The core structure is a series of buckled plates. Two stable positions of each plate (left and right) represent its binary state acting as a bit so that a plate works as a mechanical memory. The electrostatic interaction between adjacent plates is introduced by applying voltage. Plates continue to flip between two stable ...