Mean-field Approximate Optimization Algorithm for Max-q-XORSAT problems on d-regular graphs

Many NP-hard combinatorial optimization problems can be related to the classical Ising Hamiltonians whose ground state corresponds to the optimum of the problem. The Quantum Approximate Optimization Algorithm (QAOA) for solving this type of problems was suggested as a powerful diabatic alternative to the adiabatic quantum computation.

In our previous work on the Mean-Field Approximate Optimization Algorithm (MFAOA) we benchmarked it against the QAOA and we saw that it outperforms the QAOA for the Sherrington-Kirkpatrick (SK) model and the number partitioning problem where the underlying graphs are complete. In this work, we have extended our new algorithm for d-regular and q-uniform hypergraphs which represent the Max-q-XORSAT problems for d= 2.

Mean-Field Approximate Optimization Algorithm (MFAOA) can be thought of as the semi-classical counterpart of the quantum annealing. We analyzed the Gaussian quantum fluctuations around mean-field spin trajectories corresponding to the classical path and came up with a spectrum of time-dependent positive Lyapunov exponents. Analysis of the local maxima of the largest Lyapunov exponent enables one to identify the critical point of the ergodic to many-body localization phase transition in the presence of a transverse magnetic field as we have verified it from the level-spacing statistics. By processing the largest Lyapunov exponent over time we came up with a novel population annealing based recursive version of the MFAOA which runs in polynomial time $O(N⁴p)$ and improves the results significantly.