How Much Entanglement Do Quantum Optimization Algorithms Require?

Understand

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.