Abstract: Finding the maximum cut of a graph
(MAXCUT) is a classic optimization problem that has
motivated parallel algorithm development. In this talk, I will present two neuromorphic circuits that transform a source of randomness into computationally useful correlations for approximating solutions to graph MAXCUT. Neuromorphic computing has been successfully applied to various graph algorithms, by exploiting the analogy between a graph and the connectivity of a neural circuit. However, the physical constraints of neuromorphic hardware make translating an arbitrary graph into the neuromorphic domain challenging. Neuromorphic computing is also beginning to explore stochastic devices as efficient sources of randomness for large-scale stochastic algorithms. Graph MAXCUT is a well-known NP-complete discrete optimization problem with the best-known approximate solutions being stochastic algorithms, such as the Goemans-Williamson algorithm. I will show how to combine large-scale sources of intrinsic randomness with neuromorphic principles to implement two classes of stochastic approximations to graph MAXCUT in neuromorphic hardware. These approaches have architectural advantages over other neuromorphic graph algorithms and benefit from the theoretical performance guarantees of their algorithmic inspirations. I will show results from simulations of these circuits as well as results from an implementation of one of these circuits on Intel’s Loihi neuromorphic system. This work opens a new direction for stochastic neuromorphic circuits applied to discrete optimization.