Refuting the QAOA fixed-angle conjecture

Abstract

The paper tests the fixed-angle conjecture for QAOA MaxCut: whether parameters optimal on the depth-$p$ causal tree guarantee at least the tree-optimal approximation ratio on every $d$-regular graph. This would provide worst-case guarantees without instance-specific parameter optimisation. The general conjecture is refuted at $p=2$, $d=9$ by the complete bipartite graph $K_{9,9}$. The tree optimum is rigorously enclosed between $0.6391275408952286$ and $0.6391276594250365$. Every tree-optimal parameter choice performs worse on $K_{9,9}$ by at least $0.0029209162022571854$. The proof avoids assuming that numerical optimisation found a global optimum: interval arithmetic covers the symmetry-reduced four-dimensional parameter domain and certifies the performance deficit everywhere the tree value exceeds a witnessed lower bound. Evaluation combines an existing closed-form tree expression with a symmetry-reduced Dicke-state simulator; the certificate has approximately $1.62$ million leaves and is independently checked for a strictly positive violation. Two positive regimes are also established: $p=1$ for every degree, using analytic edge expectations and triangle-counting inequalities, and $d\leq2$ for every depth, using free-fermionic and quantum-signal-processing representations. For $d=2$, the guaranteed ratio is $1-1/[2(p+1)]$. The counterexample does not resolve the conjecture for $3$-regular graphs or refute the weaker large-loop conjecture with instance-optimised parameters. Indeed, explicit parameters achieve more than $0.79287$ on $K_{9,9}$. No general failure claim is made for degrees above nine; the all-depth positive results concern classically trivial MaxCut instances.