Semiclassical Approximate Optimization Algorithm

In this work, we develop a new Semiclassical Approximate Optimization Algorithm (SAOA) as a classical counterpart to the Quantum Approximate Optimization Algorithm (QAOA). This algorithm substitutes a quantum evolution of QAOA by classical spin dynamics. Within the Trotterization scheme of QAOA, this dynamics can be found exactly for any number of layers p defining the algorithm. We test SAOA for the Sherrington-Kirkpatrick (SK) model and the number partition problem - it delivers an approximated optimum with accuracy of order 1/√N or higer in a polynomial time and outperforms QAOA in these cases.

To quantify quantum fluctuations around mean-field spin trajectories we solve an effective scattering problem in time. It describes a propagation of cellective paramagnon modes above an instantaneous ground state of the adiabatic Hamiltonian H(s) and is characterized by a spectrum of positive Lyapanov exponents that depend on normalized time s∈[0,1]. The s-dependence of the largest Lyapanov exponent in the quantum SK model enables one to identify its instance specific critical point of the ergodic to many-body localization transition in the presence of a transverse magnetic field. We believe in the general applicability of SAOA for a large class of random optimization problemes defined on strongly connected graphs.