2023/05/15 by Tong Guanchun, Michael Muehlebach, Guanchun, Tong +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Quantum Computing Algorithms and Architecture #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2305.08536
openalex publication_date 2023/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We discuss a dynamical systems perspective on discrete optimization. Departing from the fact that many combinatorial optimization problems can be reformulated as finding low energy spin configurations in corresponding Ising models, we derive a penalized rank-two relaxation of the Ising formulation. It turns out that the associated gradient flow dynamics exactly correspond to a type of hardware solvers termed oscillator-based Ising machines. We also analyze the advantage of adding angle penalties by leveraging random rounding techniques. Therefore, our work contributes to a rigorous understanding of oscillator-based Ising machines by drawing connections to the penalty method in constrained optimization and providing a rationale for the introduction of sub-harmonic injection locking. Furthermore, we characterize a class of coupling functions between oscillators, which ensures convergence to discrete solutions. This class of coupling functions avoids explicit penalty terms or rounding schemes, which are prevalent in other formulations.