The p -stage Quantum Approximate Optimization Algorithm (QAOA p ) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond p=1 . We analyze QAOA 2 for the maximum cut problem (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any D -regular graph of girth >5 (i.e. without triangles, squares, or pentagons).We show that for all degrees D≥2 and every D -regular graph G of girth >5 , QAOA 2 has a larger expected cut fraction than QAOA 1 on G . However, we also show that there exists a 2 -local randomized classical algorithm A such that A has a larger expected cut fraction than QAOA 2 on all G . This supports our conjecture that for every constant p , there exists a local classical MAX-CUT algorithm that performs as well as QAOA p on all graphs.
The Quantum Approximate Optimization Algorithm (QAOA) is widely studied for combinatorial optimization and has achieved significant advances both in theoretical guarantees and practical performance, yet for general combinatorial optimization problems the expected performance and classical simulability of fixed-round QAOA remain unclear. Focusing on Max-Cut, we first show that for general graphs and any fixed round
p≥2, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is
NP-hard, and that approximating this expectation within additive error
2−O(n) in the number
n of vertices is already
NP-hard. To evaluate the expected performance of QAOA, we propose a dynamic programming algorithm leveraging tree decomposition. As a byproduct, when the
p-local treewidth grows at most logarithmically with the number of vertices, this yields a polynomial-time \emph{exact} evaluation algorithm in the graph size
n. Beyond Max-Cut, we extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO). Finally, we provide reproducible evaluations for rounds up to
p=3 on representative structured families, including the generalized Petersen graph
GP(15,2), double-layer triangular 2-lifts, and the truncated icosahedron graph
C60, and report cut ratios while benchmarking against locality-matched classical baselines.
The Maximum Cut (MaxCut) problem is NP-Complete, and obtaining its optimal solution is NP-hard in the worst case. As a result, heuristic-based algorithms are commonly used, though their design often requires significant domain expertise. More recently, learning-based methods trained on large (un)labeled datasets have been proposed; however, these approaches often struggle with generalizability and scalability. A well-known approximation algorithm for MaxCut is the Goemans-Williamson (GW) algorithm, which relaxes the Quadratic Unconstrained Binary Optimization (QUBO) formulation into a semidefinite program (SDP). The GW algorithm then applies hyperplane rounding by uniformly sampling a random hyperplane to convert the SDP solution into binary node assignments. In this paper, we propose a training-data-free approach based on a non-episodic reinforcement learning formulation, in which an agent learns to select improved rounding hyperplanes that yield better cuts than those produced by the GW algorithm. By optimizing over a Markov Decision Process (MDP), our method consistently achieves better cuts across large-scale graphs with varying densities and degree distributions.