⚛️ quantum physics

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

This paper establishes that evaluating exact or exponentially precise QAOA expectation values for the MaxCut problem at depth $p \geq 2$ is #P-hard, demonstrating that the computational difficulty transitions from tractability to counting optimal solutions rather than merely optimization.

Original authors: Stuart Hadfield

Published 2026-08-13

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Stuart Hadfield

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where computers don't just crunch numbers but dance with probabilities. This is the realm of quantum computing, a field that promises to solve problems so tangled and complex that today's supercomputers would take longer than the age of the universe to figure them out. At the heart of this dance is a popular routine called the Quantum Approximate Optimization Algorithm, or QAOA. Think of QAOA as a high-tech treasure hunt. You have a map (a problem) with many possible paths, and you want to find the one path that leads to the most gold (the best solution). The quantum computer prepares a special "superposition" state—a magical mix of all possible paths at once—and then, through a series of steps called "layers" or "depth," it tries to tilt the odds so that the best path shines the brightest when you finally look.

To know if the treasure hunt is going well, scientists need to check the "expectation value." In plain English, this is like taking a quick peek at the quantum computer's dance to see how close it is to finding the gold, without actually stopping the dance to count every single coin. For a long time, researchers knew that if the dance had only one step (depth $p=1$ ), checking this score was easy, like reading a simple recipe. But what happens when the dance gets more complicated, with two or more steps? A recent study by Wang and colleagues showed that checking the score for these deeper dances is incredibly hard—so hard it's as difficult as solving the original treasure hunt itself. But is it just as hard as finding one good path, or is it even harder?

This paper, written by Stuart Hadfield, dives deep into that question. The author proves that for QAOA with two or more layers, checking the score isn't just as hard as finding a single best solution; it's as hard as counting every single best solution that exists. In the world of computer science, finding one solution is a tough challenge, but counting them all is a monster of a different size, often considered even more impossible for classical computers to handle. Hadfield shows that this "counting monster" appears the moment you add a second layer to the algorithm. The paper doesn't just suggest this; it provides a rigorous mathematical proof, constructing a specific type of problem graph that forces any computer trying to calculate the QAOA score to essentially solve the impossible counting problem. This means that for these deeper quantum algorithms, the very act of checking how well they are doing is, in the worst-case scenario, a task that might be fundamentally beyond the reach of classical computers, even if we have a perfect quantum machine to run the dance.

The Treasure Hunt Gets Complicated

Let's break down the magic trick. The QAOA algorithm is designed to solve the "MaxCut" problem. Imagine a group of friends at a party, and you want to split them into two teams (Team Red and Team Blue) to play a game. The goal is to arrange the teams so that the maximum number of friendships are broken between the two sides. This is the "MaxCut." Some arrangements are better than others, and finding the absolute best arrangement is a classic puzzle that gets harder the more friends you add.

The QAOA algorithm tries to find this best arrangement by spinning a quantum coin. It starts with everyone in a superposition (both Red and Blue at the same time) and then applies a series of "twists" (the layers). The more twists you add, the more sophisticated the dance becomes. To see if the dance is working, scientists calculate an "expectation value." Think of this as a "score" that tells you, on average, how many friendships are broken in the quantum dance.

For a single twist ( $p=1$ ), calculating this score is easy. You can write it down on a napkin. But when you add a second twist ( $p=2$ ), things get weird. Previous research showed that calculating this score was "NP-hard," meaning it was as hard as finding the single best team arrangement. But Hadfield's paper says, "Wait, it's actually worse than that."

The Counting Monster

Hadfield's main discovery is a sharp upgrade in our understanding of the difficulty. He proves that calculating the score for $p \ge 2$ is not just "NP-hard" (finding one solution); it is #P-hard.

To understand the difference, imagine you are a detective.

NP-hard is like being asked: "Can you find one suspect who committed the crime?" It's hard, but if you get lucky or try hard enough, you might find one.
#P-hard is like being asked: "How many suspects in total committed the crime?" You have to find every single one and count them.

In the world of computer science, counting is generally believed to be much harder than just finding one. Hadfield shows that for QAOA with two or more layers, the math required to calculate the score forces you to count the number of perfect solutions.

The Magic Gadget

How did he prove this? Hadfield built a clever "gadget," which is like a trap designed to catch the computer. He took a standard MaxCut problem and built a giant, complex graph around it. This graph has special "anchor" points and "variable" blocks.

The trick is in the design. When the quantum computer runs its dance on this specific graph, the final score (the expectation value) turns into a giant mathematical expression called a "Laurent polynomial." This expression is like a long string of terms, each with a different power of a variable (like $z^1, z^2, z^3...$ ).

Hadfield showed that the highest power in this string (the "extreme coefficient") holds a secret. If you can calculate the score perfectly, you can extract this highest power. And here is the kicker: the size of that specific number is directly proportional to the total number of perfect solutions to the original problem.

So, if you could easily calculate the QAOA score for this graph, you would instantly know the answer to the "counting monster" problem. Since counting is believed to be impossible for classical computers to do efficiently, calculating the QAOA score must also be impossible for them.

The "One Edge" Surprise

The paper gets even more surprising. You might think, "Okay, calculating the total score is hard, but maybe calculating the score for just one specific friendship (a single edge) is easy?"

Hadfield says no. He proves that even if you only ask the quantum computer to tell you the correlation between two specific people (a "two-qubit correlator" like $\langle Z_r Z_s \rangle$ ), the problem remains #P-hard. The difficulty isn't just in the big picture; it's baked into the smallest details of the algorithm.

What This Means for the Future

The paper draws a clear line in the sand:

Depth $p=1$ : Easy. We can calculate the score efficiently.
Depth $p \ge 2$ : Hard. Calculating the score is as hard as counting all optimal solutions.

This has huge implications. Many modern algorithms use QAOA to train the machine, adjusting the "twists" (parameters) to get a better score. If calculating the score is this hard, then training these algorithms on a classical computer (to see how the quantum machine is doing) might be impossible for deep circuits.

The author also notes that this doesn't mean quantum computers are useless. In fact, it might mean they are more useful. If a classical computer can't even check the score, maybe the quantum computer is the only thing that can. However, the paper also warns that this "hardness" is a worst-case scenario. It doesn't mean every graph is impossible to solve; it just means there are specific, nasty graphs where the math breaks down for classical computers.

The Bottom Line

Stuart Hadfield's paper is a wake-up call for the quantum community. It tells us that as we make QAOA more powerful by adding more layers, we aren't just making the problem harder to solve; we are making the problem of checking our work exponentially harder. We've moved from a world where we could easily verify the quantum dance to a world where verifying the dance requires solving a counting puzzle that might be the hardest thing in computer science. It's a reminder that in the quantum realm, the deeper you go, the more mysterious the math becomes.

Technical Summary: Evaluating QAOA Expectation Values is #P-Hard

Problem Statement
The paper addresses the computational complexity of evaluating expectation values for the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem. While evaluating the cost expectation value $F_p(G; \gamma, \beta) = \langle \psi_p | C_G | \psi_p \rangle$ is known to be efficiently computable for depth $p=1$ on arbitrary graphs, recent work established that exact evaluation becomes NP-hard for any fixed depth $p \ge 2$ . The central question investigated here is whether the hardness for $p \ge 2$ is limited to optimization (finding a solution) or extends to counting (determining the number of optimal solutions). Specifically, the author asks if computing these expectation values is #P-hard, a complexity class generally believed to be harder than NP, corresponding to the difficulty of counting the number of solutions to a constraint satisfaction problem.

Methodology
The author refines the hardness proof mechanism introduced by Wang et al. [5], which utilized Laurent polynomials to recover the maximum cut value from the largest exponent. The author's approach involves the following steps:

Graph Construction (Balanced Counting Gadget): Instead of the asymmetric gadgets used in prior work, the author constructs a specific graph $G(H)$ from an input graph $H$ . This construction employs:
- Variable Gadgets: For each vertex in $H$ , a balanced complete bipartite graph $K_{L,L}$ is created, where $L = O(n)$ .
- Synchronous Edges: Edges connecting corresponding vertices in the $K_{L,L}$ gadgets of adjacent vertices in $H$ to preserve the original graph's structure.
- Anchor Vertices: Two universal vertices, $r$ and $s$ , connected to every vertex in the variable gadgets and to each other.
- This construction ensures that the graph $G(H)$ has a diameter of 2 and that its maximum cuts are rigidly constrained: the $K_{L,L}$ gadgets must be cut completely, and the anchors must be on opposite sides.
Laurent Polynomial Analysis: The cost expectation value (or a specific two-qubit correlator $\langle Z_r Z_s \rangle$ ) is expressed as a Laurent polynomial in a phase variable $z = e^{i\phi}$ . The author analyzes the coefficients of this polynomial.
- They identify an "extreme coefficient" corresponding to the highest degree exponent $D^*$ .
- Through a "reduced path sum" analysis, they prove that the coefficient $a_{D^*}$ is non-zero and directly proportional to the number of maximum cuts of the original graph $H$ , denoted $|\# \text{MC}(H)|$ .
- Specifically, $a_{D^*} = \kappa \cdot |\# \text{MC}(H)|$ , where $\kappa$ is a known non-zero algebraic factor dependent on the mixer angles and graph size.
Reduction via Interpolation: The author demonstrates that by querying the QAOA expectation value oracle at polynomially many distinct phase values (roots of unity), one can use the inverse discrete Fourier transform to recover the Laurent coefficients exactly. Since the extreme coefficient encodes the count of maximum cuts, an oracle capable of exact evaluation (or exponentially precise evaluation) allows for the recovery of this count, thereby establishing a deterministic polynomial-time Turing reduction from the #P-hard problem of counting maximum cuts to the problem of evaluating QAOA expectation values.

Key Contributions and Results

Complexity Dichotomy: The paper establishes a sharp complexity transition for QAOA expectation values on unweighted simple graphs:
- $p=1$ : The problem is in FP (polynomial-time computable).
- $p \ge 2$ : The problem is #P-hard under deterministic polynomial-time Turing reductions.
Counting vs. Optimization: Unlike the previous NP-hardness result which recovered the value of the maximum cut, this work shows that evaluating the expectation value allows one to recover the number of maximum cuts. This elevates the hardness from optimization to counting.
Restricted Hardness: The #P-hardness holds even under significant restrictions:
- It applies to the evaluation of a single designated two-qubit correlator $\langle Z_r Z_s \rangle$ rather than the global cost function.
- It holds for a highly restricted set of algorithm parameters (fixed mixer angles $\beta_1 = \arctan(1/2)$ , $\beta_2 = \pi/4$ , and tied cost angles $\gamma_1 = \gamma_2 = \phi$ ).
- It applies to graphs with diameter 2 (though these graphs have high degree).
Derivatives and Hessians: The author extends these results to show that computing exact gradients and Hessians of the QAOA cost function with respect to the parameters is also #P-hard.
Exponential Precision: The hardness extends to the problem of approximating the expectation value with exponentially small additive error ( $2^{-\alpha N}$ ), as this precision is sufficient to distinguish the extreme coefficient and recover the integer count via rounding.

Significance and Claims
The paper claims to provide a "clean exact-complexity classification" for QAOA expectation values. The primary significance lies in demonstrating that the transition from $p=1$ to $p=2$ is not merely a shift from tractability to optimization hardness (NP-hard), but a shift to counting hardness (#P-hard).

The author emphasizes that their results are worst-case statements regarding specific families of high-degree graphs and do not imply that evaluating QAOA is hard for all graphs or typical instances. They note that the hardness relies on exact or exponentially precise evaluation; they do not claim hardness for constant or polynomially small additive error regimes, which are more relevant to current noisy intermediate-scale quantum (NISQ) devices.

Furthermore, the paper distinguishes its findings from quantum supremacy results related to sampling. While sampling from QAOA outputs at $p=1$ is already classically hard under certain conditions, this work shows that evaluating the expectation value at $p=2$ is sufficient to solve #P-hard counting problems. The author concludes that their results imply that if one could efficiently evaluate QAOA expectation values to exponential precision, the polynomial hierarchy would collapse to its lowest level ($P=PH$). This has implications for hybrid algorithms that rely on classical processing of quantum expectation values, suggesting that such approaches may face fundamental computational barriers in the worst case if high precision is required.