Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond

Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019], we study the limitations of the Quantum Approximate Optimization Algorithm (QAOA) and show that there exists $\epsilon > 0$, such that $\epsilon\log(n)$ depth QAOA cannot arbitrarily-well approximate boolean constraint satisfaction problems as long as the problem satisfies a combinatorial property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random \kxors{} problem has this property when $k\geq4$ is even by extending the corresponding result for diluted $k$-spin glasses. As a consequence of our techniques, we confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth -- in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. Our results provide a new way to study the power and limit of QAOA through statistical physics methods and combinatorial properties.