The geometry and dynamics of annealed optimization in the coherent Ising machine with hidden and planted solutions

The coherent Ising machine (CIM) is a nonconventional hardware architecture for finding approximate solutions to large-scale combinatorial optimization problems by adiabatically deforming a high dimensional energy landscape over a set of soft spins. We address how the evolving energy landscapes guides the optimization dynamics against problems with hidden planted solutions. We study the Sherrington-Kirkpatrick spin-glass with ferromagnetic couplings that favor a hidden configuration. We combine the replica method, random matrix theory, the Kac-Rice method to characterize location, energy and Hessian eigenspectra of global and local minima. We develop a dynamical mean field theory to study the annealed optimization dynamics. We find that low energy and global minima develop soft modes which the dynamics exploits to descend the energy landscape. Even when these global minima are aligned to the hidden configuration, there can be exponentially many higher energy local minima that are all unaligned with the hidden solution, which are avoided by the dynamics. Eventually, as the landscape is further annealed, low energy minima become rigid, terminating any further optimization gains from annealing.