@article{hastings2018classical,
author = {Hastings, Matthew},
title = {Classical and quantum bounded depth approximation algorithms},
year = {2018},
month = {December},
abstract = {We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of "local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of "global" classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.},
url = {http://approjects.co.za/?big=en-us/research/publication/classical-and-quantum-bounded-depth-approximation-algorithms/},
pages = {1116-1140},
journal = {2019 Quantum Information & Computation},
volume = {19},
}