次优解

arXiv:2112.11151v1 [quant-ph] 2021 年 12 月 21 日

量子近似优化算法 (QAOA) 是一种变分量子算法，旨在给出组合优化问题的次优解。人们普遍认为 QAOA 有潜力在具有浅电路深度的嘈杂中型量子 (NISQ) 处理器中展示应用级量子优势。由于 QAOA 的核心是计算问题哈密顿量的期望值，一个重要的实际问题是我们是否可以找到一种有效的经典算法来求解一般浅量子电路情况下的量子均值。在这里，我们提出了一种基于图分解的新型经典算法，该算法在大多数优化问题（完全图情况除外）中与浅 QAOA 电路的量子比特数呈线性关系。与最新方法相比，在 Max-cut、图着色和 Sherrington-Kirkpatrick 模型问题中的数值测试显示出数量级的性能提升。我们的结果不仅对于探索 QAOA 的量子优势具有重要意义，而且对于 NISQ 处理器的基准测试也很有用。