论文标题
量子状态的浓度界限和对多项式近似值的QAOA的局限性
Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations
论文作者
论文摘要
我们证明了以下量子状态类别的浓度界限：（i）浅量子电路的输出状态，从[DPMRF22]回答一个空的问题； （ii）注射矩阵产品状态； （iii）输出状态浓密的哈密顿进化状态，即形式的状态$ e^{i^{（（p）}}} \ cdots e^{（1）} |ψ_0\ rangle $ for Any $ n $ qubit content $ qubit content $ | c $ |满足规范限制的哈密顿人，包括与量子位之间相互作用的密集的哈密顿人。我们的证明使用多项式近似，表明这些状态与本地运营商接近。这意味着计算基础测量（以及其他相关可观察到的）浓度的锤击重量的分布。 （iii）的一个例子是量子近似优化算法（QAOA）产生的状态。使用这些状态的浓度结果，我们表明，对于一个随机的自旋模型，即使在超稳定级别$ p = o（\ log \ log \ log n）$的情况下，QAOA也只能以可忽略不计的概率成功，假设所谓的重叠差距属性的增强版本。这给出了QAOA在超稳定级别的密集实例上的第一个局限性，从而改善了最新结果[BGMZ22]。
We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [DPMRF22]; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $e^{ιH^{(p)}} \cdots e^{ιH^{(1)}} |ψ_0\rangle$ for any $n$-qubit product state $|ψ_0\rangle$, where each $H^{(i)}$ can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates. An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level $p = o(\log \log n)$, assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level, improving upon the recent result [BGMZ22].
