Abstract
Ising machines—dynamical systems that operate in parallel and iteratively—have emerged as a promising paradigm for solving combinatorial optimization problems. Despite their computational advantages, solution quality depends strongly on the choice of dynamics and parameter tuning, which are typically selected heuristically due to limited systematic understanding.
This thesis develops general theoretical frameworks for a broad class of Ising machines, encompassing phase diagrams, optimal dynamical trajectories, and algorithmic complexity analyses. These results provide principled guidance for architecture design and parameter tuning. They also uncover the fundamental exploratory mechanisms that govern Isingmachine behavior and demonstrate their advantages.
In the first part of the thesis, we perform an equilibrium analysis on Ising machines by characterizing phase diagrams of spin distributions in the Sherrington-Kirkpatrick model. We show that the ground state is achieved in the phase where the spin distribution becomes binary, and that optimal solutions arise where the binary and gapless phases coexist. Our analysis further shows that this coexistence region can be expanded by carefully introducing a digitization operation, yielding a family of superior Ising machines, exemplified by the proposed algorithm referred as digCIM.
In the second part, we develop a dynamical mean-field framework to analyze Isingmachine dynamics and identify mechanisms enabling rapid convergence to near-optimal energies. For a fixed near-optimal target energy density Ec, we show that solutions are typically reached within time complexity O(N2), indicating an algorithmic advantage. Building on these insights, we propose a general framework for designing optimized parameter schedules, thereby improving the practical effectiveness of Ising machines for complex optimization tasks.