论文标题
Maxcut QAOA性能保证P> 1
MAXCUT QAOA performance guarantees for p >1
论文作者
论文摘要
我们在均匀的3个规范图上获得了$ P = 2 $的最差案例性能保证和$ 3 $ QAOA。 Farhi等人的先前工作获得了$ p = 1 $的近似值0.692 $的下限。我们发现$ p = 2 $的$ 0.7559 $的下限，其中最坏的情况是没有循环的$ \ leq 5 $。该界限适用于以特定固定参数评估的任何3个常规图。我们猜想了所有$ p $的层次结构，其中最坏的情况图没有循环$ \ leq 2p+1 $。在此猜想下，所有3个常规图的近似值至少为$ 0.7924 $，$ p = 3 $。此外，使用一个简单的不可区分性参数，我们在所有$ p $的最坏情况下近似率上找到了上限，这表明图形类别至少$ p <6 $没有量子优势。
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 $\leq 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 $\leq 2p+1$. Under this conjecture, the approximation ratio is at least $0.7924$ for all 3 regular graphs and $p=3$. In addition, using a simple indistinguishability 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$.
