Abstract
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of randomized classical algorithms.
1) We prove that every (quantum or classical) onelocal algorithm (where the value of a vertex only depends on its and its neighbors' state) achieves on Dregular graphs of girth > 5 a maximum cut of at most 1/2 + C/√D for C = 1/√2 ≈ 0.7071. This is the first such result showing that onelocal algorithms achieve a value that is bounded away from the true optimum for random graphs, which is 1/2 + P_*/√D + o(1/√D) for P_* ≈ 0.7632 [Dembo et al., 2017].
2) We show that there is a classical klocal algorithm that achieves a value of 1/2 + C/√D  O(1/√k) for Dregular graphs of girth > 2k+1, where C = 2/π ≈ 0.6366. This is an algorithmic version of the existential bound of [Lyons, 2017] and is related to the algorithm of [Aizenman et al., 1987] (ALR) for the SherringtonKirkpatrick model. This bound is better than that achieved by the onelocal and twolocal versions of QAOA on highgirth graphs [M. B. Hastings, 2019; Marwaha, 2021].
3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constantlocality QAOA for random Dregular graphs, as well as other natural instances, including graphs that do have short cycles.
While our theoretical bounds require the locality and girth assumptions, our experimental work suggests that it could be possible to extend them beyond these constraints. This points at the tantalizing possibility that O(1)local quantum maximumcut algorithms might be pointwise dominated by polynomialtime classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality on every possible instance. This is in contrast to the evidence that polynomialtime algorithms cannot simulate the probability distributions induced by local quantum algorithms.
BibTeX  Entry
@InProceedings{barak_et_al:LIPIcs.ITCS.2022.14,
author = {Barak, Boaz and Marwaha, Kunal},
title = {{Classical Algorithms and Quantum Limitations for Maximum Cut on HighGirth Graphs}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {14:114:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15610},
URN = {urn:nbn:de:0030drops156105},
doi = {10.4230/LIPIcs.ITCS.2022.14},
annote = {Keywords: approximation algorithms, QAOA, maximum cut, local distributions}
}
Keywords: 

approximation algorithms, QAOA, maximum cut, local distributions 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 
Supplementary Material: 

Software: https://tiny.cc/QAOAvsALR 