Abstract
We obtain worst-case performance guarantees for and 3 QAOA for MaxCut on uniform 3-regular graphs. Previous work by Farhi et al. obtained a lower bound on the approximation ratio of 0.692 for . We find a lower bound of 0.7559 for , where worst-case graphs are those with no cycles . This bound holds for any 3-regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all , where worst-case graphs have with no cycles . Under this conjecture, the approximation ratio is at least 0.7924 for all 3-regular graphs and . In addition, using an indistinguishable argument we find an upper bound on the worst-case approximation ratio for all , which indicates classes of graphs for which there can be no quantum advantage for at least .
6 More- Received 4 February 2021
- Accepted 14 April 2021
DOI:https://doi.org/10.1103/PhysRevA.103.042612
©2021 American Physical Society