A Review on Quantum Approximate Optimization Algorithm and its Variants

• VQAs combine parameterized quantum circuits with classical optimization, using shallow circuits to reduce susceptibility to NISQ noise.They have been applied to quantum chemistry, machine learning, and optimization.Source: §1 · p. 3
• QAOA [12] uses layered cost and mixer Hamiltonians with optimized parameters to construct approximate solutions to hard combinatorial optimization problems.Its approximation ratio CQAOA/Cmax theoretically improves with circuit depth p and approaches adiabatic evolution as p →∞.Source: §1 · p. 3
• QAOA supports problems including MaxCut [12], MIS, BPSP, BLLS, Max E3LIN2, Multi-Knapsack, and general QUBO.Reported applications span portfolio optimization, tail assignment, object detection, protein folding, and wireless scheduling.Source: §1 · p. 3
• The review addresses conflicting evidence about whether QAOA can outperform classical algorithms or achieve practical quantum advantage on noisy current hardware.It aims to identify when QAOA should be used and to assess its prospects for quantum advantage.Source: §1 · pp. 3–4
• The review surveys QAOA variants, parameter optimization, efficiency, problem-instance performance, noise, errors, and hardware-tailored implementations.It also experimentally evaluates promising variants on MaxCut [31] and provides practical guidance on choosing and optimizing QAOA approaches.Source: §1 · p. 4

• Combinatorial optimization minimizes or maximizes an objective over feasible assignments to constrained discrete variables, often represented as a weighted sum of satisfied clauses.Source: §2 · p. 4
• Knapsack, Traveling Salesman, and MaxCut are typical examples, while exact optimization is often NP-complete or NP-hard and classically requires exponentially scaling time.Source: §2 · p. 4
• Approximation algorithms seek polynomial-time solutions with approximation ratio α near 1, providing lower-bound guarantees, although hardness of approximation can preclude such guarantees unless P = NP.Source: §2 · p. 4
• Many optimization problems map to QUBO, whose exponentially large solution space motivates quantum approaches; QAOA uses quantum circuits for approximate solutions, but performance depends on problem characteristics.Source: §2 · pp. 4–5

Problem formulation

• Figure 1 illustrates a six-vertex, 11-edge equal-weight graph whose displayed maximum cut crosses 8 edges.Source: Figure 1 · p. 5
• MaxCut partitions vertices into two complementary subsets, maximizing the weighted sum of edges connecting different partitions.Weighted-MaxCut allows general positive symmetric edge weights, while plain MaxCut sets every edge weight to 1.Source: §2.1 · p. 5

Computational difficulty

• MaxCut is NP-hard, with Håstad conjecturing that approximation ratios above 16/17 ≃0.9412 are NP-hard, while Goemans–Williamson achieves α ≃0.878.These hardness and approximation results make MaxCut a paradigmatic hard combinatorial optimization problem and motivate quantum approaches such as QAOA.Source: §2.1 · p. 5

QUBO formulation

• QUBO problems use binary decision variables and a symmetric matrix, generalize MaxCut, and can represent all NP-complete problems through polynomial-time mappings.Applications include Graph Coloring, Number Partitioning, and Quadratic Knapsack.Source: §2.2 · pp. 5–6
• QUBO models are unconstrained, and minimization can be converted to maximization by flipping the cost-function coefficients’ signs.Source: §2.2 · p. 6

QUBO and Ising models

• QUBO instances correspond one-to-one with Ising models through z_i = 2x_i − 1, enabling annealing-based solution methods and quantum-annealing implementations.The resulting Ising Hamiltonian differs only by an optimization-irrelevant constant [46].Source: §2.2 · p. 6

Higher-order extensions

• Higher-order PUBO interactions can be quadratized with ancillary gadgets, although QAOA focuses on QUBO because current hardware primarily supports two-qubit interactions.With gates acting on more than two qubits, retaining higher-order interactions may reduce the number of interactions; arbitrary combinatorial problems can also map to PUBO.Source: §2.2 · p. 6

• MaxCut is NP-hard, so practical solvers use approximation algorithms and heuristics that trade optimality guarantees against computational efficiency.Source: §2.3 · p. 6
• Greedy, local search, simulated annealing, genetic, spectral, linear-programming, and semidefinite-programming methods offer practical or theoretical benefits but face suboptimality, sensitivity, or scaling limitations.Greedy methods can be myopic; local search may depend on initialization and neighborhoods; simulated annealing and genetic algorithms can be slow; spectral methods depend on eigenvectors and spectral gaps; mathematical programs may require substantial resources.Source: §2.3 · pp. 6–7
• The Goemans–Williamson algorithm guarantees an approximation ratio of at least 0.87856, producing cuts with weights at least 87.856% of optimal and achieving the best possible polynomial-time ratio under the Unique Games Conjecture [40, 53, 54].Source: §2.3 · p. 7
• Goemans–Williamson formulates MaxCut as a QUBO, relaxes binary variables into unit vectors for an SDP, solves the relaxation, and applies Gaussian hyperplane rounding to return a cut.The rounding assigns vertices according to the sign of each vector’s inner product with a random Gaussian vector.Source: §2.3 · p. 7

2.4 Variational Quantum Algorithms

• VQAs apply the variational principle by iteratively optimizing a parameterized ansatz to minimize a Hamiltonian’s expectation value, with ansatz design ranging from problem-inspired to hardware-efficient forms.Hardware-efficient ansätze use native single- and two-qubit gates to reduce circuit depth, whereas problem-inspired forms reflect the target Hamiltonian.Source: §2.4 · p. 8

2.4.1 Variational Quantum Eigensolver (VQE)

• VQE uses a hybrid quantum-classical loop in which quantum circuits estimate eigenvalues and classical optimization, often via gradient descent, updates ansatz parameters [1].The framework supports increasingly expressive ansätze and has been applied to molecular Hamiltonians and combinatorial optimization problems [65].Source: §2.4.1 · p. 9

2.4.2 Quantum Adiabatic Algorithm (QAA)

• QAA evolves from an easily prepared initial Hamiltonian ground state toward a problem Hamiltonian ground state, with gate-based implementations obtained by Trotterizing the evolution.For difficult MAX 2-SAT instances, faster evolution, excited-state initialization, and an intermediate random local Hamiltonian often increased success probability, unlike in Grover-search tests.Source: §2.4.2 · pp. 9–10

2.4.3 Barren plateaus

• Barren plateaus cause exponentially small cost-function gradients as qubit counts increase, potentially stalling training in parameterized circuits such as VQE and QAOA.Formally, the gradient variance vanishes as O(b^-n) for b > 1.Source: §2.4.3 · p. 10

Core formulation

• QAOA [12] encodes an optimization objective in a cost Hamiltonian and alternates it with a noncommuting mixer Hamiltonian to search for high-quality bitstrings.For MaxCut, binary variables map to Pauli-Z operators, while the mixer uses Pauli-X operators.Source: §2.5 · pp. 10–11

Circuit construction

• Mixer elements use single RX rotations, whereas two-qubit cost interactions use two CNOT gates sandwiching a local RZ rotation.Figure 2 depicts the corresponding mixer and cost-layer implementations.Source: Figure 2 · p. 11, §2.5 · p. 11
• The algorithm initializes a mixer-basis state, applies p repeated cost–mixer layers with 2p variational parameters, and produces the state |ψ_p(γ, β)⟩.The parameters satisfy γ_k ∈ [0, 2π) and β_k ∈ [0, π).Source: §2.5 · p. 11

Hybrid optimization

• Repeated computational-basis measurements estimate the cost Hamiltonian expectation, and a classical optimizer updates γ and β to maximize F_p(γ, β).The optimized parameters determine the approximation ratio α for the underlying optimization problem.Source: §2.5 · pp. 11–12

Variants and implementation context

• QAOA is typically initialized in the mixer Hamiltonian’s highest-energy eigenstate rather than its ground state, and an analog variant for quantum annealers was proposed by Barraza et al..The review notes that the adiabatic theorem still holds for this initialization choice.Source: §2.5 · p. 12

Scope

• The analysis covers ansatz variants, parameter optimization, computational resource efficiency, solution quality, noise and errors, and hardware-specific approaches.It evaluates QAOA’s strengths and limitations in light of recent literature, emphasizing challenges for realizing practical applications.Source: §3 · p. 13

3.1 Ansatz Variants

• Ansatz design balances problem and hardware specificity against generality, motivating variants that address limitations of the original layered QAOA circuit.The standard circuit applies cost and mixer operators in p layers, with ansatz choices influenced by graph structure and hardware design.Source: §3.1 · p. 13

3.1.1 Multi-Angle QAOA

• ma-QAOA assigns separate angles to each cost and mixer element, achieving approximation ratios at least as good as vanilla QAOA while sometimes using shallower circuits.The parameter count is (n+m)p; symmetry exploitation reduces parameters by approximately 33% with little to no objective-function impact.Source: §3.1.1 · p. 13

3.1.2 QAOA+

• QAOA+ augments p = 1 QAOA with multi-parameter problem-independent ZZ and mixer X layers, achieving higher MaxCut approximation ratios than p = 1 while remaining shallower than p = 2.On random regular graphs, QAOA+ showed similar performance to p = 2 QAOA; for N qubits, its added depth uses 2N − 1 parameters.Source: §3.1.2 · p. 15

3.1.3 Digitized counterdiabatic QAOA

• DC-QAOA adds variational counterdiabatic driving to accelerate optimization, and it outperformed standard QAOA on Ising, classical optimization, and k-spin problems.The method targets the computational cost and circuit depth associated with adiabatic evolution; related CD-QAOA also uses counterdiabaticity to improve convergence and solution quality.Source: §3.1.3 · p. 15

3.1.4 Adaptive bias QAOA

• Adaptive bias QAOA introduces n adaptive local-field parameters into the mixer and initial state, making convergence polynomially shorter than vanilla QAOA at fixed accuracy and gate count.The computation-time improvement increases with problem size.Source: §3.1.4 · p. 15

3.1.5 ADAPT-QAOA

• ADAPT-QAOA selects mixer operators from a predefined pool using commutator-gradient information, converging faster on MaxCut while reducing CNOT gates and optimization parameters by about 50% each.Its operator-selection step requires additional measurements whose number depends on the pool size.Source: §3.1.5 · p. 16

3.1.6 Recursive QAOA

• RQAOA repeatedly uses all-pair ZZ correlations to impose parity constraints, eliminate qubits, solve a cutoff-sized residual problem classically, and reconstruct the solution.For complete graphs with 2n vertices, level-1 RQAOA achieves approximation ratio 1, whereas p = 1 QAOA satisfies α ≤ 1 − 1/(8n^2).Source: §3.1.6 · p. 16

3.1.7 Quantum alternating operator ansatzes

• QAOAnsatz generalizes QAOA to parameterized phase-separation and mixing operators, enabling hard constraints through feasible subspaces and broader combinatorial optimization modeling.Constraint encoding can use XY, partial, and other mixers instead of cost penalties, with UQAOA proposed to unify the approaches.Source: §3.1.7 · pp. 16–17
• GM-QAOA exactly implements Grover-like mixers, avoids Trotterization and Hamiltonian-simulation errors, and outperformed other QAOA approaches for discrete portfolio rebalancing.It restricts mixing to feasible states while connecting all feasible states and supports efficient preparation of feasible-solution superpositions.Source: §3.1.7 · pp. 17–18

3.1.8 Warm-starting QAOA

• Warm-starting QAOA preserves the Goemans–Williamson bound, while WS-RQAOA produced the best reported MaxCut results for 20- and 30-node graphs.The approach offers an advantage over standard QAOA at low depth, especially for NISQ devices.Source: §3.1.8 · p. 19

3.1.9 FALQON

• FALQON assigns parameters from quantum measurements without classical optimization, and FALQON+ improves approximation ratio and success probability with minimal depth and noise costs.FALQON’s solution estimate improves monotonically with circuit depth, while FALQON+ provides smoother initialization for QAOA.Source: §3.1.9 · p. 19

3.1.10 Fermionic QAOA

• FQAOA intrinsically preserves fermion particle number to enforce constraints and demonstrated substantial advantages over existing methods for portfolio optimization.Its driver-Hamiltonian design guideline also applies to QAOA, Grover adaptive search, and quantum phase estimation.Source: §3.1.10 · p. 20

3.1.11 Other approaches

• Other approaches smooth rugged QAOA landscapes through quantum clause dropout, match classical performance at one ST-QAOA round, and improve approximation ratios through modified cost Hamiltonians.ST-QAOA approaches the exact MaxCut solution with more rounds, while quantum dropout preserves the solution and Modified QAOA improves approximation ratios at p = 1.Source: §3.1.11 · pp. 20–21

3.2 Parameter Optimization

• Random initialization can hinder QAOA in rugged landscapes, motivating efficient strategies for initial parameters, classical optimization, and barren-plateau mitigation.The challenge becomes more important as circuit depth and complexity increase.Source: §3.2 · p. 21

3.2.1 Finding good initial parameters

• Heuristics, layerwise fixing, GNNs, transferability, QAOAKit, and Trotterized annealing provide alternatives to random initialization for finding good QAOA parameters.Zhou et al. obtain quasi-optimal p-level parameters in O[poly(p)] time, compared with 2O(p) random-initialization runs for similar performance; transfer-based methods also improve solution quality and reduce evaluations.Source: §3.2.1 · pp. 21, 23

3.2.3 Overcoming barren plateaus

• Layerwise learning avoids initializing or drifting onto barren plateaus, while parameter concentration permits training on w < n qubits and transferring nearly optimal parameters to larger systems.Layerwise learning achieved an average generalization error 8% lower than standard schemes, and concentration occurs inverse-polynomially with problem size.Source: §3.2.3 · p. 26

3.2.4 Parameter transferability and reusability

• Optimal QAOA parameters converge around values predictable from local subgraph characteristics, enabling reuse across similar instances to avoid local optima and reduce evaluations.QAOAKit supplies pre-optimized parameters and circuit templates, retrieving angles by graph-isomorphism certificates or returning the closest fixed angles.Source: §3.2.4 · p. 27

3.2.5 Leveraging parameter symmetries

• Exploiting symmetry reduces redundant QAOA energy evaluations and predicts required depth, although automorphism analysis can outweigh savings on difficult graphs; parameter concentration also yields scalable near-optimal reuse.Symmetry exploitation achieved a median speedup of 4.06 for p = 1 on 71.7% of graphs, while optimal parameters formed two symmetric branches and remained polynomially close across system sizes.Source: §3.2.5 · p. 27
• A 28.1% parameter reduction preserved MaxCut accuracy on over two-thirds of eight-node connected non-isomorphic graphs, while largest-symmetry reductions cut parameters 37.1% with only a 6.1% cost decrease when performance declined.In 35.9% of graphs, the 28.1% reduction was achieved using the largest symmetry.Source: §3.2.5 · p. 28
• Removing time-reversal, Z2, and graph-structure degeneracies creates a lower-dimensional, smoother, and more navigable QAOA parameter space for optimization.For MaxCut on regular undirected graphs, additional structural symmetry introduces parameter redundancy.Source: §3.2.5 · p. 28
• Analytical level-1 solutions exist for MaxCut on general graphs, while a fermionic representation solves arbitrary p for the one-dimensional antiferromagnetic ring by reducing QAOA evolution to independent-spin control.Symmetry reduction identifies a lower-dimensional sub-manifold, and numerical analysis found that all minima are global minima.Source: §3.2.5 · p. 28

3.3 Computational Resource Efficiency

• QAOA’s computational efficiency depends on runtime, with speedup potential balanced against parameter-optimization and error-correction overheads.The section examines speedup evidence, obstacles to general advantage, and strategies for improving runtime performance.Source: §3.3 · p. 28

3.3.1 Speedup potential

• O(n^2p) gates and O(np) runtime for n-node MaxCut instances contrast with classical Goemans-Williamson runtime O(nm), suggesting speedup for dense graphs.Here p is the number of QAOA layers, m the number of graph edges, and O(n) gates are assumed parallelizable.Source: §3.3.1 · pp. 28–29
• QAOA achieved exponential acceleration for large Minimum Vertex Cover problems, with complexity O[poly(k) + poly(p)] versus O(2n2 + n4).The comparison used graphs with 10 vertices and 16 edges and QAOA depths 2 ≤p ≤10.Source: §3.3.1 · p. 29
• QAOA’s smaller success-probability exponent than simulated annealing yields superlinear speedup for Maximum Independent Set only in the deep-circuit regime δmin > 1/T.The evidence concerns 115 randomly generated graphs with 80–289 vertices on 2D Rydberg atom arrays.Source: §3.3.1 · p. 29
• QAOA also provides quadratic Grover-like speedup for unstructured search and exponential advantage in system size N for quantum linear systems.The reported QLSP runtime is O(κ poly(log(κ/ϵ))) versus classical conjugate-gradient complexity O(N√κ log(1/ϵ)).Source: §3.3.1 · p. 29

3.3.2 Obstacles to quantum speedup

• General advantage is constrained by parameter optimization: QAOA must run within a minute for problems with fewer than 400 variables, while several hundreds of qubits are needed for speedup.Increasing depth p adds variational parameters; one benchmark estimated complete optimization at about 16 minutes, orders of magnitude slower than classical AKMAXSAT solvers.Source: §3.3.2 · pp. 29–30
• Error-correction overhead makes quadratic speedups unlikely to yield advantage on early fault-tolerant processors, whereas quartic speedups are more promising.State distillation was identified as a major source of slowness and inefficiency for processors with around a million physical qubits or less.Source: §3.3.2 · p. 30

3.3.3 Runtime performance improvements

• ADAPT-QAOA reduces variational parameters and CNOT gates by approximately 50%, while ab-QAOA achieves polynomially shorter MaxCut runtimes than vanilla QAOA as graph size grows.ADAPT-QAOA also converges faster and produces better results at increasing layer counts; ab-QAOA uses the same number of gates and measurements.Source: §3.3.3 · pp. 30–31

3.4.1 Solution guarantees

• QAOA’s approximation guarantees improve with depth, reaching α ≥0.7559 at p = 2 and α ≥0.7924 at p = 3 on specified 3-regular graphs, but remain below leading classical bounds.The cited classical guarantees are 0.8786 for GW and 0.9326 for an SDP algorithm on maximum-degree-3 graphs.Source: §3.4.1 · p. 33
• At p = 11, QAOA exceeds the classical SK-model SDP benchmark with V̄11 ≥0.6393 > 2/π, while V̄12 ≥0.6466; whether it beats every classical MaxCut algorithm remains unclear.The comparison concerns infinite-size SK-model performance and its connection to large-degree random regular graphs.Source: §3.4.1 · p. 34
• QAOA1 can outperform threshold algorithms for Max-kXOR when k > 4 in the large-degree limit, although alternative local tensor algorithms may still match or exceed it.For Max-3XOR, the threshold algorithm performs better as degree increases, whereas QAOA1 wins for some degrees D ≤27.Source: §3.4.1 · p. 35

3.4.2 Performance limitations

• Fixed-depth QAOA is obstructed by locality and overlap-gap structure: on sparse MIS instances it reaches at most 0.854 of optimum, while on worst-case bipartite random regular graphs its ratio approaches 0.Related obstructions extend to bounded-depth Max-kXOR and dense even-k spin models, including regimes where QAOA sees the whole graph.Source: §3.4.2 · p. 37

3.4.3 Empirical evidence

• Simulator studies report approximation ratios exceeding GW: QAOA first surpasses GW at p = 6 on 10-node random graphs and consistently does so across tested sizes for p ≥8.An exhaustive study of connected non-isomorphic graphs with n ≤9 found QAOA exceeded the worst-case GW bound on most graphs by p = 3.Source: §3.4.3 · p. 37
• Increasing depth raises average optimal-solution probability but widens its distribution, showing that success probability is more sensitive to graph structure than approximation ratio.This contrasts with the narrower, converging approximation-ratio distributions observed across graph structures.Source: §3.4.3 · pp. 37–38
• Restricted-entanglement simulations solved MaxCut and Exact Cover 3 exactly or approximately at p ≈30 with up to 60 qubits, suggesting entanglement may matter less than sufficient depth.The relationship between entanglement, depth, and performance across other problem instances remains open.Source: §3.4.3 · p. 38
• Heuristic initialization finds depth-p quasi-optimal parameters in O[poly(p)] time instead of 2O(p) random-start optimization runs, improving approximation ratios through p = 50.QAOA3 with INTERP surpassed quantum annealing on difficult small-gap instances, attributed to non-adiabatic mechanisms.Source: §3.4.3 · p. 38
• QAOA’s advantage is highly instance-dependent: graphs without odd cycles had a 12% higher mean optimal-solution probability, while density, symmetries, cycles, and diameter predicted performance.For constraint problems with αd > 1, higher depth was necessary for satisfactory results.Source: §3.4.3 · p. 38
• QAOA generally struggled to beat classical heuristics at scale because exponential sampling time dominates, although it outperformed GW on most 4-regular graphs up to 24 nodes at p = 10.Machine-learning predictors reached 96% cross-validated accuracy and under 19.7% relative error for identifying favorable instances and solver choices.Source: §3.4.3 · pp. 38–39
• On IBM Q 16 Melbourne, p = 1, . . . , 5 QAOA could not match D-Wave quantum annealing, and hardware noise caused poor performance on an eight-variable 2-SAT instance.The simulator performed well on the same instance, indicating substantial QPU limitations.Source: §3.4.3 · p. 39
• Hardware studies found 96.6% success on small Exact-Cover instances at p = 2, robust 23-qubit grid performance through p = 3 before noise degraded deeper circuits, and limited scaling after compilation.Trapped-ion results remained stable from 20 to 40 qubits, while application-specific QPU quality varied independently of quantum volume. Photonic two-qubit CSP experiments reached classical fidelities of 99.88 ± 0.10%, 96.98 ± 0.56%, and 99.48 ± 0.27%.Source: §3.4.3 · pp. 39–40

3.5 Noise and Errors Considerations

• QAOA’s ideal approximation ratio improves with layer count, but deeper circuits accumulate noise; larger systems and higher hardware noise further hinder practical effectiveness.The noise–depth trade-off implies an instance- and noise-dependent optimal number of layers rather than unlimited layering.Source: §3.5 · p. 41

3.5.1 Characterizing the sources of noise

• For local noise, fidelity and approximation ratio degrade as a power law whose exponent scales with system size, while required measurements can grow exponentially with gate error rates.Noise-induced barren plateaus can make gradients vanish exponentially with circuit depth and cannot be addressed by methods designed for noise-free barren plateaus.Source: §3.5.1 · p. 41
• Correlated errors can distort QAOA landscapes and success probabilities, although simulations found performance sometimes improved with stronger noise correlations at fixed local error rates [221–223].Crosstalk, precision errors, residual ZZ coupling, and temporally or spatially correlated noise are relevant error sources in NISQ devices.Source: §3.5.1 · pp. 41–42

3.5.2 Quantum advantage in the presence of noise

• Current-device error rates make substantial QAOA quantum advantages unlikely for large, dense problems, with required rates sometimes below 10^-6 or near fault-tolerance thresholds.Empirical studies likewise find noise-sensitive performance, especially at high depth, while hardware-native instances can remain more robust than compiled, non-native problems.Source: §3.5.2 · pp. 42–43

3.5.3 Noise mitigation techniques

• Optimizing compilation and connectivity can reduce QAOA errors: a greedy spanning-tree method achieved nearly a factor of 10 higher MaxCut success probability per iteration.Related approaches reduce CNOT counts or compiled depth, and equivalent circuit averaging produced around 60% average error reduction for depth-1 QAOA.Source: §3.5.3 · pp. 43–44
• Correlated-measurement mitigation reduced average errors by factors >22 on IBM devices and >5.5 on Rigetti devices, while improving QAOA across multiple graph instances.Digitizing variational parameters can mitigate precision errors, at the cost of increased circuit depth.Source: §3.5.3 · p. 44
• Symmetry verification, redundant parity encoding, and related conservation-based methods improve QAOA robustness by projecting states, correcting symmetry-breaking errors, or decoding redundant information.These techniques improved fidelity, objective values, or optimal-solution sampling in small MaxCut, TSP, and parity-QAOA demonstrations.Source: §3.5.3 · p. 44
• Exponential error-suppression schemes offer future promise, but resolving noise-induced barren plateaus ultimately requires more accurate gates and fault-tolerant quantum computing.Noise mitigation therefore improves practicality without removing the fundamental hardware limitations affecting QAOA scalability.Source: §3.5.3 · p. 44

Platform-specific hardware approaches

• Hardware implementations across superconducting, trapped-ion, neutral-atom, and photonic platforms aim to overcome connectivity limits, mitigate noise, and validate error-mitigation techniques.Selected state-of-the-art experiments are summarized in Table 4, which reports qubit counts, QAOA layers, and approximation ratios where investigated.Source: §3.6 · p. 44, Table 4 · p. 45

Neutral atoms

• A programmable four-qubit Rydberg parity gate enables scalable qubit remapping for complex interaction graphs and supports small-scale QAOA implementations beyond numerical simulations.The gate uses laser-coupled Rydberg states and adiabatic pulses to imprint dynamical phases on computational basis states.Source: §3.6 · p. 46

Trapped ions

• Native trapped-ion Hamiltonians enabled ansatz families that prepared ground states of arbitrary 6-qubit Sherrington–Kirkpatrick instances by overcoming symmetry protection.The approach addresses the all-to-all connectivity of the SK Hamiltonian, which cannot be directly implemented on planar processors.Source: §3.6 · p. 46

Quantum spin systems

• Global entangling operations can construct arbitrary weighted and unweighted coupling graphs with lower noise susceptibility than standard gate-based compilation.The method provides operation-count upper bounds and a mixed-integer program for optimizing operation sequences, while tighter bounds remain necessary.Source: §3.6 · p. 46

Qudits

• Qudit-based QAOA maps k-coloring efficiently when the hardware dimension satisfies k = d, while numerical tests found global evolutionary optimizers outperforming gradient-based methods.Deller et al. applied a momentum-operator Lx mixer to k-graph coloring and electric-vehicle charging with global power constraints.Source: §3.6 · p. 46

Photonic quantum computers

• Photonic-specific QAOA achieved up-to 30-fold lower cluster-state dimension for Max-k-Cut, while cat qubits improved fixed-resource fidelity for Exact Cover.These approaches tailor QAOA to measurement-based photonic computation and address single-photon losses, respectively.Source: §3.6 · p. 46

4.1 Related Tools

• QPack benchmarks runtime, accuracy, scalability, and capacity, while QAOAKit provides reproducible QAOA parameters and circuit generators for exploratory comparisons.Table 4 surveys experiments spanning multiple hardware technologies, problem types, qubit counts, and QAOA layer depths.Source: §4.1 · p. 47

4.2 Implementation and Systematic Evaluation of QAOA Variants

• The study evaluated QAOA [12], QAOA+ [78], FALQON, ModifiedQAOA, WSQAOA, and ma-QAOA across 78 MaxCut graphs.The graphs were complete, 3-regular, or random and ranged from 4 to 18 nodes; optimization used scipy’s COBYLA until tolerance 0.0002 or 500 iterations, whichever came first. Implementations ran on Qiskit simulators and IBM Quantum Falcon r5.11H processors.Source: §4.2 · pp. 47–48, Table 5 · p. 48

4.3 Experimental Results and Discussion

• Mean approximation ratios reach 0.98 on complete graphs and 0.94 on regular graphs in simulations, but random graphs reach at most 0.92 and decline further with size.Complete graphs retain ratios over 0.9 up to 18 nodes, whereas 18-node random graphs typically reach 0.6–0.8; QAOA and FALQON show relative robustness to scaling.Source: §4.3 · pp. 48, 50
• QAOA and FALQON generally improve with layer depth through p = 8, while ma-QAOA gains most and QAOA+ and ModifiedQAOA respond more modestly.Real hardware significantly reduces mean approximation ratios across variants, although graph-type trends generally persist; ma-QAOA can achieve higher ratios at substantially greater resource cost than WS-QAOA.Source: §4.3 · pp. 50–51
• Cosine similarity exceeds 0.96 for most variants but is approximately 0.51 for FALQON, indicating limited versus more extensive exploration of the parameter space.WS-QAOA’s high similarity is expected because its warm-start design begins near optimal parameters.Source: §4.3 · pp. 51–52, Table 9 · p. 52

4.4 Limitations and Future Work

• Future work expands the study to newer variants, larger and more diverse graph and problem types, additional optimizers, and interactive released code.The authors note that the current review omits many findings and that broader comparisons are planned for weighted-MaxCut and other problems.Source: §4.4 · p. 52

5.1 Summary of Analysis

• QAOA performance depends strongly on ansatz design, circuit depth, parameter optimization, graph structure, entanglement, and noise, motivating variants, symmetry methods, parameter transfer, and error mitigation.Local and correlated errors can cause exponential degradation and noise-induced barren plateaus, although trapped-ion devices have shown monotonic improvement up to 10 layers on 20-qubit graphs.Source: Parameter optimization · pp. 53–54

5.2 Potential Applications and Use Cases

• QAOA and its variants have been applied to constrained optimization, graph coloring, vehicle routing, portfolio optimization, Hamiltonian simulation, communication, protein folding, and computer vision.Examples include level-1 RQAOA exceeding a generic classical SDP-rounding algorithm on some 3-colorable graphs, noisy VQAs matching classical solvers for vehicle routing, and a 13-fold speedup for object detection using L-BFGS-B.Source: §5.2 · pp. 55–56

5.3 The Quantum Advantage of QAOA

• QAOA can outperform classical algorithms on selected problems, including Max-kXOR for k > 4 and large-girth MaxCut at depth p = 11, but classical methods remain superior in many settings.Locality, symmetry, Overlap Gap Property obstructions, and graph structure can limit QAOA, while noise and near-term hardware continue to hinder consistent advantage.Source: §5.3 · pp. 57–58
• Ansatz variants such as ab-QAOA, ADAPT-QAOA, QAOAnsatz, WS-QAOA, FALQON+, and FQAOA improve convergence, resource use, low-depth performance, noise resilience, or constraint handling in specific settings.ADAPT-QAOA reduces CNOT gates and optimization parameters by about half, while ab-QAOA reduces computation time and accelerates convergence as problem size grows.Source: §5.1 · pp. 52–53, §5.3 · p. 57

5.4 Open Questions and Future Directions

• Achieving quantum advantage requires stronger theory, empirical standardization, problem-specific ansatzes, improved parameter optimization, and deeper understanding of entanglement, depth, and problem structure.A specific open question is whether QAOA approaches the Parisi value as p →∞ on random D-regular graphs, which would imply optimal solutions for the SK model and MaxCut.Source: Parameter optimization · p. 54, §5.4 · p. 58
• QAOA’s ability to achieve quantum advantage remains unresolved for OGP instances, extremely small spectral gaps, larger-k local tensor comparisons, and generalizations beyond specific speedup domains.These questions include scaling beyond small problem sizes and extending observed speedups from MIS on 2D Rydberg arrays to general cases.Source: §5.4 · pp. 58, 60
• Constructing arbitrary coupling operations may scale promisingly for dense unweighted QAOA interactions, but optimal sequences and compilation complexity for arbitrary graphs remain unresolved.Future work should seek graph-specific constructions, tighter upper bounds, and a formal complexity characterization.Source: §5.4 · pp. 58–59
• Application-specific benchmarking should compare QAOA with classical and local tensor algorithms, relate success probability to runtime, and test machine-learning predictions across problems, instances, and hardware.Graph sparsification and new runtime metrics are proposed as possible ways to identify or enhance QAOA’s advantages.Source: §5.4 · pp. 59–61
• Parameter optimization research should address barren plateaus, initialization, transferability, symmetries, analytical solutions, and the generalization of unsupervised learning and reinforcement learning to larger instances.Open issues include whether BFGS remains effective for p ≥3 and whether similarities between parameters on related graphs are universal.Source: §5.4 · p. 59
• Noise research should determine whether correlated noise improves resilience, whether coherent dephasing removes training saturation beyond simple models, and whether mitigation can suppress noise-induced barren plateaus.Promising techniques include symmetry verification, SWAP-network optimization, reduced CNOT counts, equivalent-circuit averaging, and fault-tolerant methods.Source: §5.4 · pp. 60–61
• Hardware scaling requires systematic study of connectivity, decoherence, gate errors, routing, compilation overhead, direct gate implementations, and experimental performance across ion, atom, superconducting, photonic, and qudit platforms.The four-qubit Rydberg parity architecture remains experimentally uncertain beyond numerical simulation, while routing overhead can significantly reduce performance on mismatched graphs.Source: §5.4 · p. 61
• Up to 30-fold improvement in cluster-state dimension was reported for photonic MBQC QAOA versus gate-based QAOA, motivating further photonic algorithm development.The discussion also calls for improved surface-code implementations to enable advantages on early fault-tolerant processors.Source: §5.4 · p. 61
• Future algorithm design should explore FALQON, FQAOA, warm-starting, shortcuts to adiabaticity, ma-QAOA, ab-QAOA, QAOAnsatz, WS-QAOA, selective clause dropout, and broader CSP applications.These directions target simpler parameter optimization, improved low-depth initialization, scalability, rugged energy landscapes, and wider applicability.Source: §5.4 · pp. 61–62

6.1 Which QAOA Ansatz Variant Should I Use for My Problem?

• QAOA variant selection should account for problem structure, hardware constraints, and the trade-off between specificity and generality.Variants can exploit constraints, graph symmetries, density, odd cycles, hardware grids, and higher-depth requirements, but QAOA may be unsuitable for non-combinatorial problems, large-depth or high-entanglement requirements, noise-sensitive settings, or mismatched hardware connectivity.Source: §6.1 · pp. 62, 64
• Different ansatzes target different settings: standard QAOA suits simple or unknown structures, QAOAnsatz handles hard and soft constraints, and specialized variants address graph, Ising, MaxCut, and constrained problems.DC-QAOA outperforms standard QAOA on the cited Ising, classical optimization, and k-spin problems; ST-QAOA matches the classical solver at r = 1, approaches exact MaxCut as rounds increase, and can outperform vanilla QAOA at low depths.Source: §6.1 · pp. 62–64
• Other variants trade circuit resources, convergence, constraints, or initialization: ma-QAOA reduces parameters by approximately 33% with little to no objective impact, while ADAPT-QAOA reduces CNOT gates and parameters by about 50% each.QAOA+ keeps depth low while improving over p = 1 QAOA, ab-QAOA has polynomially shorter computation time than vanilla QAOA, and FALQON assigns parameters through measurements without classical optimization.Source: §6.1 · p. 63

6.2 How to Optimize the QAOA Parameters?

• Parameter optimization has no universal method because suitable choices depend on the ansatz design, hardware platform, circuit depth, objective landscape, and noise.The guide distinguishes gradient-free, gradient-based, and machine-learning approaches by computational cost, robustness, generalization, convergence, and data requirements.Source: §6.2 · p. 65

Gradient-free methods

• Gradient-free methods fit moderate-depth circuits and limited resources, whereas gradient-based methods suit smooth objectives and broad problem variation but require more computation and measurements.BOBYQA within APOSSM performs best for a fixed number of functional evaluations; AMSGrad and BFGS outperform gradient-free methods under shot-noise, while gradient-based methods can be vulnerable to NISQ noise.Source: Gradient-free methods · p. 65, Gradient-based approaches · p. 65

Machine Learning Approaches

• Machine-learning optimizers can accelerate QAOA and generalize across problem instances and graph sizes, but they may require many training instances and face scalability challenges.The guide lists GPR, linear and tree regression, RSVM, LSTM, GNN, and reinforcement learning as example approaches.Source: Machine Learning Approaches · p. 66

Other considerations

• Additional strategies exploit parameter symmetries, transferability, and layerwise learning, while warm-starting improves low-depth initialization and FALQON remains primarily limited to future fault-tolerant devices.Layerwise learning grows circuits incrementally and updates parameter subsets to avoid plateaus and improve convergence; warm-starting provides an advantage over standard QAOA at low depth.Source: Other considerations · p. 66
• Transferring parameters across locally similar instances improves solution quality and reduces evaluations, while exploiting natural graph symmetries improves performance by approximately 33%.Parameter symmetries also simplify optimization and eliminate parameter-space degeneracies.Source: Other considerations · pp. 66–67
• Parameter symmetry can result in runtime acceleration of up to 5.5 times, and the cited material also reports acceleration of more than 1.23 times.Source: Other considerations · p. 66
• Optimal parameter initialization can be found in O(poly(p)) time, whereas random initialization requires 2O(p) optimization runs for comparable performance.Heuristic initialization can therefore substantially reduce optimization effort.Source: Other considerations · p. 67

6.3 Practical Considerations for Implementing QAOA

• Implementation should match the ansatz, mixer, initialization, and optimizer to the problem and hardware, using Ansatz Architecture Search when jointly optimizing architecture and variational parameters.Mixer designs require balancing performance gains against longer circuit depth, while optimizer choice spans gradient-free, gradient-based, and machine-learning methods.Source: §6.3 · p. 67
• Barren plateaus and difficult large-scale landscapes may require layerwise learning, incremental depth growth, target-parameter initialization, hybrid quantum-classical methods, or specialized ansätze.These strategies address optimization difficulty as problem size and landscape complexity increase.Source: §6.3 · p. 67
• Noise mitigation should combine gate-count reduction, SWAP-network optimization, symmetry verification, and hardware-specific features, whose choice depends on platform capabilities such as connectivity or qudits.Continuous-time quantum-walk perspectives can also help identify optimal parameters in ma-QAOA on dynamic graphs.Source: §6.3 · p. 67, Other considerations · p. 67