Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
复制标题
DOI：
10.1103/physrevx.10.021067
复制
发表时间：
2020-06-24
影响因子：
12.5
通讯作者：
Lukin, Mikhail D.
中科院分区：
文献类型：
--
作者：
Zhou, Leo;Wang, Sheng-Tao;Lukin, Mikhail D.
量子近似优化算法（QAOA）是一种混合量子-经典变分算法，旨在解决组合优化问题。尽管QAOA有望在近期实现量子应用，但目前对其最低深度变体以外的性能了解不多。理解和部署QAOA的一个重要但缺失的要素是执行外循环经典优化的建设性方法。我们提供了一个深入的研究QAOA的MaxCut问题的性能，通过开发一个有效的参数优化程序，并揭示其利用非绝热操作的能力。基于观察到的最优参数模式，我们提出了启发式策略，用于初始化优化，以在O[poly（p）]时间内找到准最优p级QAOA参数，而随机初始化的标准策略需要2（O）（P）优化运行才能实现类似的性能。然后，我们基准QAOA，并将其与量子退火，特别是在困难的情况下，绝热量子退火失败，由于小的光谱间隙。比较结果表明，QAOA可以通过优化学习，利用非绝热机制来规避与消失的光谱间隙相关的挑战。最后，我们提供了一个现实的资源分析实验实施的QAOA。当测量中的量子波动占，我们说明，优化是重要的，只为问题的大小超出数值模拟，但可在近期的设备。我们提出了一个可行的实现大型MaxCut问题的几百个顶点的系统中的二维中性原子，达到政权挑战最好的经典算法。
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems. Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant. An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization. We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations. Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O[poly(p)] time, whereas the standard strategy of random initialization requires 2(O)(P) optimization runs to achieve similar performance. We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps. The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps. Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA. When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices. We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.