  Inspired by the developments in quantum computing, building domain-specific
classical hardware to solve computationally hard problems has received
increasing attention. Here, by introducing systematic sparsification
techniques, we demonstrate a massively parallel architecture: the sparse Ising
Machine (sIM). Exploiting sparsity, sIM achieves ideal parallelism: its key
figure of merit - flips per second - scales linearly with the number of
probabilistic bits (p-bit) in the system. This makes sIM up to 6 orders of
magnitude faster than a CPU implementing standard Gibbs sampling. Compared to
optimized implementations in TPUs and GPUs, sIM delivers 5-18x speedup in
sampling. In benchmark problems such as integer factorization, sIM can reliably
factor semiprimes up to 32-bits, far larger than previous attempts from D-Wave
and other probabilistic solvers. Strikingly, sIM beats competition-winning SAT
solvers (by 4-700x in runtime to reach 95% accuracy) in solving 3SAT problems.
Even when sampling is made inexact using faster clocks, sIM can find the
correct ground state with further speedup. The problem encoding and
sparsification techniques we introduce can be applied to other Ising Machines
(classical and quantum) and the architecture we present can be used for scaling
the demonstrated 5,000-10,000 p-bits to 1,000,000 or more through analog CMOS
or nanodevices.
