论文标题
量子近似优化算法需要查看整个图：典型情况
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
论文作者
论文摘要
量子近似优化算法自然可以应用于图表上的搜索问题。量子电路具有尊重图形位置的单一操作员的P应用。在具有足够小p的界图上，QAOA在状态输出中遥远的QABIT的测量值可得出不相关的结果。我们专注于在随机图中找到大型独立集，其中DN/2边缘保持D固定和N大。使用随机图中几乎最佳独立集的重叠间隙属性，以及QAOA的局部性，我们能够证明，如果P小于d依赖性常数log n，则QAOA将无法做得更好，而不是找到一个大小的独立集合。.854乘以D型d的最佳尺寸。由于对数正在缓慢增长，即使在100万量子位时，我们也只能证明，如果P单位为单位，则该算法被阻止。在较高的p处，算法“看到”了整个图，我们没有迹象表明性能是有限的。
The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator that respects the locality of the graph. On a graph with bounded degree, with p small enough, measurements of distant qubits in the state output by the QAOA give uncorrelated results. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large. Using the Overlap Gap Property of almost optimal independent sets in random graphs, and the locality of the QAOA, we are able to show that if p is less than a d-dependent constant times log n, the QAOA cannot do better than finding an independent set of size .854 times the optimal for d large. Because the logarithm is slowly growing, even at one million qubits we can only show that the algorithm is blocked if p is in single digits. At higher p the algorithm "sees" the whole graph and we have no indication that performance is limited.
