The deep learning and statistical physics applications to the problems of combinatorial optimization

Semyon Sinchenko, Dmitry Bazhanov

Published 2019-11-16Version 1

We present herein a new approach based on the simultaneous application of the deep learning and statistical physics methods to solve the combinatorial optimization problems. The recent modern advanced techniques, such as an artificial neural network, demonstrate their efficiency for solving various physical tasks for the quantum many-body systems, which may be related directly to the problems of combinatorial optimization. One of them is a classical Maximum Cut (MaxCut) problem, which we ascribe here to the search of the ground state of a quantum many-body system using an artificial neural network and deep learning. We found that the exact solution received for a quantum system corresponds to its counterpart in a classical MaxCut problem. As a proof, we have realized our approach for two random graphs of different size, containing 60 vertices (885 edges) and 100 vertices (2475 edges), and achieved for them the total performances p60~0.99 and $p100~0.97 of known maximal cuts, respectively.