Restoring Sparsity in Potts Machines via Mean-Field Constraints
For practitioners using probabilistic hardware for constrained optimization, this work provides methods to maintain sparsity and scalability, with significant speedups demonstrated on FPGA.
The paper addresses the problem of dense couplings in Ising machines for constrained optimization, introducing a native formulation for multi-state probabilistic digits and mean-field constraints to restore sparsity. Applied to balanced graph partitioning, their FPGA implementation achieves over 10x speedup over CPU probabilistic solvers and over 100x over a Tabu Ising baseline.
Ising machines and related probabilistic hardware have emerged as promising platforms for NP-hard optimization and sampling. However, many practical problems involve constraints that induce dense or all-to-all couplings, undermining scalability and hardware efficiency. We address this constraint-induced density through two complementary approaches. First, we introduce a hardware-aware native formulation for multi-state probabilistic digits (p-dits) that avoids the locally dense intra-variable couplings required by binary Ising encodings. We validate p-dit dynamics by reproducing known critical behavior of the 2D Potts model. Second, we propose mean-field constraints (MFC), a hybrid scheme that replaces dense pairwise constraint couplings with dynamically updated single-node biases. Applied to balanced graph partitioning, MFC achieves solution quality comparable to exact all-to-all constraint formulations while dramatically reducing graph density. Finally, we demonstrate the practical impact of restored sparsity through an FPGA implementation that accelerates partitioning by more than an order of magnitude over CPU probabilistic solvers and by over two orders of magnitude over a Tabu Ising baseline. Together, these results outline a pathway for scaling constrained optimization on probabilistic hardware.