A Reconfigurable Potts Machine with Successive Boundary Approximation Annealing for Solving Combinatorial Optimization Problems

The Ising machines based on simulated-annealing algorithm have gained increasing attention for solving combinatorial optimization problems (COPs) with applications in logistics management, communication networking, medical diagnosis and financial optimization. By mapping a COP to the Ising model with spin network, the machine naturally tends to search for its lowest energy by iteratively updating spin states. The Potts model is a generalization of the Ising model [1], where the spin states are a set of discrete values instead of +1 and -1, as shown in Fig. 1 (top). It can provide a more natural representation of many COPs such as graph clustering and graph coloring, making it straightforward in hardware embedding and more efficient in finding the optimal solutions. The challenge of solving the Potts model mainly relies on the exponential increase in computational resources with the increase of spin state number and problem size. In addition, due to the complicated topology connection between each spin, a large amount of memory is required for storing their interaction coefficients.