Hong, Seokmin 2025-08-20T05:05:41Z 2025-08-20T05:05:41Z 2025-08-20 2025-07 https://pubs.kist.re.kr/handle/201004/152972 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. English Institute of Electrical and Electronics Engineers Inc. Impact of Network Complexity on the Computational Performance of Ising Machines Article 10.1109/ACCESS.2025.3586179 1 IEEE Access, v.13, pp.119946 - 119953 IEEE Access 13 119946 119953 Y scie scopus 001530267800016 2-s2.0-105010122694 Computer Science, Information Systems Engineering, Electrical & Electronic Telecommunications Computer Science Engineering Telecommunications Article OPTIMIZATION Field programmable gate arrays Logic gates Stationary state Schedules Network topology Optimization Logic Complexity theory Annealing Topology Combinatorial optimization domain-specific hardware p-bits p-computer Ising machines sampling spintronics hardware accelerators massive parallelism