The deep learning and statistical physics applications to the problems of combinatorial optimization
arXiv:1911.10680
Abstract
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.
16 pages, 1 attachment
References in corpus (10)
- Solving the Quantum Many-Body Problem with Artificial Neural Networks
- Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
- Green Function Monte Carlo with Stochastic Reconfiguration
- Exact Combinatorial Optimization with Graph Convolutional Neural Networks
- Study of the Two-Dimensional Frustrated J1-J2 Model with Neural Network Quantum States
- Constructing neural stationary states for open quantum many-body systems
- Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
- Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
- Approximating power of machine-learning ansatz for quantum many-body states
- PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers