{"id":"arxiv/2608.11385","url":"https://arxiv.org/abs/2608.11385","tags":["quant-ph","cs.CC"],"score":0,"title":"Evaluating QAOA expectation values can be as hard as counting optimal solutions","domain":"quant-ph","source":"arxiv","authors":["Stuart Hadfield"],"reviews":0,"subject":"quant-ph","summary":"Evaluating expectation values is a critical task for variational quantum eigensolvers, parameterized quantum circuits, and many other quantum algorithms. We consider the well-studied case of the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut problem. Recent work of Wang et al. [arXiv:2511.20212] showed this task to be NP-hard in general for any QAOA depth $p\\geq 2$, complementing past results showing efficiently computable formulas for $p=1$ with arbitrary problem graphs. We sharpen this dichotomy showing that for $p\\geq 2$ exact or exponentially precise cost expectation…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}