Impact of Network Complexity on the Computational Performance of Ising Machines

Abstract

Recent demonstrations of massively parallel probabilistic computing have shown a practical route to tackling computationally hard problems in various combinatorial optimizations, with impressive performance that can be further accelerated using emerging devices. A technique known as network sparsification has been adopted and adapted for hardware implementation, transforming dense networks into sparse ones by introducing additional nodes or p-bits. Here, we present the impact of network complexity on Boolean SATisfiability (SAT) and integer factorization problems using a more conventional compact network, as well as corresponding dense and sparse networks encoded with invertible logic. These networks are evaluated through both CPU-based simulations and prototyped hardware implementations on a Field-Programmable Gate Array (FPGA) with up to 1935 nodes. Among various network topologies, the success probability of finding optimal solutions using standard simulated annealing generally decreases with the addition of nodes, as expected, and several orders of magnitude more Markov Chain Monte Carlo (MCMC) samples are required to achieve comparable performance in larger networks. Graph sparsification provides a useful means of adjusting network complexity for practical and scalable applications with moderate computational overhead. However, its benefits should be weighed against those of optimized network connections, as the search space increases exponentially with the introduction of auxiliary nodes.