Parametric Oscillator Networks Naturally Implement the Lagrange Multiplier Primal-Dual Algorithm for Combinatorial Optimization Problems

Coupled parametric oscillator networks such as the Coherent Ising Machine generated significant recent interest because of their observed ability to rapidly produce high-quality solutions to NP-hard optimization problems. While prior literature often derives the dynamics of such systems, it hasn't explained why exactly the dynamics perform optimization so well. We present a previously unrecognized precise mathematical equivalence between parametric oscillator network dynamics and the primal-dual method of Lagrange multipliers that (1) lucidly explains how coupled oscillator solvers implement the correct optimization constraints and find high-quality solutions, (2) provides precise mathematical meaning to each physical component, (3) and enables theoretically-supported design of systems that implement more sophisticated optimization algorithms; we give one such design example. Our simulated system performance (a) is competitive with the best-known digital algorithms and, (b) is robust to large hardware component variations. We believe this fundamental interdisciplinary connection between physics and theoretical optimization will open the doors to future work on principled physical implementation of complex optimization algorithms for resource-intensive applications such as machine learning.