The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions

Francisco Chicano, Zakaria Abdelmoiz Dahi, Gabriel Luque

QAOA is a hybrid quantum-classical algorithm to solve optimization problems in gate-based quantum computers. It is based on a variational quantum circuit that can be interpreted as…