Scalable Connectivity for Ising Machines: Dense to Sparse
In recent years, hardware implementations of Ising machines have emerged as a viable alternative to quantum computing for solving hard optimization problems, among other applications. Unlike quantum hardware, dense connectivity can be achieved in classical systems; however, we show that dense connectivity leads to severe frequency slowdowns and interconnect congestion, scaling unfavorably with system size. As a scalable solution, we propose a systematic sparsification method for dense graphs by introducing copy nodes to limit the number of neighbors per graph node. In addition to solving interconnect congestion, this approach enables constant frequency scaling, where all spins in a network can be updated in constant time. Nonetheless, sparsification introduces new difficulties, such as constraint-breaking between copied spins and increased convergence times to solve optimization problems, especially if exact ground states are sought. Relaxing the exact-solution requirements, we find that the overheads in convergence times are milder. We demonstrate these ideas by designing probabilistic bit Ising machines using ASAP7 (a predictive 7-nm fin field-effect-transistor technology model) process design kits as well as field-programmable-gate-array-based implementations. Finally, we show how formulating problems in naturally sparse networks (e.g., by invertible logic) sidesteps challenges introduced by sparsification methods. Our results are applicable to a broad family of Ising machines using different hardware implementations.