skip to main content


Title: New Computational Results and Hardware Prototypes for Oscillator-based Ising Machines
In this paper, we report new results on a novel Ising machine technology for solving combinatorial optimization problems using networks of coupled self-sustaining oscillators. Specifically, we present several working hardware prototypes using CMOS electronic oscillators, built on bread-boards/perfboards and PCBs, implementing Ising machines consisting of up to 240 spins with programmable couplings. We also report that, just by simulating the differential equations of such Ising machines of larger sizes, good solutions can be achieved easily on benchmark optimization problems, demonstrating the effectiveness of oscillator-based Ising machines.  more » « less
Award ID(s):
1901004
PAR ID:
10184299
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Proc. Design Automation Conference
Page Range / eLocation ID:
1 to 2
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Booleank-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.

     
    more » « less
  2. Abstract

    The rich non‐linear dynamics of the coupled oscillators (under second harmonic injection) can be leveraged to solve computationally hard problems in combinatorial optimization such as finding the ground state of the Ising Hamiltonian. While prior work on the stability of the so‐called Oscillator Ising Machines (OIMs) has used the linearization method, in this letter, the authors present a complementary method to analyze stability using the second‐order derivative test of the energy/cost function. The authors establish the equivalence between the two methods, thus augmenting the tool kit for the design and implementation of OIMs.

     
    more » « less
  3. Nonlinear dynamical systems such as coupled oscillators are being actively investigated as Ising machines for solving computationally hard problems in combinatorial optimization. Prior works have established the equivalence between the global minima of the cost function describing the coupled oscillator system and the ground state of the Ising Hamiltonian. However, the properties of the oscillator Ising machine (OIM) from a nonlinear control viewpoint, such as the stability of the OIM solutions, remain unexplored. Therefore, in this work, using nonlinear control-theoretic analysis, we (i) identify the conditions required to ensure the functionality of the coupled oscillators as an Ising machine, (ii) show that all globally optimal phase configurations may not always be stable, resulting in some configurations being more favored over others and, thus, creating a biased OIM, and (iii) elucidate the impact of the stability of locally optimal phase configurations on the quality of the solution computed by the system. Our work, fostered through the unique convergence between nonlinear control theory and analog systems for computing, provides a new toolbox for the design and implementation of dynamical system-based computing platforms.

     
    more » « less
  4. Abstract

    Ising machines are hardware accelerators for combinatorial optimization and probabilistic sampling, using stochasticity to explore spin configurations and avoid local minima. We refine the previously proposed coupled chaotic bits (c-bits), which operate deterministically, by introducing noise. This improves performance in combinatorial optimization, achieving algorithmic scaling comparable to probabilistic bits (p-bits). We show that c-bits follow the quantum Boltzmann law in a 1D transverse field Ising model. Furthermore, c-bits exhibit critical dynamics similar to p-bits in 2D Ising and 3D spin glass models. Finally, we propose a noise-augmented c-bit approach via the adaptive parallel tempering algorithm (APT), which outperforms fully deterministic c-bits running simulated annealing. Analog Ising machines with coupled oscillators could draw inspiration from our approach, as running replicas at constant temperature eliminates the need for global modulation of coupling strengths. Ultimately, mixing stochasticity with deterministic c-bits yields a powerful hybrid computing scheme that can offer benefits in asynchronous, massively parallel hardware implementations.

     
    more » « less
  5. Abstract

    With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an “Augmented” Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.

     
    more » « less