Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches.
In particular, they state in the discussion:
"More generally, however, the results here point to a pattern. It seems like the QAOA is simply a way of writing a quantum circuit which does something similar to a very simple classical algorithm: initialize spins in some configuration and then update spins depending on those around it. For a one-step version of the algorithm, the update is usually very simple: if the spins around it apply a strong enough force to the given spin, then it changes in a way to increase the objective function. To the extent that the QAOA works, it seems that it works because the classical algorithm works; there does not seem to be any general explanation in the literature as to why such a quantum circuit should be better than such a classical algorithm."
Caveat: I'm just coming to understand QAOA. That said, from my reading of the paper, it seems that the 'local' QAOA approaches discussed don't yield better approximation bounds than the comparable classical heuristics. Indeed, the authors appear to indicate that classical approaches may be better in some respects given the additional guarantees they can offer. Of course, QAOA can be applied to multiple optimization problems, so this may not be generalizable. Further, even the global QAOA doesn't appear to do much better – with classical approaches still offering better approximation.
Thus, my question is: Given our current understanding of quantum algorithms and the approaches they enable, can quantum approaches (like QAOA) yield provably better approximation bounds than classical algorithmic approaches on optimization problems?
Any specific example of a quantum approach with a known better approximation bound would be great; even better would be a complexity argument demonstrating that a quantum model of computation can enable better approximation than classical models.