  The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a
promising variational quantum algorithm for addressing NP hard combinatorial
optimization problems. However, a significant limitation lies in optimizing its
classical parameters, which is in itself an NP hard problem. To circumvent this
obstacle, initialization heuristics, enhanced problem encodings and beneficial
problem scalings have been proposed. While such strategies further improve
QAOA's performance, their remaining problem is the sole utilization of local
optimizers. We show that local optimization methods are inherently inadequate
within the complex cost landscape of QAOA. Instead, global optimization
techniques greatly improve QAOA's performance across diverse problem instances.
While global optimization generally requires high numbers of function
evaluations, we demonstrate how restricted global optimizers still show better
performance without requiring an exceeding amount of function evaluations.
