MaxCut quantum approximate optimization algorithm performance guarantees for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>></mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math>
Jonathan Wurtz, Peter J. Love
Abstract
We obtain worst-case performance guarantees for $p=2$ 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 $p=1$. We find a lower bound of 0.7559 for $p=2$, where worst-case graphs are those with no cycles $\ensuremath{\le}5$. This bound holds for any 3-regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all $p$, where worst-case graphs have with no cycles $\ensuremath{\le}2p+1$. Under this conjecture, the approximation ratio is at least 0.7924 for all 3-regular graphs and $p=3$. In addition, using an indistinguishable argument we find an upper bound on the worst-case approximation ratio for all $p$, which indicates classes of graphs for which there can be no quantum advantage for at least $p<6$.