Evaluating QAOA expectation values can be as hard as counting optimal solutions
Abstract
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≥ 2, complementing past results showing efficiently computable formulas for p=1 with arbitrary problem graphs. We sharpen this dichotomy showing that for p≥ 2 exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at p≥ 2 is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from p=1 to p=2 is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.
Related
- Benchmarking a randomized quantum algorithm for estimating expectation values of molecular observables
- Hardware-Friendly Estimation of LCU-Based Expectation Values via Quantum-to-Classical Workload Shifting
- Pulsed single-photon magnetometry with a Λ-type three-level system: near-optimal frequency-resolved photon counting
- New directions in dynamical expectation estimation
- Alignment-Free Optical Combining with Scalar-Message Expectation Propagation Detection for Distributed Multi-Aperture Coherent Reception
BibTeX
@misc{hadfield2026evaluating,
title = {{Evaluating QAOA expectation values can be as hard as counting optimal solutions}},
author = {Stuart Hadfield},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.11385},
eprint = {2608.11385},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.11385},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Evaluating QAOA expectation values can be as hard as counting optimal solutions
AU - Stuart Hadfield
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2608.11385
UR - https://arxiv.org/abs/2608.11385
AB - 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≥ 2, complementing past results showing efficiently computable formulas for p=1 with arbitrary problem graphs. We sharpen this dichotomy showing that for p≥ 2 exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at p≥ 2 is shown to remain even for evaluating single pairwise correlators $\langle Z\otimes Z\rangle $, as well as for highly restricted sets of algorithm parameters. Our proof refines the NP-hardness construction of Wang et al. that recovers the maximum cut value from the largest exponent of a QAOA Laurent polynomial, utilizing a distinct and simpler construction that extracts a value proportional to the total number of maximum cuts, in addition to the optimal cut value. Thus we show that the QAOA expectation value hardness transition from p=1 to p=2 is not only from tractability to optimization hardness, but to that of counting optimal solutions. As an application we show our results imply analogous hardness results for computing gradients and Hessians of QAOA circuits.
ER -