Spintronics-Compatible Approach to Solving Maximum-Satisfiability Problems with Probabilistic Computing, Invertible Logic, and Parallel Tempering

This work will show recent results on Ising machines (IMs) and their potential hardware implementation with spintronic technology focusing on IMs built with p-bits (probabilistic

computing). This computing paradigm is very promising to solve combinatorial optimization problems (COPs), which are a class of mathematical problems that have important applications in a variety of industrial and scientific fields, which span from logistics to geoscience, from water distribution network design to job scheduling. Many of these, such as maximum cut (Max-Cut), maximum Boolean satisfiability (max-SAT) or the travelling salesman problem, are NP- complete or NP-hard, meaning in their worst-case instances they have no polynomial-time solution. We show how the probabilistic computing can be used to solve max-sat instances (the other problems can be mapped on them) beating state-of-the art solvers having a time-to-solution to 95% at least one order of magnitude smaller. [1] [2]