2019/05/16 by M. B. Hastings, Hastings, M. B. · 12 citations
Computer Science · Decision Sciences · Mathematics · Physics and Astronomy · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.1905.07047
17 pages, 8 figures; v2 minor typo corrections
openalex publication_date 2019/05/16 · arxiv created 2019/08/01 · arxiv updated 2019/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.