Coupled Oscillator Based Dynamical Systems to Solve Combinatorial Optimization

Despite the colossal growth in computation power fueled by digital computers, there exist many computational problems that are still considered intractable to solve using such computing platforms. As a case in point, many problems in combinatorial optimization belong to the NP-hard (non-deterministic polynomial-time hard) computational complexity class and computing their solutions on digital computers typically requires exponentially increasing resources (computing time and memory) with increasing problem size. Consequently, solving even problems of moderate size can become unmanageable. This motivates the exploration of alternative computing models that can be more efficient in solving such problems.
Analog dynamical systems as well as computational models inspired by such platforms offer a promising alternative for solving such problems. For example, Ising machines realized using coupled oscillators have been extensively investigated for accelerating hard combinatorial optimization problems. While Ising machines help showcase the potential of the dynamical system-based approach, they are constrained in their capabilities. Specifically, an Ising ‘spin’ only allows two states and the traditional Ising model can only capture quadratic interactions. However, many practical combinatorial optimization problems entail more than two states as well as higher order (>2) interactions - demands that are typically accomplished using extensive computationally intensive pre-processing, resulting in an expansion in problem size.
Therefore, in this dissertation, new coupled oscillator-inspired computational models are formulated that not only allow variables with more than two values (commonly termed as the Potts model) but also capture higher order interactions. This work advances the capabilities of the analog approach by largely circumventing the need for pre-processing required with Ising machines. Complementing this effort, the properties of such non-linear dynamical systems are analyzed from a control-theoretic viewpoint, allowing critical insights into the design and optimization of the computational properties of such systems.
Finally, to test the potential performance benefits of the models developed in this work, a 3- and 4-state Potts machine designed to solve the Max-K-Cut problem (K=3,4) is implemented on an FPGA. Evaluations performed on graphs with up to 10,000 nodes from the G-Set dataset reveal that the new models combined with the inherent parallelism incorporated in the FPGA architecture can provide a ~390x speedup over the state-of-the-art GPU-based simulated bifurcation machine.
In summary, this dissertation contributes to advancing the design and computational capabilities of analog dynamical systems as an approach for accelerating a class of computationally intractable problems.