Precision meets speed through an FPGA-based natively sparse Ising machine for combinatorial optimization

Ising machines constitute a framework to solve combinatorial optimization problems efficiently utilizing dynamical interacting systems. Typical approaches simulate the dynamics on digital hardware, which is strongly dependent on matrix-vector operations, and were shown to experience acceleration of several orders of magnitude by parallel processing on FPGAs. However, optimization on single FPGAs has remained limited to small-scale problems due to memory limitations, and multi-FPGA networks are challenging to operate. In this work, we propose a high-accuracy and FPGA-based Ising machine design that achieves state-of-the-art solution speeds on integrated hardware and is scalable to problems of up to 20,000 variables on a single FPGA unit. Concretely, we introduce a sparse data format, called tiled coordinate list, for more efficient memory use and fast matrix-vector operations. Further, we propose a quantization mechanism to 8-bit integer precision that allows problem sizes to be scaled without reducing the accuracy of the solution. Co-optimization of the data flow and hardware design strongly accelerates the Ising machine while reducing computational costs. This enables 10- to 68-fold speedups on Max-Cut problems from the Gset graph collection compared to previous state-of-the-art FPGA-based Ising machines.