Using continuation methods to analyse the difficulty of problems solved by Ising machines
Jacob Lamers, Guy Verschaffelt, Guy Van der Sande · Communications Physics · 2024
Ising machines are dedicated hardware solvers of NP-hard optimization problems. However, they do not always find the most optimal solution. The probability of finding this optimal solution depends on the problem at hand. Using continuation methods, we show that this is closely linked to how the ground state emerges from other states when a system parameter is changed, i.e. its bifurcation sequence. From this analysis, we can determine the effectiveness of solution schemes. Moreover, we find that the proper choice of implementation of the Ising machine can drastically change this bifurcation sequence and therefore vastly increase the probability of finding the optimal solution. Lastly, we also show that continuation methods themselves can be used directly to solve optimization problems. An Ising machine is a piece of hardware that tries to solve quadratic unconstrained binary optimization problems. The authors explain why some problems are significantly easier to tackle than others using Ising machines and demonstrate that different physical implementations can render some challenging problems a lot easier to solve.