Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
复制标题
DOI：
10.1109/focs54457.2022.00039
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
J. Basso;D. Gamarnik;Song Mei;Leo Zhou
中科院分区：
文献类型：
--
作者：
J. Basso;D. Gamarnik;Song Mei;Leo Zhou
量子近似优化算法(QAOA)是一种用于组合优化的通用量子算法。我们分析了它的期望性能，并证明了它在任意恒定水平(层数)上对无限大的随机组合优化问题集成的聚集性。这些系综包括稀疏随机超图上的混合自旋模型和MAX-Q-XORSAT。我们的分析可以通过路径总和积分的鞍点近似来理解。这是通过证明多项式定理的推广而变得严格的，多项式定理是独立利益的技术结果。然后，我们证明了对于纯q-自旋模型，QAOA在恒定水平上的性能与在随机稀疏ErdôS-Rényi超图和每一个大周长正则超图上的MAX-Q XORSAT模型的QAOA性能渐近匹配。通过这种对应，我们证明了当Qq4$和为偶数时，QAOA在恒定能级下产生的平均值与纯Q自旋模型的最优值是有界的。这一限制使得量子算法在一种新的可以看到整个图的区域中的近似结果变得困难。
The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose quantum algorithm designed for combinatorial optimization. We analyze its expected performance and prove concentration properties at any constant level (number of layers) on ensembles of random combinatorial optimization problems in the infinite size limit. These ensembles include mixed spin models and Max-q-XORSAT on sparse random hypergraphs. Our analysis can be understood via a saddlepoint approximation of a sum-over-paths integral. This is made rigorous by proving a generalization of the multinomial theorem, which is a technical result of independent interest. We then show that the performance of the QAOA at constant levels for the pure q-spin model matches asymptotically the ones for Max-q XORSAT on random sparse Erdôs-Rényi hypergraphs and every large-girth regular hypergraph. Through this correspondence, we establish that the average-case value produced by the QAOA at constant levels is bounded away from optimality for pure q-spin models when $q\geq 4$ and is even. This limitation gives a hardness of approximation result for quantum algorithms in a new regime where the whole graph is seen.