A Comparison of Energy Minimization Algorithms for Solving Max-Sat Problem with Probabilistic Ising Machines

Ising machines are one of the most promising unconventional computing paradigms in the field of combinatorial optimization. Several ways of employing the Ising model were devised in the latest years and, among them, probabilistic computing with p-bits stands out for its high hardware compatibility and remarkable performance. One of the key elements of the solving process of a given instance of a problem is the energy minimization algorithm used. In this work, classical annealing (CA), parallel tempering (PT), and simulated quantum annealing (SQA) are compared over the same instance of a maximum satisfiability problem. The results show that, for a high number of replicas, SQA performs better than the other two algorithms. Conversely, with contained number of replicas, CA and PT are comparable in performance between each other and both are superior to SQA. Those results call for the development of platforms/protocols where to compare and potentially combine those annealing approaches.