  Many classical optimization problems can be mapped to finding the ground
states of diagonal Ising Hamiltonians, for which variational quantum algorithms
such as the Quantum Approximate Optimization Algorithm (QAOA) provide heuristic
methods. Because the solutions of such classical optimization problems are
necessarily product states, it is unclear how entanglement affects their
performance. An Adaptive Derivative-Assembled Problem-Tailored (ADAPT)
variation of QAOA improves the convergence rate by allowing entangling
operations in the mixer layers whereas it requires fewer CNOT gates in the
entire circuit. In this work, we study the entanglement generated during the
execution of ADAPT-QAOA. Through simulations of the weighted Max-Cut problem,
we show that ADAPT-QAOA exhibits substantial flexibility in entangling and
disentangling qubits. By incrementally restricting this flexibility, we find
that a larger amount of entanglement entropy at earlier stages coincides with
faster convergence at later stages. In contrast, while the standard QAOA
quickly generates entanglement within a few layers, it cannot remove excess
entanglement efficiently. Our results demonstrate that the role of entanglement
in quantum optimization is subtle and provide guidance for building favorable
features into quantum optimization algorithms.
