How Much Entanglement Do Quantum Optimization Algorithms Require?

Many classical optimization problems can be mapped to finding the ground states of Ising Hamiltonians, for which quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) provide heuristic methods. 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 talk, I will examine the entanglement generated during the execution of ADAPT-QAOA and show that its behavior is quite different from standard QAOA.