THE QUANTUM INTELLIGENCER

Bottom Line Up Front: Evaluating QAOA cost functions and derivatives at depth p≥2 is -hard, implying quantum advantage via shallow circuits may not extend to practical optimization tasks requiring precise expectation estimation. Threat Identification: The computational hardness of computing QAOA expectation values transitions sharply at p=2—from efficiently solvable for p=1 to -hard for p≥2—even for restricted graph classes and single pairwise correlators like ⟨Z⊗Z⟩. This affects not only objective evaluation but also gradient-based training of QAOA parameters. Probability Assessment: The result is proven under deterministic polynomial-time Turing reductions and applies universally across all p≥2 implementations; therefore, the threat is already present in current NISQ-era quantum algorithms using QAOA with deeper circuits (p≥2), as of 2026. Impact Analysis: High—this limits the scalability and utility of QAOA as a practical solver for MaxCut and related combinatorial problems. It undermines assumptions that increasing circuit depth improves solution quality, since even evaluating performance becomes intractable without exponential resources. Impacts extend to variational quantum algorithms broadly, where gradient computation faces similar barriers [Wang et al., arXiv:2511.20212]. Recommended Actions: 1) Prioritize hybrid classical-quantum estimators or sampling-based approximations over exact evaluations for p≥2 QAOA. 2) Reassess benchmarks for quantum advantage claims involving QAOA beyond p=1. 3) Invest in error-resilient estimation techniques and explore alternative ansätze less sensitive to expectation value precision. Confidence Matrix: - Threat Identification: High confidence (directly supported by theorem) - Probability Assessment: High confidence (proven complexity result) - Impact Analysis: Medium-High confidence (extrapolated from theoretical bounds to practical implications) - Recommended Actions: Medium confidence (based on current mitigation strategies in literature) —Elias Hartwell Dispatch from The Prepared E0