Physical Review X · 2024 · 11 citations · 92 references
Natural SciencesComputer SciencePhysicsComputational PhysicsCondensed Matter PhysicsQuantum MechanicsEnergy MinimizationOptical ResonatorsPhase TransitionsSymmetry BreakingEnergy Landscape TheoryGradient DescentIsing ModelOptical Parametric OscillatorsParametric OscillatorsQuadratic OptimizationSpin Glass BehaviorSpin Glasses
Given the fundamental importance of combinatorial optimization across many diverse domains, there has been widespread interest in the development of unconventional physical computing architectures that can deliver better solutions with lower resource costs. However, a theoretical understanding of their performance remains elusive. We develop such understanding for the case of the coherent Ising machine (CIM), a network of optical parametric oscillators that can be applied to any quadratic unconstrained binary optimization problem. We focus on how the CIM finds low-energy solutions of the Sherrington-Kirkpatrick spin glass. As the laser gain of this system is annealed, the CIM interpolates between gradient descent on coupled soft spins to descent on coupled binary spins. By combining the Kac-Rice formula, the replica method, and supersymmetry breaking, we develop a detailed understanding of the evolving geometry of the high-dimensional energy landscape of the CIM as the laser gain increases, finding several phase transitions in the landscape, from flat to rough to rigid. Additionally, we develop a novel cavity method that provides a geometric interpretation of supersymmetry breaking in terms of the reactivity of a rough landscape to specific external perturbations. Our energy landscape theory successfully matches numerical experiments, provides geometric insights into the principles of CIM operation, and yields optimal annealing schedules. Published by the American Physical Society 2024
92
Solvable Model of a Spin-Glass
David C. Sherrington, Scott Kirkpatrick · Physical Review Letters · 1975 · 4.3K citations
The Kuramoto model: A simple paradigm for synchronization phenomena
Juan A. Acebrón, L. L. Bonilla, C. J. Pérez Vicente et al. · Reviews of Modern Physics · 2005 · 3.5K citations · Full text
Natural Sciences, Biology, Physics +16
Ising formulations of many NP problems
Andrew Lucas · Frontiers in Physics · 2014 · 2.5K citations · Full text
Computing, Computer Science, Physics +15