Combinatorial optimization with photonics-inspired clock models

Mostafa Honari-Latifpour

doi:10.1038/s42005-022-00874-7

2022-04-29

Mostafa Honari-Latifpour

Matthew S. Mills

Mohammad‐Ali Miri *

DOI：10.1038/s42005-022-00874-7

原文链接

原文求助

摘要

En 中文

NP-hard combinatorial optimization problems are in general hard problems that their computational complexity grows faster than polynomial scaling with the size of the problem. Thus, over the years there has been a great interest in developing unconventional methods and algorithms for solving such problems. Here, inspired by the nonlinear optical process of q-photon down-conversion, in which a photon is converted into q degenerate lower energy photons, we introduce a nonlinear dynamical model that builds on coupled single-variable phase oscillators and allows for efficiently approximating the ground state of the classical q-state planar Potts Hamiltonian. This reduces the exhaustive search in the large discrete solution space of a large class of combinatorial problems that are represented by the Potts Hamiltonian to solving a system of coupled dynamical equations. To reduce the problem of trapping into local minima, we introduce two different mechanisms by utilizing controlled chaotic dynamics and by dynamical formation of the cost function through adiabatic parameter tuning. The proposed algorithm is applied to graph-q-partitioning problems on several complex graphs. Physics-inspired algorithms are being developed to solve NP-hard problems while alleviating issues with scaling and trapping in local minima. Here, a method to search the global minimum of the Potts Hamiltonian with a photonic-inspired model is proposed.

Keyword:

NEURAL-NETWORK MODEL

ADIABATIC EVOLUTION