Quantum Approximate Optimization Algorithm in Finite Size and Large Depth and Equivalence to Quantum Annealing

Understand

The quantum approximate optimization algorithm (QAOA) and quantum annealing are two of the most popular quantum optimization heuristics.

• While QAOA is known to be able to approximate quantum annealing, the approximation requires QAOA angles to vanish with the problem size $n$, whereas optimized QAOA angles are observed to be size-independent for small $n$ and constant in the infinite-size limit.
• This fact led to a folklore belief that QAOA has a mechanism that is fundamentally different from quantum annealing.
• In this work, we provide evidence against this by analytically showing that QAOA energy approximates that of quantum annealing under two conditions, namely that angles vary smoothly from one layer to the next and that the sum is bounded by a constant.