⚛️ quantum physics

Refuting the QAOA fixed-angle conjecture

This paper refutes the fixed-angle conjecture for the Quantum Approximate Optimization Algorithm (QAOA) by demonstrating its failure on 9-regular graphs at depth-2, while simultaneously proving the conjecture holds for depth-1 on any regular graph and for any depth on 2-regular graphs.

Original authors: Lennart Binkowski

Published 2026-09-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Lennart Binkowski

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

In the race to build useful quantum computers, scientists are constantly looking for ways to solve complex puzzles faster than classical machines ever could. One of the most promising tools for this task is an algorithm called the Quantum Approximate Optimization Algorithm, or QAOA. Think of it as a sophisticated search engine for finding the best possible solution to a problem, such as dividing a group of people into two teams so that the number of friendships broken between the teams is minimized. To make this search work, the algorithm uses a set of adjustable knobs, known as parameters, which guide the quantum computer through a landscape of possibilities. The challenge is that finding the perfect setting for these knobs is often harder than solving the original problem itself, especially as the problems get bigger.

For years, researchers have hoped for a shortcut. They wondered if there were a single, universal setting for these knobs that would work well for almost any problem of a certain type, regardless of the specific details of the puzzle. This idea, known as the fixed-angle conjecture, suggested that once scientists found the best settings for a simple, tree-like structure, those same settings would perform just as well on much more complex, tangled networks. If true, this would be a massive breakthrough, allowing quantum computers to tackle huge, real-world problems without needing to spend years recalibrating for each new situation. It promised a reliable, one-size-fits-all key for a vast array of locks.

A recent study by physicist Lennart Binkowski has now shown that this hope is misplaced for a significant class of problems. While the idea holds true for very simple networks and for the simplest version of the algorithm, it fails when the algorithm is made slightly more powerful and applied to highly connected networks. Specifically, the study proves that for a network where every point is connected to nine others, the universal settings do not work as well as hoped. The researcher demonstrated this by constructing a specific, highly symmetric network made of two groups of nine points, where every point in one group is connected to every point in the other. When the algorithm used the "universal" settings derived from the simple tree structure, it performed noticeably worse on this specific network than it did on the tree itself.

This finding is not a guess or a rough estimate; it is a rigorous mathematical proof backed by precise computer simulations. The study used advanced computational techniques to map out every possible setting for the algorithm's knobs, ensuring that no better setting was missed. The researchers found that for this specific nine-connected network, there is no single setting that can match the performance of the tree-based settings. In fact, the universal settings were strictly worse, proving that the algorithm's behavior is far more sensitive to the shape of the network than previously believed. This result effectively closes the door on the idea that a single set of parameters can guarantee top performance across all regular networks of this complexity.

However, the story is not entirely one of failure. The paper also confirms that the fixed-angle idea does work in other important scenarios. It holds true for the simplest version of the algorithm, where only one layer of operations is used, regardless of how connected the network is. It also works for networks where each point is connected to only one or two others, which are essentially simple lines or rings. These positive results provide a solid foundation for understanding where the algorithm is reliable. But the discovery that it breaks down for deeper, more complex settings on highly connected graphs serves as a crucial warning. It tells scientists that they cannot simply copy-paste settings from simple models to complex ones. Instead, they must continue to develop methods to find the best settings for each specific problem, acknowledging that the landscape of quantum optimization is more varied and challenging than the fixed-angle conjecture had suggested.

The research relied on a clever combination of mathematical proofs and computer simulations to reach these conclusions. For the part of the study that disproved the conjecture, the team used a specialized simulator capable of tracking the quantum state of the system with extreme precision. They did not just test a few random settings; they systematically checked the entire range of possibilities to ensure that the "universal" settings were indeed the best the algorithm could do on the simple tree, and then proved that those same settings failed on the complex network. This level of certainty is rare in this field, where many results are based on approximations. By proving that the performance gap is real and unavoidable for this specific case, the study forces a reevaluation of how we approach quantum optimization.

The implications of this work are subtle but significant for the future of quantum computing. It suggests that while the dream of a universal parameter set is appealing, the reality of quantum mechanics is more nuanced. The algorithm's success depends heavily on the specific geometry of the problem it is trying to solve. For networks with many short loops and high connectivity, the simple tree models used to derive the universal settings are not a good enough guide. This does not mean the algorithm is useless; it simply means that the path to its success requires more tailored strategies. Scientists will need to invest in finding better ways to optimize these settings for specific types of problems, rather than hoping for a single magic solution that works everywhere.

In the end, this paper serves as a necessary correction to the field's expectations. It clarifies the boundaries of what is currently possible with quantum optimization algorithms. By showing exactly where the fixed-angle conjecture fails, it helps researchers focus their efforts on the right problems and develop more robust methods for the future. The work highlights that while quantum computers hold great promise, unlocking their full potential will require a deep, case-by-case understanding of the problems they are asked to solve, rather than relying on broad generalizations. The journey to practical quantum advantage is paved with these kinds of precise discoveries, which chip away at our assumptions and bring us closer to a realistic understanding of the technology's capabilities.

Technical Summary: Refuting the QAOA Fixed-Angle Conjecture

Problem Statement
The Quantum Approximate Optimization Algorithm (QAOA) is a leading near-term quantum algorithm for combinatorial optimization, particularly for the MaxCut problem. A significant challenge in QAOA is the computational cost of finding globally optimal parameters ( $\beta, \gamma$ ) for large problem instances, which involves high-dimensional, non-convex optimization. To address this, the "fixed-angle conjecture" was proposed (initiated by Wurtz and Love [9] and extended by Wurtz and Lykov [10]). This conjecture posits that for any $d$ -regular graph, the QAOA performance using parameters optimized specifically for a "tree-like" subgraph (a graph with large girth, specifically $girth \ge 2(p+1)$ ) serves as a lower bound for the performance on any $d$ -regular graph of the same degree. If true, this would allow for parameter transfer from small, tree-like instances to arbitrarily large, complex graphs without re-optimization. While proven for $d=3$ and $p \le 2$ , and numerically supported up to $p=11$ , the general validity for arbitrary depth $p$ and degree $d$ remained unproven.

Methodology
The paper employs a combination of analytical proofs and rigorous numerical verification to test the conjecture across different regimes of depth ( $p$ ) and regularity ( $d$ ).

Analytical Proofs for Special Cases:
- Case $p=1$ : The author utilizes closed-form expressions for single-edge expectation values derived by Wang et al. [13]. By analyzing the difference between the tree-optimal performance and the performance on a general graph, the proof employs elementary binomial identities to show monotonic behavior regarding the number of triangles. This establishes that for $p=1$ , the conjecture holds for all $d$ .
- Case $d \le 2$ : For 2-regular graphs (disjoint unions of cycles), the paper leverages recent work by Marwaha [14] connecting QAOA to quantum signal processing and Laurent polynomials. This framework allows for a rigorous lower-bounding of the approximation ratio on cycles using tree-optimal parameters, proving the conjecture for all $p$ when $d \le 2$ .
Counterexample Construction ( $p=2, d=9$ ):
- Hypothesis Generation: The author hypothesizes that the conjecture fails for bipartite graphs containing many short even cycles (specifically 4-cycles), which are visible to the QAOA at $p=2$ but do not increase the number of uncut edges ( $\nu$ ) in the maximum cut. The complete bipartite graph $K_{d,d}$ is identified as the structure maximizing 4-cycles per edge.
- Simulation Strategy: To avoid the pitfalls of local optima in numerical searches, the author uses an exact Dicke state simulator. This exploits the symmetry of $K_{d,d}$ (specifically the $Sym(d) \times Sym(d) \rtimes \mathbb{Z}_2$ automorphism group) to reduce the simulation dimension from $2^{2d}$ to $(d+1)(d+2)/2$ .
- Rigorous Verification: Instead of merely finding a local optimum on the tree that performs better on the graph, the paper proves a stronger statement: For all parameter values $(\beta, \gamma)$ where the tree performance is above a certain threshold $b$ , the performance on $K_{9,9}$ is strictly worse. This is achieved using arbitrary-precision midpoint-radius interval arithmetic (Arb) to cover the entire bounded parameter space, ensuring no global optima are missed due to floating-point errors or local search limitations.

Key Contributions and Results
The paper presents three primary findings regarding the fixed-angle conjecture:

Validation for $p=1$ : The conjecture is proven true for all $d$ -regular graphs when the QAOA depth is 1. The proof relies on the analytic form of the expectation values and the fact that bipartite graphs (the worst-case candidates) are triangle-free.
Validation for $d \le 2$ : The conjecture is proven true for all depths $p$ on 1-regular and 2-regular graphs. This utilizes the connection between QAOA and quantum signal processing to bound the performance on cycles.
Refutation for General $d$ and $p$ : The paper provides a concrete counterexample disproving the conjecture in the general case. Specifically, for depth $p=2$ $p = 2$ and degree $d=9$ $d = 9$ , the complete bipartite graph $K_{9,9}$ $K_{9, 9}$ yields a strictly lower approximation ratio using tree-optimal parameters than the tree itself.
- The tree-optimal value $f^{tree,*}_{2,9}$ is bounded below by $b \approx 0.6391275$ .
- For all parameters achieving this tree performance, the performance on $K_{9,9}$ is strictly lower by at least $c \approx 0.0029$ .
- This demonstrates that parameters optimized for tree-like structures do not guarantee optimal or even minimal performance guarantees on dense bipartite graphs with short cycles.

Significance and Claims
The paper claims to definitively refute the general "fixed-angle conjecture" for QAOA on $d$ -regular graphs. The significance lies in demonstrating that the strategy of transferring parameters from tree-like subgraphs to general graphs is not universally valid.

Limitation of the Strategy: The counterexample at $d=9$ shows that the "performance guarantee" provided by tree subgraphs does not naturally extend to all regular graphs, particularly those with high degrees and short even cycles.
Distinction from Large-Loop Conjecture: The paper clarifies that while the fixed-angle conjecture (using tree parameters on any graph) is false, the weaker "large-loop conjecture" (comparing the graph's own optimal parameters to the tree's optimal performance) remains unrefuted. In fact, for $K_{9,9}$ , the graph's own optimal parameters still outperform the tree's optimal performance, consistent with the large-loop conjecture.
Scope of Validity: The positive results are limited to specific regimes ( $p=1$ for all $d$ , and $d \le 2$ for all $p$ ). The author notes that for $d=1, 2$ , the MaxCut problem is trivial, so the failure of the conjecture at higher $d$ and $p$ is the critical finding for non-trivial quantum advantage scenarios.

The work concludes that while the fixed-angle approach offers a promising parameter-free strategy for specific low-depth or low-degree cases, it cannot be adopted as a general solution for arbitrary $d$ -regular graphs without re-optimization.

More like this