Coupled Oscillator-Based Ising Machines to Solve Computationally Hard Combinatorial Optimization Problems

While the Von-Neumann architecture-based digital computing framework has been the foundation for modern information processing, there are certain classes of computational problems that are still considered intractable to solve using digital computers. Such problems entail exponentially increasing computing resources with increasing problem size. This has motivated the exploration of alternate computing paradigms. Ising machines have emerged as a promising candidate for solving such computationally challenging problems e.g., the NP-Hard problem, Maximum Cut (Max-Cut) of a graph. However, the effectiveness of this paradigm and its ability to outperform state-of-the-art digital computers will ultimately be decided by the area, scalability, energy efficiency, and performance of the underlying hardware implementation. Current implementations using CMOS, optical phenomena as well as qubits have limitations in terms of these performance parameters.
In this dissertation, the electronic oscillator-based Ising machine (OIM) is investigated due to its promise of CMOS compatibility, compactness, and room-temperature operation. Prior works on coupled oscillator Ising machines have focused on small-scale prototype implementations (4-8 oscillators), while larger designs have been limited to solving only planar and sparse graphs. Therefore, to establish the coupled oscillator platform as a promising candidate for realizing physical Ising machines, its scalability needs to be evaluated- which remains missing and is the primary focus of this dissertation. To accomplish this, a 672 oscillator-based Ising machine IC (65nm GP CMOS technology) with 30,896 programmable coupling elements is developed. Using this platform, a fundamental trade-off between the solution quality and the time-to-compute is experimentally revealed. Further, we evaluate methods to overcome this tradeoff and propose a hybrid (OIM + heuristic local search) approach. Our projections show that the hybrid approach offers 3-100× improvement in experimentally measured time-to-compute at iso-solution quality, compared to a digital algorithm. Finally, we expand on the dynamical system model to enable solving a broad range of problems requiring multi-valued ‘spin’ states such as the traveling salesman problem, the graph coloring problem, the Hamiltonian path/cycle problem, etc.