标题： 一级QAOA和IQP电路的禁止子空间 显示英文标题

标题： Forbidden subspaces for level-1 QAOA and IQP circuits

摘要： 我们对可以使用一级量子近似优化算法（QAOA）精确求解的问题进行了深入研究。为此，我们隐式定义了一类问题哈密顿量，这些哈密顿量作为一级QAOA电路中的相位分离器时，与由一组计算基态张成的目标子空间具有单位重叠。对于一维目标子空间，我们在隐式定义的哈密顿量类中识别出一些实例，其中量子退火（QA）和模拟退火（SA）找到解的概率呈指数级小。因此，我们的结果界定了QAOA、QA和SA之间的第一条分界线，并突显了基于干涉的搜索启发式方法如QAOA与基于热和量子涨落的启发式方法如SA和QA之间的根本差异。此外，对于二维解子空间，我们能够证明QAOA电路的深度随着两个目标状态之间的汉明距离线性增长。我们进一步表明，对于维度大于$2$且小于$2^n$的目标子空间，不存在真正的解。我们还将这些结果转移到即时量子多项式（IQP）电路中。 显示英文摘要

摘要： We present a thorough investigation of problems that can be solved exactly with the level-1 Quantum Approximate Optimization Algorithm (QAOA). To this end we implicitly define a class of problem Hamiltonians that employed as phase separator in a level-1 QAOA circuit provide unit overlap with a target subspace spanned by a set of computational basis states. For one-dimensional target subspaces we identify instances within the implicitly defined class of Hamiltonians for which Quantum Annealing (QA) and Simulated Annealing (SA) have an exponentially small probability to find the solution. Consequently, our results define a first demarcation line between QAOA, QA and SA, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively. Moreover, for two-dimensional solution subspaces we are able to show that the depth of the QAOA circuit grows linearly with the Hamming distance between the two target states. We further show that there are no genuine solutions for target subspaces of dimension higher than $2$ and smaller than $2^n$. We also transfer these results to Instantaneous Quantum Polynomial (IQP) circuits.