Hardware Acceleration of Probabilistic Computing for Max-Cut Problems

Abstract

Probabilistic-bit (p-bit)-based computing provides a hardware-friendly framework for solving combinatorial optimization and sampling problems by exploiting stochastic binary dynamics. However, the practical performance of p-bit systems depends not only on the optimization algorithm, but also on the underlying hardware architecture and graph connectivity. In this paper, we present a systematic cross-platform evaluation of p-bit-based Max-Cut solvers on CPU, GPU, and FPGA platforms under a common computational framework. Using representative Gset benchmark instances with random, toroidal, and planar topologies, we implement and evaluate simulated annealing, parallel tempering, and population annealing algorithms. We further introduce a connectivity-aware throughput metric based on the maximum node degree to account for topology-dependent synaptic workloads and enable more meaningful comparisons across graph structures. The GPU implementation exploits massive replica-level parallelism, whereas the FPGA implementation achieves high raw flip rates through a customized p-bit architecture. Experimental results show that the proposed implementations achieve competitive solution quality, including a new best-known cut value for a large-scale instance. These findings clarify the algorithm–architecture tradeoffs in p-bit-based optimization and provide design guidelines for scalable probabilistic accelerators.