As discussed in Section , the coloring is used to exploit the trick that allows the parallel update of unconnected (conditionally independent) p-bits. We first color the graph using a heuristic graph coloring algorithm DSATUR [1]}. Coloring a graph with exactly the minimum number of colors is NP-hard [2]}. However, this is unimportant for our purposes since we use DSATUR as an efficient (polynomial) coloring algorithm, which may or may not find the optimum coloring. We find that as long as the starting graph is sparse only a few colors are needed for the invertible logic problems we have considered. For example, for the 8-bit factorizer graph only five colors are used and as a result, we need five parallel and equally phase-shifted clocks in the sIM (Fig. REF d). The equal phase shift is required to avoid any concurrent edges of the clocks. In our architecture (Supplementary Information, Fig. REF b,c), different color blocks receive different clocks to their RNGs, ensuring no two connected p-bits flip at the same time for exact Gibbs sampling. This is a constraint we relax in Section .
