Evaluating QAOA expectation values can be as hard as counting optimal solutions
The study investigates evaluating expectation values for Quantum Approximate Optimization Algorithm (QAOA) applied to MaxCut problems. It proves that for any fixed depth of two or more ($p ext{ ≥ } 2$), finding the exact cost expectation value is a 'counting hardness' problem, meaning it is as difficult as counting all optimal solutions. This establishes a fundamental complexity barrier for evaluating QAOA beyond depth one.