Limitations of quantum approximate optimization in solving generic higher-order constraint-satisfaction problems

The ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put into doubt. Here we analyze the QAOA's performance on random Max-<a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:mi>k</a:mi><a:mtext>XOR</a:mtext></a:math> as a function of <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mi>k</b:mi></b:math> and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"><c:mi>k</c:mi></c:math> and numbers of layers <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"><d:mi>p</d:mi></d:math>, there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"><e:mi>p</e:mi></e:math>, which must be considered rather difficult both in the variational context and on near-term devices.