Performance and limitations of the QAOA at constant levels on different problems

The Quantum Approximate Optimization Algorithm (QAOA) is a general

purpose quantum algorithm designed for combinatorial optimization. We

analyze its expected performance and prove concentration properties at

any constant level (number of layers) on ensembles of random

combinatorial optimization problems in the infinite size limit. These

ensembles include mixed spin models and Max-q-XORSAT on sparse random

hypergraphs. We then show that the performance of the QAOA at constant

levels for the pure q-spin model matches asymptotically the ones for

Max-q-XORSAT on random sparse Erdos-Renyi hypergraphs and every

large-girth regular hypergraph. Through this correspondence, we

establish that the average-case value produced by the QAOA at constant

levels is bounded away from optimality for pure q-spin models when q ≥

4 and is even. This limitation gives a hardness of approximation

result for quantum algorithms in a new regime where the whole graph is

seen. Furthermore, we also derive analytical expressions for the

performance of the QAOA on the spiked tensor model at low-depth and

compare it to the classical power iteration method, shedding

additional light on the comparative power of classical and quantum

algorithms for optimization.