A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation

• URL: http://arxiv.org/abs/2511.20212v1
• Date: Tue, 25 Nov 2025 11:35:37 GMT
• Title: A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation
• Authors: Jingheng Wang, Shengminjie Chen, Xiaoming Sun, Jialin Zhang,
• Abstract summary: We show that for general graphs and any fixed round $pge2$, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is $mathrmNP$-hard.<n>We extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO)
• Score: 5.137643077079792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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\ge2$, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is $\mathrm{NP}$-hard, and that approximating this expectation within additive error $2^{-O(n)}$ in the number $n$ of vertices is already $\mathrm{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 $C_{60}$, and report cut ratios while benchmarking against locality-matched classical baselines.

Related papers

• Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
  We study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs.<n>We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size.<n>Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.
  arXiv  Detail & Related papers  (2026-02-05T18:11:18Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  We show that our algorithms converge without any prior knowledge on the parameters of the problem.<n>All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function.<n>We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
  The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most prominent algorithms to solve multi-objective optimization problems. We give the first proven performance guarantees for a classic optimization problem, the NP-complete bi-objective minimum spanning tree problem.
  arXiv  Detail & Related papers  (2023-05-22T19:59:19Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to optimization problems. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. We make an optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value.
  arXiv  Detail & Related papers  (2021-10-27T06:35:59Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  The current practical BO algorithms have regret bounds ranging from $mathcalO(fraclogNsqrtN)$ to $mathcal O(e-sqrtN)$, where $N$ is the number of evaluations. This paper explores the possibility of improving the regret bound in the noiseless setting by intertwining concepts from BO and tree-based optimistic optimisation. We propose the BOO algorithm, a first practical approach which can achieve an exponential regret bound with order $mathcal O(N-sqrt
  arXiv  Detail & Related papers  (2021-05-10T13:07:44Z)
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
  We show that for all degrees $D ge 2$ of girth $> 5$, QAOA$ has a larger expected cut fraction than QAOA$$ on $G$. We conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all graphs.
  arXiv  Detail & Related papers  (2021-01-14T09:17:20Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
  arXiv  Detail & Related papers  (2020-05-18T14:23:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.