  Domain-specific hardware to solve computationally hard optimization problems
has generated tremendous excitement recently. Here, we evaluate probabilistic
bit (p-bit) based on Ising Machines (IM) or p-computers with a benchmark
combinatorial optimization problem, namely the 3-regular 3-XOR Satisfiability
(3R3X). The 3R3X problem has a glassy energy landscape, and it has recently
been used to benchmark various IMs and other solvers. We introduce a
multiplexed architecture where p-computers emulate all-to-all (complete) graph
functionality despite being interconnected in sparse networks, enabling a
highly parallelized chromatic Gibbs sampling. We implement this architecture in
FPGAs and show that p-bit networks running an adaptive version of the powerful
parallel tempering algorithm demonstrate competitive algorithmic and prefactor
advantages over alternative IMs by D-Wave, Toshiba, and Fujitsu, except a
greedy algorithm accelerated on a GPU. We further extend our APT results using
higher-order interactions in FPGAs and show that while higher-order
interactions lead to prefactor advantages, they do not show any algorithmic
scaling advantages for the XORSAT problem, settling an open conjecture. Even
though FPGA implementations of p-bits are still not quite as fast as the best
possible greedy algorithms implemented in GPUs, scaled magnetic versions of
p-computers could lead to orders of magnitude over such algorithms according to
experimentally established projections.
