Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization

Understand

Despite much recent work, the true promise and limitations of the Quantum Alternating Operator Ansatz (QAOA) are unclear.

• A critical question regarding QAOA is to what extent its performance scales with the input size of the problem instance, in particular the necessary growth in the number of QAOA rounds to reach a high approximation ratio.
• We present numerical evidence for an exponential speed-up of QAOA over Grover-style unstructured search in finding approximate solutions to constrained optimization problems.
• Our result provides a strong hint that QAOA is able to exploit the structure of an optimization problem and thus overcome the lower bound for unstructured search.