Evaluating QAOA expectation values can be as hard as counting optimal solutions

arXiv:2608.11385 · quant-ph, cs.CC · Submitted 2026-08-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Evaluating QAOA expectation values can be as hard as counting optimal solutions".

Mira: Evaluating expectation values in quantum algorithms like QAOA for MaxCut can be as computationally difficult as counting optimal solutions,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So Mira, we've been looking at the "Evaluating QAOA expectation values can be as hard as counting optimal solutions" paper for a bit. It seems like they are tackling a really fundamental question about how hard it is to even check the results of these quantum algorithms when we go beyond the simplest case.

Mira: Exactly, Kai, and what caught my eye immediately was that they're moving past just asking if finding one solution is hard; they’re showing that evaluating the expectation value itself becomes a counting problem, which is a step up in difficulty.

Lev: From an error-correction standpoint, if we were trying to run this on actual hardware, knowing it's a counting hardness result means we can't rely on fast classical checks for these deeper circuits.

Kai: Right, so what’s the core of what they are saying about the QAOA expectation value function? They’re looking at how hard it is to compute that cost when the depth parameter p is two or more.

Mira: They establish a sharp dichotomy: for p=one exact formulas are available in polynomial time, but once you move to p at least two computing the exact expectation value becomes as hard as counting how many maximum cuts exist in the underlying graph <ref:2608.11385#pg0>.

Lev: That makes sense; if it’s counting optimal solutions, it suggests that any quantum algorithm designed to find these values might need exponential resources just to verify its output accurately on a classical machine.

Kai: It seems like they are connecting this directly back to the MaxCut problem, where counting the number of maximum cuts is already known to be #P-hard.

Mira: That connection is key because it shows that for p at least two evaluating the cost expectation value isn't just NP-hard in a general sense; it’s specifically #P-hard, which means it's as hard as counting those solutions one <ref:2608.11385#pg0>.

Lev: If we consider running this on real hardware, having to count cuts suggests that simulating the full quantum state for a deep circuit becomes computationally infeasible very quickly.

Kai: And they don't stop there; they show this hardness extends even to looking at specific parts of the cost function, like single-edge correlators such as Z r Z s.

Title and authors: Mira: That’s significant because it means we can't rely on simplifying assumptions about the structure of the circuit when we try to extract individual pieces of information from the expectation value.

Lev: For error correction, that implies that even if you manage to get a noisy measurement, verifying what that noisy measurement actually represents in terms of the underlying graph structure is going to be extremely taxing classically.

Kai: Regarding improvements, the paper points toward how this structural hardness can be used to guide future work in variational quantum algorithms and circuit design.

Mira: They suggest using this complexity result to better understand the trade-offs between circuit depth and classical evaluation feasibility, which helps us design circuits that are easier to handle classically when we need exact answers.

Lev: If the goal is practical implementation, knowing which depths are fundamentally intractable for exact evaluation helps us avoid building circuits that rely on these hard counts unless we're willing to accept exponential overhead.

Kai: They also touch upon the difficulty of computing derivatives, like the first derivative or even the full gradient and Hessian of this cost function.

Mira: That’s a big statement because if even the first derivative is counting hard, it suggests that optimizing parameters using gradient descent methods might also face these severe classical bottlenecks when applied to deep QAOA circuits two <ref:2608.11385#pg0>.

Lev: If we can't compute the gradient efficiently, then parameter optimization for practical use becomes a very difficult problem on its own.

Kai: The paper also addresses exponential precision approximation, showing that even getting an answer with an additive error of two-alpha N is computationally hard for fixed depth p at least two <ref:2608.11385#pg0>.

Mira: That means we can't just settle for some good approximation when the required precision is high; you still need exponential samples to get that accuracy, which reinforces the structural nature of this counting hardness.

Lev: For running simulations, that means we can’t just sample a few times and hope for a certain error bound; if we need that level of precision, the classical cost explodes.

Kai: So, in conclusion for this paper on "Evaluating QAOA expectation values can be as hard as counting optimal solutions," the main implication is that moving to depth two or more fundamentally changes the complexity of analyzing these quantum algorithms from an optimization problem to a counting problem.

Title and authors: Mira: That's right; it solidifies a boundary where classical simulation power runs into inherent mathematical difficulty when dealing with parameterized quantum circuits one <ref:2608.11385#pg0>.

Lev: It sets a very clear limit on how deep we can go before the verification process becomes computationally prohibitive for practical error-corrected systems.

Kai: It’s been really interesting seeing how they build this gadget construction to prove the relationship between counting maximum cuts in G and H, which is a concrete way to show this complexity.

Mira: That construction mechanism, using the balanced counting gadget, is what makes the result so tangible; it shows exactly where the complexity comes from structurally within the graph setup one <ref:2608.11385#pg0>.

Lev: Seeing that reduction helps us predict exactly what kind of structural properties in a graph will lead to these hard counting problems when we try to simulate them.

Kai: So, as we wrap up this discussion on "Evaluating QAOA expectation values can be as hard as counting optimal solutions," the main idea is that depth two or higher transforms the evaluation task into a problem of counting maximum cuts.

Mira: And that means for those circuits, finding an exact value isn't just about optimization anymore; it’s about solving a much more complex enumeration problem one <ref:2608.11385#pg0>.

Lev: For us in error correction, this tells us we need to be very careful with the depth of the circuits we use if we want to rely on classical verification steps.

Kai: It really highlights that while QAOA is powerful for finding solutions, the tasks surrounding its rigorous evaluation have a much higher computational hurdle than initially thought one <ref:2608.11385#pg0>.

Mira: Precisely; it confirms that the hardness isn't just about finding one good cut, but about enumerating all of them when p at least two one <ref:2608.11385#pg0>.

Lev: We need to keep exploring ways to bypass this counting barrier for deeper circuits if we want these quantum methods to have a real chance in noisy environments.

Kai: That’s what we’ll be looking at next, and I think it sets up some interesting avenues for how we design algorithms that are robust against these specific complexity barriers.

The paper's summary: Kai: So, we've seen how they build this counting gadget to connect the MaxCut problem to QAOA evaluation, and now we need to wrap up what this whole paper actually tells us about the difficulty of those evaluations for deeper circuits.

Mira: Essentially, Kai, the authors are showing that once you push the depth parameter p past one, evaluating the expectation value isn't just a simple optimization task anymore; it fundamentally becomes a counting problem that is as hard as finding every single optimal solution to a constraint satisfaction problem.

Lev: From my perspective in error correction, this means if we want to run these algorithms on hardware, we can’t rely on fast classical methods to verify the results because they're stuck enumerating possibilities.

Kai: That's the core idea—the complexity shifts from finding *one* good answer to having to count *all* of them when p is two or more. It shows that for any fixed depth, this evaluation difficulty is tied directly to the maximum cut counting problem, which we already know is quite tough.

Mira: Exactly, and they don't stop at just finding one solution; they prove this hardness extends to computing the expectation value itself and even its derivatives like the gradients and Hessians. That’s a much broader statement about how computationally demanding analyzing these quantum circuits becomes.

Lev: If we consider running this on actual hardware, having to count cuts suggests that simulating the full quantum state for a deep circuit becomes computationally infeasible very quickly, which is a major hurdle for scaling up any variational approach.

Kai: And they even showed that you can't just settle for some good approximation when you need high precision; getting an answer with an error of two-alpha N still requires exponential samples, reinforcing this structural worst-case nature of the counting hardness.

Mira: That reinforces the idea that we can't just tweak parameters and hope for a good result; the very act of verifying or even precisely calculating what the quantum computer is doing becomes computationally prohibitive on classical hardware.

Lev: So, if we look at future work, this suggests that for practical applications, we really need to focus on circuit design where these expectation values are known to be tractable classically before we even worry about deep parameter optimization.

Kai: Right, so this paper points us toward designing circuits that stay shallower when exact classical evaluation is a requirement, or maybe exploring different observables altogether to avoid these counting nightmares.

Mira: Precisely; this result provides a very concrete structural map showing exactly which graph properties lead to these hard counting problems, guiding future research on complexity-aware circuit design one.

Lev: It’s a clear signal for the error correction community that we have a fundamental limit on how deep we can push these specific QAOA evaluations before classical verification becomes an insurmountable barrier.

The paper's improvements: Tom: So, we're looking at what the paper suggests we should actually do once we understand this counting hardness result for QAOA evaluation, and it’s about guiding future algorithm development.

Mira: The authors point out that this complexity analysis is really useful because it helps us design circuits where the expectation values are known to be tractable classically, which is a key constraint in condensed matter theory when mapping quantum states onto physical systems.

Lev: From an error correction standpoint, this means we should prioritize circuit structures that avoid these counting problems entirely if we want to keep the classical verification steps manageable on real hardware.

Kai: They suggest that for the sake of practical implementation, we should focus on shallower circuits or different observable choices when exact classical evaluation is needed rather than building deep circuits just because they look powerful.

Mira: That’s because they established a baseline where depth one still allows for polynomial-time evaluation, so designers have a clear starting point for what's feasible versus what’s hitting this counting barrier at depth two or more.

Lev: If we think about parameter optimization, this tells us that routines relying on exact expectation values will face inherent classical computational barriers when applied to deep circuits, pushing us toward different optimization strategies altogether.

Kai: Exactly, so the implication for hardware is that we need to be very careful about the depth of the circuits we use if we want to rely on classical verification steps without getting bogged down in intractable enumeration tasks.

Mira: They also show that this structural understanding can inform how we characterize quantum kernels and observables, allowing us to analyze them based on their complexity before even implementing them fully.

Lev: That moves the discussion from just "can we run it?" to "how complex is the verification process for this specific type of observable?" which is vital for scaling any system.

Kai: So, in short, these improvements are about using the complexity result to make smarter choices when designing and verifying quantum hardware experiments.

Mira: And that sets up a future direction where we can better characterize the trade-offs between circuit depth and classical tractability, which is a big deal for theoretical condensed matter physics intersecting with quantum computation.

Lev: It gives us concrete guidance on what kind of structural properties in a graph or circuit will lead to these hard counting problems, which helps us predict where the bottlenecks will appear when we try to scale up any system.

Conclusion: Kai: So, to wrap up this discussion on "Evaluating QAOA expectation values can be as hard as counting optimal solutions," we've established that for depth two or more, evaluating those cost functions becomes a counting problem tied to the maximum cut complexity.

Mira: It really confirms that the jump from simple optimization to enumeration is massive when we move past p=one in QAOA; it shows the underlying structure of these quantum algorithms has inherent classical computational hurdles at depth two.

Lev: For my work on error correction, this means we have a very clear ceiling on how deep we can push these specific evaluations if we want any kind of classical verification to be feasible for running on actual hardware.

Kai: That’s the experimental reality: knowing where the computational wall is helps us decide what kind of circuits we can even bother building and cooling.

Mira: And this result is significant because it ties the performance limits of a variational quantum algorithm directly to fundamental counting complexity classes, which has huge implications for how we model physical systems using these tools.

Lev: It gives us a solid theoretical basis for anticipating the classical simulation costs that will eventually hit real-world hardware limitations when we try to verify results from deep circuits.

Kai: So, this paper is a very strong piece of evidence showing that the computational cost of analyzing QAOA output scales much more steeply than just finding one good answer.

Mira: It's a powerful tool for condensed matter theorists because it allows us to use graph structures to predict when quantum simulation will become classically intractable based on known complexity results.

Lev: We need to keep pushing research into methods that can bypass this counting barrier, or we won't be able to get meaningful results from deeper QAOA circuits on any scale.

Quantum Artificial Intelligence Laboratory (QuAIL), NASA Ames Research Center · USRA Research Institute for Advanced Computer Science, Mountain View

quant-ph, cs.CC

Submitted: 2026-08-11

Updated: 2026-10-02

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Evaluating expectation values in quantum algorithms like QAOA for MaxCut can be as computationally difficult as counting optimal solutions, establishing a fundamental complexity barrier for

Key concepts

EvalMCp
This represents the cost expectation value function for QAOA on a graph G, calculated as $\langle\psi_p|CG|\psi_p\rangle$. It measures how well the quantum state approximates the optimal MaxCut solution, and its difficulty depends heavily on the depth parameter $p$.
Counting Hardness
This complexity class describes problems that are hard because they require counting solutions rather than just finding one. The paper shows that for $p \text{ ≥ } 2$, evaluating the expectation value is as hard as counting the total number of maximum cuts in a related graph, which is a known difficult problem.
Balanced Counting Gadget
This is a specific construction technique used to transform an input MaxCut instance (H) into a larger graph (G). This gadget ensures that the number of maximum cuts in G is directly proportional to the number of maximum cuts in H, allowing researchers to relate the difficulty of counting solutions between two different problems.
Fourier Analysis for Coefficients
The expectation value calculation is equivalent to evaluating a Laurent polynomial. The authors use an inverse discrete Fourier transform over specific roots of unity to recover every coefficient of this polynomial exactly. This technique ensures that all necessary information, including those with negative exponents, can be recovered without aliasing.

Terminology

Summary

Evaluating expectation values in quantum algorithms like QAOA for MaxCut can be as computationally difficult as counting optimal solutions, establishing a fundamental complexity barrier for evaluating these quantities at depth two and beyond.

How it works

The paper investigates the computational complexity of evaluating the cost expectation value function, denoted as EvalMCp, for the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on a graph G. The standard QAOA state is defined by parameters (angles) γ1,..., γp and β1,..., βp. The cost expectation value is given by Fp(G; γ, β) = ⟨ψpCGψp⟩.

The core of the hardness result lies in showing that for a fixed depth parameter p ≥ 2, evaluating this function is not just NP-hard (finding one solution), but rather counting hard to solve problems. The authors refine prior work by showing that for p ≥ 2, exact or exponentially precise cost expectation value evaluation is specifically a counting hardness problem, meaning it is as hard as counting the number of optimal solutions of a constraint satisfaction problem.

Key Findings and Hardness Results

The central theorem establishes the complexity dichotomy:

  1. For depth p = 1, EvalMC1 ∈ FP (polynomial-time computable).

  2. For every fixed p ≥ 2, EvalMCp is proven to be a counting hardness problem under deterministic polynomial-time Turing reductions, meaning it is a counting problem in the complexity class NP (specifically, it is shown to be as hard as computing the number of maximum cuts).

This hardness transition from tractability at p=1 to counting hardness at p=2 marks a significant shift in understanding the evaluation difficulty of QAOA. The authors demonstrate this by constructing instances where the extremal Laurent polynomial coefficient can be evaluated in closed form and is shown to be proportional to the full maximum-cut degeneracy, MC(G).

The Construction Mechanism

To prove this hardness, the authors construct a graph G = G(H) from an input graph H (the MaxCut problem instance). This construction utilizes a balanced counting gadget defined by:

  1. Introducing disjoint vertex sets Av and Bv for each vertex v in H, each of size L = 2(∆ + 2) + 1, where ∆ is the maximum degree of H.

  2. Adding all edges between Av and Bv (a complete bipartite graph).

  3. Adding synchronous edges between corresponding vertices in Av and Bv for every edge in E(H).

  4. Introducing two universal anchor vertices, r and s, connected to every vertex in W = ∪ V(Av) ∪ V(Bv).

This construction ensures that the number of maximum cuts in G is directly related to the number of maximum cuts in H: MC(G) = 2MC(H). The gadget rigidity lemma proves that every maximum cut of G places Av and Bv monochromatically on opposite sides, and r and s on opposite sides, inducing a specific relationship between MC(G) and MC(H).

Coefficient Recovery via Fourier Analysis

The evaluation of the expectation value F2(G; z, β) is shown to be equivalent to evaluating a Laurent polynomial in the phase variable z. The authors use the inverse discrete Fourier transform over a set of roots of unity (Q = 4m + 1) to recover every coefficient of this polynomial. Since the interval containing all exponents lies within a range smaller than Q, no aliasing occurs, allowing for exact recovery of all coefficients, including those with negative indices.

Hardness for Derivatives and Gradients

The hardness extends beyond the expectation value itself to its derivatives.

  1. Exact computation of the first derivative F'(r)G(ϕ) = d r/dϕ r FG(ϕ) is proven to be a counting hardness problem, as the largest exponent with a nonzero recovered derivative coefficient is D⋆, which contains MC(H).

  2. The full gradient ∇FG and Hessian ∇2FG are shown to be computationally intractable, meaning their exact computation is also NP-hard under deterministic polynomial-time Turing reductions.

Exponential Precision Hardness

The results extend to exponentially precise additive approximation. For a fixed depth p ≥ 2, there exists a constant α > 0 such that approximating the expectation value Fp(G; ϕ) to an additive error of at most 2−αN is also NP-hard. This implies that recovering the exact count MC(H) from exponentially precise oracle queries requires an exponential number of samples, reinforcing the structural worst-case nature of this hardness.

Conclusion and Implications

The paper concludes that for standard QAOA depth p ≥ 2 on unweighted simple graphs, exact evaluation is inherently a counting problem.

Improvements for AI systems

Based on the provided scientific paper, here are specific improvements for AI systems derived from its findings:

) Improvements for AI Systems

The core contribution is establishing that evaluating expectation values of Quantum Approximate Optimization Algorithm (QAOA) circuits at depth 2 or greater is computationally hard, specifically as a counting problem rather than an optimization problem. This hardness extends to computing gradients and Hessians.

Here are specific improvements:

  1. Enhanced Robustness in Variational Quantum Algorithms (VQAs):

  2. Improved Parameter Optimization for Quantum Circuits:

  3. Structural Analysis of Quantum Kernels/Observables:

  4. Complexity-Aware Circuit Design and Verification:

) Specific Capabilities of the Improved AI System

An AI system equipped with the knowledge from this paper would be capable of performing the following tasks:

  1. Robustness in VQAs (e.g., QAOA):

  2. Improved Parameter Optimization for Quantum Circuits:

  3. Structural Analysis of Quantum Kernels/Observables:

  4. Complexity-Aware Circuit Design and Verification:

) Detailed Breakdown of Improvements and Capabilities

Improvement Area Specific AI Capability How the Paper Enables This

:---:---:---

  1. Robustness in VQAs (e.g., QAOA) & Sampling Analysis Evaluating the computational complexity of obtaining accurate expectation values for quantum states, especially at depth 2+. The system can determine if an exact or exponentially precise evaluation of a QAOA cost function is computationally tractable (P vs. NP-hard). Theorem 1.2 proves that evaluating the global expectation value and single-edge correlators at fixed depth 2 is hard to approximate (exponentially precisely), implying classical algorithms cannot efficiently compute these values for general graphs.

  2. Improved Parameter Optimization for Quantum Circuits Developing more efficient methods for finding optimal QAOA parameters by understanding the complexity of evaluating the objective function itself, rather than just sampling it repeatedly. The paper shows that even restricted evaluations (like those on a tied-phase line) are hard to compute exactly, suggesting that optimization routines relying on exact evaluation of expectation values will face inherent classical computational barriers for deep circuits.

  3. Structural Analysis of Quantum Kernels/Observables Analyzing the structural properties (e.g., graph structure) of quantum observables and how those properties dictate the complexity of their expectation value calculation. The system can identify which graph classes (e.g., diameter-two graphs) are tractable versus those that require hard counting/evaluation. The construction of the balanced maximum-cut counting gadget (Section 2) provides a concrete structural reduction showing how to encode the counting problem of MaxCut into a larger, polynomially sized graph instance, linking graph properties directly to algebraic complexity.

  4. Complexity-Aware Circuit Design and Verification Designing quantum circuits where the expectation values are known to be tractable for classical evaluation (e.g., depth 1), or verifying if a proposed circuit structure is inherently designed to compute computationally hard quantities efficiently. The result that depth-one expectation values are in FP (Proposition A.1) provides a baseline for tractability, guiding designers toward shallower circuits or different observable choices when exact classical evaluation is needed versus approximation.

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 at least 2, complementing past results showing efficiently computable formulas for p=1 with arbitrary problem graphs. We sharpen this dichotomy showing that for p at least 2 exact or exponentially precise cost expectation value evaluation is #P-hard under deterministic polynomial-time Turing reductions. Hardness at p at least 2 is shown to remain even for evaluating single pairwise correlators Z Z, 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.

Sources

Related papers