论文标题
QAOA和IQP电路的禁止子空间
Forbidden subspaces for level-1 QAOA and IQP circuits
论文作者
论文摘要
我们对问题进行了彻底的研究，这些问题可以通过1级量子近似优化算法（QAOA）精确解决。为此，我们隐式定义了一类问题的汉密尔顿人，这些问题在1级QAOA电路中用作相位分离器，提供单位与一组计算基础状态跨越的目标子空间重叠。对于一维目标子空间，我们在隐式定义的哈密顿量类别中识别量子退火（QA）和模拟退火（SA）的实例具有指数较小的概率可以找到解决方案。因此，我们的结果定义了QAOA，QA和SA之间的第一个分界线，并强调了基于QAOA等基于干扰的搜索启发式和基于SA和QA（例如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.
