Ising Machines Using Parallel Spin Updating Algorithms for Solving Traveling Salesman Problems

As a type of physics-inspired computation, Ising computing has raised an ever-growing interest in solving problems in non-deterministic polynomial (NP) complexity classes with polynomial time. As an NP-hard problem, the traveling salesman problem (TSP) plays an important role in various routing and scheduling applications. However, the execution speed and solution quality significantly deteriorate using a solver with simulated annealing (SA) due to the quadratically increasing number of spins and strong constraints placed on the spins. In this chapter, we present two improved algorithms based on momentum annealing and simulated bifurcation for fully connected Ising machines, which can realize parallel updating of spin states. Due to the massive parallel processing capacity, the algorithms can solve the TSP with an improvement in the solution quality with shorter runtime than using SA methods.