Publications and Research

Document Type

Article

Publication Date

2022

Abstract

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.

Comments

This work was originally published as: Honari-Latifpour, Mostafa, Matthew S. Mills, and Mohammad-Ali Miri. "Combinatorial Optimization with Photonics-Inspired Clock Models." Communications Physics, vol. 5, no. 104, 2022, doi: .1038/s42005-022-00874-7 |

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.