Researchers from the Hong Kong University of Science and Technology and Huawei Technologies have designed an FPGA-based sparse Ising machine that solves combinatorial optimization problems up to 68 times faster than previous FPGA implementations, by doing something surprisingly straightforward: treating sparse problems as sparse.
The study, published in Nature Communications, targets the Max-Cut problem, an NP-hard combinatorial optimization task where the goal is to partition the vertices of a graph into two sets such that the number of edges crossing the partition is maximized. Max-Cut has applications in circuit design, statistical physics, and machine learning, and belongs to the same class of problems that Ising machines are designed to accelerate.
The sparsity insight
Real-world Max-Cut graphs are typically sparse; they have relatively few edges compared to the number of nodes. But previous FPGA-based Ising machines treated them as dense, wasting on-chip memory on zero entries and limiting the problem size that could fit on a single chip.
The team introduced a tiled coordinate list (TCOO) data format, which groups nonzero entries into fixed-size tiles that align with the FPGA’s on-chip block RAM (BRAM/URAM) architecture. This enables efficient sparse matrix-vector multiplication directly on the FPGA without streaming overhead, exploiting the native sparsity of the problem.
Combined with 8-bit integer quantization, cutting memory footprint by a factor of four compared with conventional 32-bit floating-point, the design allows up to 20,000 variables to fit on a single FPGA chip without degrading solution quality.
Performance
On the Gset graph collection, a standard Max-Cut benchmark, the design achieved a 10- to 68-fold speedup over prior state-of-the-art FPGA-based Ising machines. No multi-FPGA networks or GPU clusters were needed; the entire computation ran on a single chip.
The team, led by Baijian Yao, Xu Shi, and Wei Zhang at HKUST, with Daniel Ebler, Juntao Wang, Fan Zhang, and Jie Sun at Huawei Technologies, designed the hardware and software jointly. Data flow, pipeline architecture, and memory hierarchy were co-optimized to minimize latency and maximize throughput.
The result is the first FPGA-based Ising machine capable of handling 20,000 spins on a single chip, a scale that previously required multi-FPGA or GPU-based systems.
Sources:
1. Yao B, Shi X, Zhang W, Ebler D, Wang J, Zhang F, Sun J. “Precision meets speed through an FPGA-based natively sparse Ising machine for combinatorial optimization.” Nature Communications. 2026. DOI: 10.1038/s41467-026-75119-0