Akshay V, Philathong H, Morales M E S, Biamonte J D
Deep Quantum Laboratory, Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow 121205, Russia.
Phys Rev Lett. 2020 Mar 6;124(9):090504. doi: 10.1103/PhysRevLett.124.090504.
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm's ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
量子近似优化算法（QAOA）已迅速成为当代量子算法发展的基石。尽管应用范围不断扩大，但对于理解该算法的最终局限性，仅取得了为数不多的成果。在此，我们报告QAOA对问题实例约束与变量比率表现出强烈依赖性——这种问题密度对算法最小化相应目标函数（从而解决优化问题实例）的能力施加了限制。即便在没有贫瘠高原的情况下，此类可达性缺陷依然存在，且超出了最近报道的一级QAOA局限性。这些发现是最早确定变分量子近似优化存在严重局限性的研究之一。
