Abstract This paper studies how much Quantum Processing Unit (QPU) work can be avoided while preserving optimization quality in the Quantum Approximate Optimization Algorithm (QAOA). Using exact statevector simulation of QAOA on six graph optimization problems across seven graph families, three baselines are compared: a naive QPU-centric workflow with 30 quantum evaluations, a best-practice workflow that separates classical parameter optimization from a single QPU evaluation, and a classical-only solver. Six QPUminimization strategies are evaluated: preprocessing, pretraining, surrogate modeling, adaptive stopping, adaptive shots, and measurement reuse. Quality is measured using normalized expected value rather than the saturated best-of-b metric. The key findings are: the best-practice baseline achieves 510- to 2070-fold shot reduction across 8 to 16 qubits with at most 0.4 percent quality loss relative to naive QAOA; quality improves with QAOA depth from 0.82 to 0.91 while the gap between naive and best-practice remains negligible; four of six strategies achieve 100 percent quality retention at depth 3; quality is stable across graph families ranging from 0.77 to 0.87; and a structural predictor achieves perfect prediction on held-out graph families. These results support the thesis that the required QPU budget is a structured, predictable function of the problem instance and workflow policy, rather than a fixed algorithmic constant.
Abstract This paper studies how much Quantum Processing Unit (QPU) work can be avoided while preserving optimization quality in the Quantum Approximate Optimization Algorithm (QAOA). Using exact statevector simulation of QAOA on six graph optimization problems across seven graph families, three baselines are compared: a naive QPU-centric workflow with 30 quantum evaluations, a best-practice workflow that separates classical parameter optimization from a single QPU evaluation, and a classical-only solver. Six QPUminimization strategies are evaluated: preprocessing, pretraining, surrogate modeling, adaptive stopping, adaptive shots, and measurement reuse. Quality is measured using normalized expected value rather than the saturated best-of-b metric. The key findings are: the best-practice baseline achieves 510- to 2070-fold shot reduction across 8 to 16 qubits with at most 0.4 percent quality loss relative to naive QAOA; quality improves with QAOA depth from 0.82 to 0.91 while the gap between naive and best-practice remains negligible; four of six strategies achieve 100 percent quality retention at depth 3; quality is stable across graph families ranging from 0.77 to 0.87; and a structural predictor achieves perfect prediction on held-out graph families. These results support the thesis that the required QPU budget is a structured, predictable function of the problem instance and workflow policy, rather than a fixed algorithmic constant.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to its expected robustness to systematic errors and the short circuit depth, it is one of the promising candidates likely to run on near-term quantum devices. We project the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, both for exact or approximate solution. When comparing approximate solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we introduce performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for addressing combinatorial optimization problems on near-term quantum hardware. In this work, we conduct an empirical evaluation of QAOA on the Max-Cut problem, using the Goemans-Williamson (GW) algorithm as a classical baseline for comparison. Unlike many prior studies, our methodology treats QAOA implementations as black-box optimizers, relying solely on default parameter settings without manual fine-tuning. We evaluate specific off-the-shelf QAOA implementations under default settings, not the algorithmic potential of QAOA with optimized parameters. This reflects a more realistic use case for end users who may lack the resources or expertise for instance-specific optimization. To facilitate fair and informative evaluation, we construct benchmark instances using well-known graph generation models that emulate practical graph structures, avoiding synthetic constructions tailored to either quantum or classical algorithms. A central component of our analysis is a per-shot statistical framework, which tracks the quality of QAOA outputs as a function of the number of circuit executions. This enables probabilistic comparisons with the GW algorithm by examining when and how frequently QAOA surpasses classical performance baselines such as the GW expectation and lower bound. Our results provide insight into the practical applicability of QAOA for Max-Cut and highlight its current limitations, offering a framework that can guide the assessment and development of future QAOA implementations.
Near-term quantum approaches to combinatorial optimization are limited by qubit counts, circuit fidelity, sampling cost, and the difficulty of encoding constraints, while machine learning is increasingly used to configure and control quantum optimization workflows. We call such workflows adaptive: decisions conventionally fixed in advance, from formulation and penalties to shot budgets, backends, and whether to invoke a quantum processor at all, are made by learned policies that respond to the instance, the progress of the solve, or the hardware. This review examines three paradigms, AI for quantum optimization, quantum for AI-driven optimization, and AI-quantum co-optimization, and organizes the literature by the decision being learned rather than by application. A structured search identified a 119-paper corpus, of which 67 papers form an evidence core coded in detail. The evidence is considerably stronger for AI-assisted quantum optimization than for the reverse direction: learning already reduces quantum evaluations, improves initialization, supports decomposition and penalty control, and mitigates noise, whereas evidence that quantum computation improves learned optimizers remains largely confined to small-scale simulation. Experimental controls are thin: of 52 studies in the three paradigms, 22 include no classical baseline, the quantum contribution is fully isolated in 10 of 24 where an ablation applies, and the median largest experiment uses 16 qubits. We introduce an M0-M5 evidence hierarchy, from simulation to practical quantum advantage, and find no broadly convincing result at the highest level. We argue that scaling is increasingly a systems problem: the question is not only whether a problem fits on a quantum processor, but how classical and quantum resources should be allocated across the optimization process.
The quantum approximate optimization algorithm (QAOA) is a leading variational approach to combinatorial optimization, but its practical performance depends strongly on objective design, parameter search, and shot allocation. We present a resource-efficient QAOA framework that uses the cut value of the most probable measured bitstring as the optimization objective, combines it with Bayesian optimization, and adaptively allocates shots using dual criteria based on mode confidence and normalized cut-value variance. Numerical experiments on 3-regular MaxCut show that, for both unweighted and weighted instances, the proposed scheme achieves discrete-solution quality comparable to that of the conventional expectation-based objective while typically requiring fewer total shots to reach the same final mode accuracy. These results indicate that reorganizing QAOA around the maximum-probability bitstring provides an effective route to improving practical performance under limited measurement budgets.
Optimizing of a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs). We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, η, which we present in a manner to expose the QAOA as a transporter of probability. Using η as an application specific benchmark of performance, we measure it on selection of QPUs as a function of QAOA circuit depth p. At n=2 (2 qubits) we find peak solution quality at p=5 for most systems and for n=3 this peak is at p=4 on a trapped ion QPU. Increasing solution quality with p is also observed using variants of the more general Quantum Alternating Operator Ansätz at p=2 for n=2 and 3 which has not been previously reported. In identical measurements, η is observed to be variable at a level exceeding the noise produced from the finite number of shots. This suggests that variability itself should be regarded as a QPU performance benchmark for given applications. While studying the ideal execution of QAOA, we find that p=1 solution quality degrades when the portfolio budget B approaches n/2 and increases when B≈1 or n−1. This trend directly corresponds to the binomial coefficient nCB and is connected with the recently reported phenomenon of reachability deficits. Derivative-requiring and derivative-free classical optimizers are benchmarked on the basis of the achieved η beyond p=1 to find that derivative-free optimizers are generally more effective for the given computational resources, problem sizes and circuit depths.