  Given the fundamental importance of combinatorial optimization across many
diverse application domains, there has been widespread interest in the
development of unconventional physical computing architectures that can deliver
better solutions with lower resource costs. These architectures embed discrete
optimization problems into the annealed, analog evolution of nonlinear
dynamical systems. However, a theoretical understanding of their performance
remains elusive, unlike the cases of simulated or quantum annealing. We develop
such understanding for the coherent Ising machine (CIM), a network of optical
parametric oscillators that can be applied to any quadratic unconstrained
binary optimization problem. Here we focus on how the CIM finds low-energy
solutions of the Sherrington-Kirkpatrick spin glass. As the laser gain is
annealed, the CIM interpolates between gradient descent on the soft-spin energy
landscape, to optimization on coupled binary spins. By exploiting spin-glass
theory, we develop a detailed understanding of the evolving geometry of the
high-dimensional CIM energy landscape as the laser gain increases, finding
several phase transitions, from flat, to rough, to rigid. Additionally, we
develop a cavity method that provides a precise geometric interpretation of
supersymmetry breaking in terms of the response of a rough landscape to
specific perturbations. We confirm our theory with numerical experiments, and
find detailed information about critical points of the landscape. Our extensive
analysis of phase transitions provides theoretically motivated optimal
annealing schedules that can reliably find near-ground states. This analysis
reveals geometric landscape annealing as a powerful optimization principle and
suggests many further avenues for exploring other optimization problems, as
well as other types of annealed dynamics, including chaotic, oscillatory or
quantum dynamics.
