论文标题
量子近似优化算法需要查看整个图：最坏情况示例
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
论文作者
论文摘要
量子近似优化算法可以应用于具有与边缘相对应的项的成本函数的图表上的搜索问题。在结合边缘术语时，QAOA在深度p处统一会产生一个仅取决于由边缘组成的子图的操作员，最多由P远离有关边缘的边缘组成。在随机的d-regular图中，固定和p的恒定时间log n几乎是所有树木，因此QAOA的性能仅取决于它在树中间的边缘的作用。两分的随机d指标图和一般的随机d-regular图在本地都是树，因此这两个合奏在这两个合奏中的性能是相同的。使用此功能，我们可以证明，对于任何$ a <1 $，具有$（d-1）^{2p} <n^a $的QAOA只能在双分裂的随机d-regular d-regular Graphs上达到1/2的近似值。对于最大独立集，在相同的设置中，最佳近似值比是D依赖性常数，随着D变大，为0。
The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. When conjugating an edge term, the QAOA unitary at depth p produces an operator that depends only on the subgraph consisting of edges that are at most p away from the edge in question. On random d-regular graphs, with d fixed and with p a small constant time log n, these neighborhoods are almost all trees and so the performance of the QAOA is determined only by how it acts on an edge in the middle of tree. Both bipartite random d-regular graphs and general random d-regular graphs locally are trees so the QAOA's performance is the same on these two ensembles. Using this we can show that the QAOA with $(d-1)^{2p} < n^A$ for any $A<1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large. For Maximum Independent Set, in the same setting, the best approximation ratio is a d-dependent constant that goes to 0 as d gets big.
