The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
复制标题
量子近似优化算法需要看全图：一个典型案例
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Gutmann
中科院分区：
文献类型：
--
作者：
E. Farhi;D. Gamarnik;S. Gutmann
量子近似优化算法自然适用于图上的组合搜索问题。量子电路具有遵守图的局部性的酉运算符的p个应用。在一个有界度的图上，当p足够小时，QAOA输出的状态中的遥远量子比特的测量给出了不相关的结果。我们的重点是在n/2条边保持d固定且n大的随机图中寻找大的独立集。利用随机图中几乎最优独立集的重叠间隙性质和QAOA的局部性，我们能够证明，如果p小于d依赖的常数乘以logn，则QAOA不能比找到一个大小为d的最优值的854倍的独立集更好。因为对数是缓慢增长的，即使在一百万量子比特，我们也只能证明，如果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.
$p$-spin 模型的重叠间隙属性和近似消息传递算法
DOI：
10.1214/20-aop1448
发表时间：
2021
期刊：
The Annals of Probability
影响因子：
--
作者：
Gamarnik, David;Jagannath, Aukosh
通讯作者：
Jagannath, Aukosh
影响因子：
12.5
作者：
Zhou, Leo;Wang, Sheng-Tao;Lukin, Mikhail D.
通讯作者：
Lukin, Mikhail D.
Sherrington-Kirkpatrick 哈密顿量的优化
DOI：
10.1109/focs.2019.00087
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Montanari, Andrea
通讯作者：
Montanari, Andrea