论文标题
QAOA从一个好的古典字符串开始就卡住了
The QAOA gets stuck starting from a good classical string
论文作者
论文摘要
量子近似优化算法（QAOA）旨在最大程度地利用位字符串成本函数。尽管最初的状态在所有字符串上都是统一的叠加，但自然而然地尝试加快QAOA：首先使用经典算法生成一些良好的字符串，然后在与该字符串相关的计算基础状态下运行标准的QAOA。在这里，我们报告了数字实验，该实验表明这种初始化QAOA的方法急剧失败，几乎没有提高成本函数。我们为这种缺乏改进提供了多种分析论点，在不同的制度或假设（包括几乎线性深度）下，每种都可以严格化。我们强调，我们的负面结果仅适用于我们对温暖QAOA的简单化身，并且可能不适用于文献中的其他方法。我们希望我们的理论分析将为未来的算法设计提供信息。
The Quantum Approximate Optimization Algorithm (QAOA) is designed to maximize a cost function over bit strings. While the initial state is traditionally a uniform superposition over all strings, it is natural to try expediting the QAOA: first use a classical algorithm to produce some good string, and then run the standard QAOA starting in the computational basis state associated with that string. Here we report numerical experiments that show this method of initializing the QAOA fails dramatically, exhibiting little to no improvement of the cost function. We provide multiple analytical arguments for this lack of improvement, each of which can be made rigorous under different regimes or assumptions, including at nearly linear depths. We emphasize that our negative results only apply to our simple incarnation of the warm-start QAOA and may not apply to other approaches in the literature. We hope that our theoretical analysis will inform future algorithm design.
