The organization of this paper is as follows: Section  shows how any combinatorial optimization problem can be converted to an invertible probabilistic circuit (p-circuit) using the basic building blocks (AND, OR, NOT, Full Adder) with compact interconnection matrices and discrete weights. We illustrate in Section  how a given sparse p-circuit can be colored with a few colors using an approximate graph coloring algorithm, DSATUR [1]}. We elaborate on the details of the hardware architecture implementing the coupled equations and propose further sparsification techniques to overcome the limitations of high fan-out circuits. Next, we report our experimental results on the problem of integer factorization and the Boolean satisfiability problem in Sections - as well as detailed comparisons of the sIM with respect to CPU, GPU and TPU implementations of MCMC.
<FIGURE>