The QAOA gets stuck starting from a good classical string

Understand

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.