PaperlayerView exact revision on arXiv

Source-linked AI summary

A Review on Quantum Approximate Optimization Algorithm and its Variants

Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, Alessandro Summer

arXiv:2306.09198v2quant-ph

TL;DR

The review addresses whether QAOA can outperform classical algorithms and when it should be used for hard combinatorial optimization. It synthesizes QAOA variants, optimization methods, problem-instance performance, and hardware constraints, finding both specific asymptotic advantages and substantial near-term limitations.

  • Problem

    The review tackles conflicting evidence about QAOA’s ability to outperform classical algorithms and provide practical quantum advantage under current noise and errors.

  • Method

    The paper comprehensively reviews QAOA performance, variants, parameter optimization, problem applications, noise, and hardware-specific implementations, and experimentally evaluates selected variants on MaxCut.

  • Results

    At p ≥11, QAOA could outperform assumption-free classical SDP algorithms for MaxCut on high-girth D-regular graphs and the SK model; at p = 1, it surpassed a threshold algorithm for certain Max-kXOR instances.

  • Takeaways & Limitations

    QAOA’s prospects depend on problem structure, circuit depth, optimization, and hardware conditions rather than constituting a broadly established near-term quantum advantage.

  • Takeaways & Limitations

    The review’s experiments omit numerous findings and use a scope that is being expanded to newer variants, more graph types and sizes, more optimizers, and larger node counts.

Abstract

from arXiv · show

The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve combinatorial optimization problems that are classically intractable. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios, its applicability across various problem instances, and considerations of hardware-specific challenges such as error susceptibility and noise resilience. Additionally, we conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm. We aim to provide insights into key questions about the algorithm, such as whether it can outperform classical algorithms and under what circumstances it should be used. Towards this goal, we offer specific practical points in a form of a short guide. Keywords: Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Algorithms (VQAs), Quantum Optimization, Combinatorial Optimization Problems, NISQ Algorithms

1 Introduction

QAOA is a variational quantum algorithm for approximate solutions to hard combinatorial optimization problems on near-term quantum hardware. This review examines its variants, performance, optimization strategies, and hardware-specific challenges to guide when it may be useful.

  • QAOA encodes an optimization problem’s Hamiltonian into a layered quantum circuit and measures the circuit after variational-parameter optimization to construct an approximate solution.It combines adiabatic time evolution with circuit layering in a hybrid quantum-classical setting.
  • QAOA has been applied to problems including MaxCut, Maximum Independent Set, BPSP, BLLS, Max E3LIN2, Multi-Knapsack, and QUBO.The review also notes applications such as portfolio optimization, tail assignment, and object detection.
  • The review addresses conflicting views about whether QAOA can outperform classical algorithms and provide practical quantum advantage under current noise and errors.It evaluates performance across problem instances and considers noise, hardware-tailored implementations, and parameter optimization.
  • The paper surveys QAOA extensions and variants, optimization strategies, efficiency, performance, noise effects, and hardware-specific implementations.It also experimentally assesses selected variants on MaxCut.

2 Background

Combinatorial optimization seeks optimal assignments over discrete feasible solutions, but its solution spaces can grow exponentially and make exact classical optimization intractable. Approximation algorithms target efficiently computable solutions with guarantees, while QUBO and quantum approaches are discussed as routes toward these problems.

  • Combinatorial optimization selects an optimal solution from discrete feasible assignments under constraints using a minimization or maximization objective.The objective can be represented as a weighted sum of satisfied clauses.
  • The solution space of many combinatorial problems grows explosively with input size, and exact solution finding commonly belongs to the NP complexity class.Classical algorithms therefore require exponentially scaling time for optimal solutions in these cases.
  • Approximate optimization algorithms seek good solutions in polynomial time and evaluate them using an approximation ratio relative to the optimum.The ratio is ideally close to 1 and can provide lower bounds on solution quality.
  • For some problems, the gap between approximate and optimal solutions cannot be reduced in polynomial time unless P = NP, creating hardness-of-approximation barriers.Such barriers make tight lower bounds difficult to obtain.
  • QUBO problems are generally NP-complete, whereas quantum superposition may accommodate exponentially growing solution spaces and QAOA is designed to find approximate QUBO solutions.The passage presents this as a potential route for addressing classical optimization hardness.

2.1 MaxCut Problem Overview

MaxCut partitions graph vertices into two subsets to maximize the total weight of crossed edges. Because exact MaxCut is NP-hard, approximate algorithms are central, with classical and quantum methods compared against approximation-quality benchmarks.

  • Figure 1 depicts a 6-vertex graph with 11 equal-weight edges whose shown partition crosses 8 edges.The red and blue groups define the cut, represented by the black curve.
  • MaxCut divides graph vertices into two complementary subsets so that the sum of weights on crossed edges is maximized.The unweighted problem is the special case where every edge weight equals 1.
  • MaxCut is NP-hard, so polynomial-time approaches focus on cuts whose value approaches the optimum Cmax.The conjectured hardness threshold is an approximation ratio above 16/17 ≃0.9412.
  • The Goemans-Williamson algorithm is identified as the best-performing classical MaxCut algorithm, with α ≃0.878.This benchmark motivates studying QAOA as a possible source of good approximate solutions.

2.2 QUBO Problems and Applications

QUBO expresses broad classes of discrete optimization problems using binary variables and quadratic objectives, including mappings from many NP-complete problems. The formulation is unconstrained and can be extended to higher-order interactions through ancillary variables.

  • QUBO problems are NP-complete, and NP-complete problems can be mapped to QUBO in polynomial time.The cited mapping includes all 21 Karp NP-complete problems.
  • QUBO represents decision variables as a binary vector x = (x1, …, xn) with x ∈ {0, 1}^n.Relevant mapped problems include Graph Coloring, Number Partitioning, and Quadratic Knapsack.
  • QUBO can be formulated as either a minimization or maximization problem by flipping the sign of the cost function or its coefficients.This changes the optimization direction without changing the binary-variable representation.
  • QUBO is unconstrained, meaning that its variables have no constraints imposed on them.
  • QUBO instances correspond one-to-one with Ising models through the transformation zi = 2xi − 1.Ising variables therefore replace binary QUBO variables with values in {−1, 1}.
  • Higher-order interactions can be reduced to quadratic form by introducing an ancillary gadget variable such as x′ := xixj.Then a third-order term xixjxk becomes the quadratic term x′xk.

2.3 Classical Algorithms for MaxCut Problem

Classical MaxCut methods range from simple heuristics to approximation algorithms with formal guarantees. The Goemans–Williamson algorithm uses semidefinite programming and randomized rounding to obtain a polynomial-time solution with a strong guarantee.

  • MaxCut is NP-hard, although approximation algorithms and heuristics can provide good solutions within reasonable time for practical instance sizes.
  • Greedy algorithms make locally optimal choices efficiently but can produce suboptimal solutions for problems with complex variable interactions.Their myopic strategy focuses on the current step rather than the global structure.
  • Local search iteratively improves an initial solution by exploring neighboring solutions, so its quality depends strongly on initialization and neighborhood design.
  • Goemans–Williamson algorithm: The Goemans–Williamson algorithm relaxes binary MaxCut variables into unit vectors, solves the resulting semidefinite program, and randomly rounds the vectors into a feasible cut.
  • Goemans–Williamson algorithm: 0.87856 is the Goemans–Williamson approximation ratio guarantee for MaxCut, meaning the returned cut has at least 87.856% of the optimal cut weight.
  • Goemans–Williamson algorithm: Under the Unique Games Conjecture, the 0.87856 approximation ratio is the best possible for any polynomial-time algorithm.

2.4 Variational Quantum Algorithms

Variational quantum algorithms use parameterized quantum circuits within hybrid quantum-classical optimization loops. Their flexibility supports problem- and hardware-informed ansätze, but training can be hindered by barren plateaus and hardware limitations.

  • VQAs use the variational principle to optimize a parameterized trial wave function for an observable, typically a Hamiltonian expectation value.
  • Ansatz design: Ansatz selection can be problem-inspired or hardware-efficient, trading problem specificity against reduced circuit depth and hardware-native implementation.
  • Hybrid optimization: VQE exemplifies a hybrid algorithm in which a quantum circuit estimates states or energies while a classical optimizer updates parameters.
  • Ansatz design: More expressive variational forms can improve eigenvalue estimation accuracy by enabling finer tuning through additional parameters, gates, and entanglement schemes.
  • Hybrid optimization: Hybrid computing does not always provide the most efficient solution because some algorithms can be more powerful when run only on quantum hardware.
  • Training challenges: Barren plateaus make gradients exponentially small in qubit number, causing parameter optimization to stall for affected circuit families.

2.5 The Quantum Approximate Optimization Algorithm (QAOA)

QAOA is a discretized, variational form of adiabatic optimization that alternates cost and mixer layers to encode and approximately solve combinatorial problems. Its hybrid workflow trains circuit parameters classically and evaluates the resulting state quantum mechanically.

  • QAOA encodes an optimization objective in a cost Hamiltonian and uses repeated variational cost and mixer layers to search for a high-quality bitstring.
  • The original QAOA was introduced as a VQA for approximate MaxCut solutions suitable for NISQ devices.
  • Circuit construction: Mixer elements can use single-qubit RX rotations, while two-qubit Pauli-Z interactions in the cost layer decompose into CNOT gates surrounding an RZ rotation.
  • Hamiltonians: For MaxCut, the cost Hamiltonian is diagonal in the computational basis and maps each binary variable to a Pauli-Z operator.
  • Initialization: The standard QAOA initialization uses the highest-energy eigenstate of the mixer Hamiltonian rather than the ground state, as in MaxCut.
  • Circuit construction: A QAOA layer contains one cost unitary and one mixer unitary, and deeper circuits stack these layer pairs.
  • Hybrid workflow: QAOA initializes a state, applies p parameterized layer pairs, measures the cost expectation, and uses a classical optimizer to update γ and β.

3 QAOA Analysis

The review analyzes QAOA across ansatz design, optimization, resources, solution quality, noise, and hardware-specific implementation. It evaluates strengths and limitations while organizing the algorithm’s broader features for practical assessment.

  • Figure 4 presents a general scheme of QAOA and its associated features.
  • The analysis covers ansatz variants, parameter optimization, computational resource efficiency, solution quality, noise and errors, and hardware-specific approaches.
  • The review evaluates QAOA’s strengths and limitations in light of recent advancements and studies in the literature.

3.1 Ansatz Variants

QAOA ansatz variants modify circuit structure, parameterization, or operator selection to improve approximation quality, convergence, computational cost, or hardware suitability. The review covers multi-angle, counterdiabatic, adaptive-bias, iterative, and recursive approaches, while emphasizing trade-offs between flexibility, depth, optimization complexity, and measurement overhead.

  • Ansatz design: The QAOA ansatz consists of layered cost and mixer operators, with its design depending on the problem structure and hardware constraints.Ansatz design must balance specificity and generality to avoid overfitting while retaining broad applicability.
  • Multi-angle QAOA: ma-QAOA assigns separate angles to individual cost and mixer terms, increasing the circuit parameter count to (n+m)p.Vanilla QAOA is recovered when parameters within each layer share the same values.
  • Multi-angle QAOA: 33% parameter reduction through graph symmetries had little to no impact on the objective function, while ma-QAOA achieved an approximation ratio at least as good as vanilla QAOA.Empirical results also suggested that ma-QAOA may require shallower circuits despite more complex parameter optimization.
  • QAOA+: QAOA+ adds a multi-parameter ZZ layer and mixer-X layer to p = 1 QAOA, producing higher MaxCut approximation ratios while remaining shallower than p = 2 QAOA.For N qubits, the added depth scales with a set of 2N −1 parameters; QAOA+ showed performance similar to p = 2 QAOA on random regular graphs.
  • Counterdiabatic QAOA: Counterdiabatic variants add problem-dependent driving terms to accelerate convergence and reduce circuit depth, and DC-QAOA outperformed standard QAOA across the tested problem classes.The reported applications included Ising models, classical optimization problems, and the k-spin model.
  • Adaptive variants: ab-QAOA adaptively biases mixer operators and reduced computation time polynomially for a fixed accuracy and gate count, with larger gains as problem size increased.ADAPT-QAOA instead selects mixers from an operator pool, converging faster on MaxCut while reducing CNOT gates and optimization parameters by about 50% each.
  • Adaptive and recursive variants: ADAPT-QAOA requires additional measurements for mixer selection, with overhead depending on the size of its operator pool.Recursive QAOA addresses locality limitations by using ZZ correlations to eliminate qubits, repeatedly solving reduced Hamiltonians before a final classical solution.

3.1.7 Quantum alternating operator ansatzes

Quantum alternating-operator ansatzes generalize QAOA by replacing fixed mixer designs with operators that can encode problem constraints and support broader feasible-state spaces. Variants such as GM-QAOA and FALQON target exact operator implementation, stable sampling, and quantum-based parameter initialization.

  • Constraint encoding: QAOAnsatz encodes graph constraints through specialized mixers rather than only adding penalties to the cost Hamiltonian.Examples include XY-mixers and partial mixers, with a unified approach also investigated.
  • QAOAnsatz: QAOAnsatz alternates generalized phase-separation and mixing operators, with the latter depending on the domain structure and constraints.A depth-p circuit applies p alternating operator pairs.
  • GM-QAOA: GM-QAOA uses Grover-like selective phase-shift mixing operators for constrained and unconstrained NP optimization problems.Its operators are implemented exactly with standard gate sets, avoiding Trotterization and other Hamiltonian-simulation errors.
  • GM-QAOA: GM-QAOA samples solutions with the same objective value at equal amplitude and was demonstrated on traveling-salesman, k-Vertex-Cover, and portfolio-rebalancing problems.For portfolio rebalancing, mixing can remain within the feasible subspace while connecting all feasible states.
  • Feedback-based approaches: FALQON uses measurement-based feedback to assign circuit parameters constructively, producing estimates that improve monotonically with circuit depth without classical optimization.FALQON+ uses the resulting parameters to warm-start QAOA on NISQ devices, increasing success probability with minimal depth and noise degradation.

3.2 Parameter Optimization

QAOA parameter optimization uses transferability, symmetry, machine learning, gradient-free search, evolutionary methods, and robust control to address increasingly difficult and noisy optimization landscapes. Reported studies show faster convergence, reduced circuit calls, improved approximation ratios, or error suppression, while scalability and noise remain concerns.

  • Initial parameters: Parameter transferability predicts reusable QAOA initial values from local subgraph characteristics across related graph instances.This approach reuses parameters learned for one problem as starting points for similar problems.
  • Gradient-free methods: Gradient-free optimizers reduce reliance on derivatives, but realistic NISQ noise can significantly impair variational optimization and necessitate method-specific tuning.Studies tested gradient-free methods across QAOA and broader hybrid quantum-classical problems.
  • Evolutionary optimization: Genetic algorithms statistically outperform other gradient-free methods in approximation ratio for the same circuits on problems with 5 to 9 nodes.The authors identify scalability and premature convergence as limitations.
  • Noise-robust optimization: Robust control optimization with sequential convex programming suppresses QAOA simulation error when the error source is known, even if its magnitude is unknown.This extends parameter optimization toward noise-robust control.
  • Classical optimizers: BFGS returned optimal QAOA angles for tested graphs up to p = 2, but its behavior for larger parameter vectors remains unclear.The study also observed symmetry patterns among optimized angles.
  • Machine-learning methods: Machine-learning optimizers predict quasi-optimal parameters or learn angle assignments, reducing circuit calls or accelerating convergence with limited approximation-ratio loss.Reported examples include less than 1–2% reduction from clustering and predictions within 2.7% of optimum from a GNN.

3.3 Computational Resource Efficiency

QAOA’s resource-efficiency evidence includes speedup potential in dense graphs, minimum vertex cover, unstructured search, and selected hardware experiments. The review also emphasizes that parameter optimization, circuit depth, noise, and fault-tolerant overheads constrain practical quantum advantage.

  • Speedup potential: QAOA’s gate complexity is primarily limited by the number of required two-qubit gates, and modest-depth circuits may speed up classical methods on dense graphs.This conclusion follows an analysis that amortizes training over batches of MaxCut instances.
  • Speedup potential: QAOA solved a 10-vertex, 16-edge minimum vertex cover instance with complexity O[poly(k) + poly(p)].Here, k denotes optimization iterations and p denotes the number of QAOA layers.
  • Hardware experiments: On selected deep-circuit graph instances, QAOA’s smaller success-probability exponent implies a speedup over simulated annealing.The review states that extending this advantage to more general cases remains open.
  • Speedup potential: A QAOA-based unstructured-search algorithm achieved near-optimal query complexity T ∼O(N) with an intermediate number of layers.The result provides a quadratic speedup analogous to Grover’s algorithm.
  • Obstacles to speedup: Practical speedup may require several hundred qubits, and QAOA must run within about one minute to compete on problems with fewer than 400 variables under decoherence and dissipation.The cited analysis attributes exponential protocol cost mainly to variational-parameter optimization.
  • Obstacles to speedup: Increasing QAOA parameters can make optimization harder even when approximation quality improves or equivalent quality requires fewer layers.For ma-QAOA, gradient-component counts increase with variables, and equal-parameter convergence comparisons remain unresolved.

3.4 Quality of Solution

QAOA’s solution quality has been characterized through approximation guarantees across MaxCut and constraint-satisfaction problems, alongside comparisons with classical local, threshold, SDP, and other algorithms. Results show strong guarantees in selected graph and hypergraph regimes, but also persistent uncertainty about whether QAOA generally outperforms classical methods.

  • MaxCut guarantees: 0.6924 is QAOA1’s guaranteed approximation ratio for MaxCut on any 3-regular graph, improving on random guessing’s 0.5.For 2-regular rings with n > 2p, QAOAp achieves α ≥ (2p+1)/(2p+2), approaching optimality as p grows.
  • MaxCut guarantees: 0.7559 and 0.7924 are the guarantees reported for QAOA2 and QAOA3 on 3-regular graphs with girth greater than 5 and 7, respectively.The girth requirements arise from the large loop conjecture used in the analysis.
  • Classical comparisons: QAOA1 initially exceeded a threshold algorithm bound on triangle-free D-regular graphs, but direct calculations found the classical algorithm achieves α ≥ 1 − 0.335/√D asymptotically and outperforms QAOA1 numerically for 2 ≤ D < 1000.The earlier QAOA1 bound used c ≈ 0.303, compared with the threshold algorithm’s earlier c ≈ 0.281.
  • Classical comparisons: For high-girth random regular graphs, QAOA at p ≥ 11 can outperform assumption-free classical SDP algorithms, while the conjectured convergence to the Parisi value remains unproven.The same asymptotic relationship connects these MaxCut results with the SK model, but alternative classical algorithms still leave QAOA’s general advantage unclear.
  • Constraint-satisfaction problems: On bounded-degree Max-kXOR, QAOA1’s advantage depends on the instance family and k: it can beat threshold algorithms for some settings but loses as degree increases in others.For triangle-free Max-kXOR, QAOA1 beats the threshold algorithm for some D ≤ 27 on Max-3XOR, whereas the threshold algorithm performs better as D grows.
  • Constraint-satisfaction problems: Higher-depth analyses generalized QAOA performance formulas to Max-kXOR on large-girth regular hypergraphs, evaluating k from 3 to 6 and depths p from 1 to 14.These formulas were used to identify optimal parameters and assess solution quality across the specified problem regimes.

3.5 Noise and Errors Considerations

QAOA performance theoretically improves with deeper layering, but accumulated noise and hardware errors limit this benefit in realistic NISQ settings. Studies therefore identify finite optimal depths, severe scalability constraints, and mitigation strategies as central practical considerations.

  • Performance under noise: Increasing QAOA layers theoretically improves the approximation ratio, but deeper circuits accumulate more noise, while larger systems and higher hardware noise further hinder effectiveness.The practical layer count must balance approximation improvement against noise accumulation.
  • Local noise: Local dephasing, bit-flip, and depolarizing noise degrade output-state fidelity and approximation ratio as a power law in noise strength, with the exponent proportional to system size.This relationship supports selecting an optimal layer count for a given noise rate.
  • Scalability: Measurement requirements increase exponentially with gate error rates under local noise, yielding exponential time complexity when measurement count determines runtime.The result directly constrains QAOA scalability even when the circuit itself remains executable.
  • Correlated errors: Correlated readout noise can alter QAOA’s energy landscape and place optimization in sub-optimal regions, while precision errors cause success probability to decrease exponentially with order and noise strength.The reported correlated effects include crosstalk and parameter misspecification.
  • Quantum advantage: Theoretical and empirical studies indicate that substantial quantum advantage is unlikely at current noise levels, especially for large, dense, or nonhardware-native problems.Empirical work also finds greater noise sensitivity for high-depth QAOA and limits on beneficial layering.
  • Mitigation strategies: Hardware compilation and connectivity affect gate count and circuit depth, motivating edge-coloring, DFS-based constructions, and other hardware-aware strategies that can outperform standard QAOA implementations.On IBM’s ibmq_manhattan, the DFS method outperformed both standard QAOA and the edge-coloring implementation.
  • Mitigation strategies: Crosstalk-mitigation techniques reduced average errors by a factor > 22 on IBM devices and > 5.5 on Rigetti devices, while exponential error-suppression schemes offer further prospective improvements.The reported devices had 15 and 23 qubits, respectively.

3.6 Hardware-Specific Approaches

Hardware-specific QAOA approaches adapt ansätze, connectivity, compilation, and computational encodings to the properties of superconducting, trapped-ion, neutral-atom, and photonic platforms. These adaptations target connectivity and noise constraints while enabling problem mappings better matched to particular devices.

  • Platform-specific design: Hardware-tailored QAOA research spans superconducting qubits, trapped ions, neutral atoms, and photonic quantum computers to address connectivity and noise-related limitations.The stated goal is to broaden QAOA applicability across combinatorial optimization problems.
  • Connectivity constraints: Hardware interaction models impose distinct implementation constraints, including architecture-determined couplings for superconducting qubits and coupling-decay limitations for neutral atoms.A Rydberg parity gate was introduced to support scalable qubit remapping in neutral-atom architectures.
  • Trapped-ion approaches: Ion-native Hamiltonians enabled ansatz families for arbitrary problem Hamiltonians, and tests on 6-qubit Sherrington-Kirkpatrick instances demonstrated minimization after overcoming symmetry protection.The approach addresses the all-to-all connectivity that prevents direct SK implementation on planar processors.
  • Connectivity constraints: Global entangling operations can construct arbitrary weighted and unweighted coupling graphs with lower noise susceptibility than standard gate-based compilation, particularly for dense unweighted couplings.The approach includes operation-count bounds and a mixed-integer program for sequence optimization.
  • Qudit encodings: Qudits with d energy levels can improve hardware mappings when the problem’s color count matches d, such as choosing k = d for a k-color graph.This encoding leverages higher energy levels beyond ordinary qubit representations.
  • Photonic approaches: An MBQC QAOA for photonic computers used diagonal unitary evolution for Max-k-Cut and achieved up-to 30-fold improvement in cluster-state dimension versus gate-based QAOA circuits.The comparison concerns cluster-state dimension rather than optimization quality.

4 Experimental Results

The experiments compare QAOA variants across graph structures, sizes, circuit depths, simulation and real hardware, revealing strong dependence on problem structure, noise, and resource use.

  • Variation across graph types: Graph structure strongly influences performance: simulated mean approximation ratios reach 0.98 on complete graphs and 0.94 on regular graphs, but at most 0.92 on random graphs.For 18-node graphs, complete-graph ratios generally remain above 0.9, whereas random-graph ratios typically range from 0.6 to 0.8.
  • Effect of graph size: Mean approximation ratios generally decline as graph size increases, especially for regular and random graphs, although FALQON and vanilla QAOA appear more robust.Without noise, QAOA falls from 0.98 and 0.94 at 4 nodes to 0.83 and 0.76 at 18 nodes for regular and random graphs, respectively.
  • Balancing approximation ratio and resource use: Variant selection requires balancing approximation quality against computational resources, because higher-performing methods can require more gates, depth, or circuit evaluations.ma-QAOA may achieve higher ratios on larger graphs but uses substantially more effective circuit depth, whereas WS-QAOA can be less quantum-resource-intensive while incurring classical warm-start cost.
  • Effect of circuit layer depth: Increasing circuit depth from p = 1 to p = 8 generally improves QAOA and FALQON, with ma-QAOA showing the greatest improvement and QAOA+ and ModifiedQAOA more limited responses.Depth affects variants differently and appears less influential than other factors up to p = 8.
  • Noise-free simulations vs. real hardware: Real quantum hardware significantly reduces mean approximation ratios relative to noiseless simulations, while graph-type performance trends usually persist.The comparison indicates that hardware noise degrades all evaluated variants, even when their relative graph-structure patterns remain visible.
  • Scope and future work: The review’s experimental account is curated rather than exhaustive, with broader experiments, source code, optimizers, and larger node counts reserved for future work.The authors state that the extensive QAOA landscape prevented inclusion of numerous findings and results.

5 Discussion

QAOA shows promising advantages on selected problem instances and under specific conditions, but classical solvers remain competitive and noise limits near-term performance. The review identifies circuit depth, parameter optimization, graph structure, and hardware errors as central determinants of effectiveness.

  • Performance and quantum advantage: QAOA can outperform classical algorithms in selected settings, including high-depth MaxCut and certain Max-kXOR instances.The review reports advantages at p ≥11 for MaxCut on high-girth D-regular graphs and at p = 1 for Max-kXOR when k > 4.
  • Hardware limitations: QAOA’s general quantum advantage remains unresolved, despite compatibility with NISQ devices and evidence of noise resilience in some variants.The review calls for improved error rates, standardized experiments, and broader testing of learning-based parameter optimization on larger and more diverse instances.
  • Hardware limitations: Noise and hardware errors remain major obstacles because they degrade QAOA performance, scalability, and parameter optimization on near-term devices.The review discusses exponential degradation under increasing local noise, noise-induced barren plateaus, and the unlikelihood of near-term quantum speedup.
  • Performance and quantum advantage: QAOA’s runtime advantages have been reported for dense-graph MaxCut, large MVC instances, and specific MIS graphs.Reported speedups include exponential acceleration for large MVC problems and superlinear speedup over Simulated Annealing for selected MIS instances.
  • Performance and quantum advantage: Classical methods can match or surpass QAOA across many scenarios, including asymptotic MaxCut comparisons and some local-algorithm settings.The review cites Gaussian wave process improvements over QAOA1 and a 2-local classical MaxCut algorithm that outperforms QAOA2 on stated graph families.
  • Variants and improvements: Ansatz variants such as ab-QAOA, ADAPT-QAOA, and QAOAnsatz improve convergence, computation time, gate counts, or constraint handling relative to standard QAOA.These variants target efficiency and problem-specific structure, with ADAPT-QAOA reducing CNOT gates and optimization parameters by about 50% each in a reported setting.

6 A Practical Guide to QAOA

The practical guide matches QAOA variants and parameter strategies to problem structure, hardware constraints, and the trade-off between specificity and generality. It highlights faster convergence and improved approximation guarantees while emphasizing that QAOA is not best suited to every problem.

  • Choosing an ansatz: Variant selection should consider problem type, hardware constraints, and the trade-off between specificity and generality.Problem-specific ansatzes are especially relevant when hard constraints must remain satisfied and soft-constraint violations must be minimized.
  • Choosing an ansatz: Standard QAOA is a useful starting point for MaxCut, MVC, CSPs, MIS, unknown structures, and simple instances.The guide presents the basic ansatz as a baseline when problem structure is unknown or instances are small.
  • Ansatz variants: ma-QAOA assigns separate angles to cost and mixer elements, improving approximation ratios while potentially allowing shallower circuits.Graph symmetries can reduce the number of ma-QAOA parameters by approximately 33% with little to no objective-function impact.
  • Ansatz variants: QAOA+ adds parameterized ZZ layers to p = 1 QAOA, achieving higher approximation ratios while maintaining low circuit depth in stated MaxCut settings.Its added depth grows with the number of qubits, and it outperforms multi-angle QAOA in most reported cases.
  • Ansatz variants: DC-QAOA reduces computational complexity and circuit depth through counterdiabatic driving and is reported to outperform standard QAOA in stated applications.The listed applications include Ising models, classical optimization problems, and k-spin models.
  • Ansatz variants: ab-QAOA uses adaptive bias fields to accelerate convergence and has polynomially shorter computation time than vanilla QAOA.The reported computation-time improvement increases with problem size.
  • Ansatz variants: ADAPT-QAOA selects mixers iteratively and reportedly reduces CNOT gates and optimization parameters by about 50% each.Its operator-pool selection adds an extra computational requirement.
  • Choosing an ansatz: QAOAnsatz generalizes the operator set to support hard and soft constraints, including tailored mixers such as XY and Grover mixers.This flexibility targets feasible-subspace preservation and broader problem coverage.
Loading 2306.09198v2…