An improved update rule for probabilistic computers

Abstract

Many hard combinatorial problems can be mapped onto Ising models, which replicate the behavior of classical spins. Recent advances in probabilistic computers are characterized by parallelization and the introduction of novel hardware platforms. An interesting application of probabilistic computers is to operate them in `reverse' mode, where the network self-organizes its behavior to find the input bits that result in an output state. This can be used, for example, as a factorizer of semiprimes. One issue with simulating probabilistic computers on standard logic devices, such as field-programmable gate arrays, is that the update rules for each spin involve many multiplications, evaluation of a hyperbolic tangent, and a high-resolution numerical comparison. We simplify these rules, which improves the spatial and temporal circuit complexity when simulating a probabilistic computer on a field-programmable gate array. Applying our method to factorizing semiprimes, we achieve at least an order-of-magnitude reduction in the on-chip resources and the time-to-solution compared to recently reported methods. For a 32-bit semiprime, we achieve an average factorization in $\sim$100 s. Our approach will inspire new physical realizations of probabilistic computers because we relax some of their update-rule requirements.

11 pages, 11 figures

References in corpus (11)

• Parallel Tempering: Theory, Applications, and New Perspectives
• Quantum error correction below the surface code threshold
• Stochastic p-bits for Invertible Logic
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Weighted p-bits for FPGA implementation of probabilistic circuits
• Autonomous Probabilistic Coprocessing with Petaflips per Second
• Ultra-Fast Physical Generation of Random Numbers Using Hybrid Boolean Networks
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Probabilistic Circuits for Autonomous Learning: A simulation study
• Scalable Connectivity for Ising Machines: Dense to Sparse
• Ground-State Probabilistic Logic with the Simplest Binary Energy Landscape for Probabilistic Computing