Optimization Geometry of QAOA and Variational Quantum Algorithms
Authors: Vojtěch Novák, Ivan Zelinka, Silvie Illésová, Swagatam Das, Martin Beseda
Organizations: Department of Computer Science, Faculty of Electrical Engineering and Computer Science, VSB – Technical University of Ostrava, Ostrava, Czech Republic · IT4Innovations National Supercomputing Center, VSB – Technical University of Ostrava, 708 00 Ostrava, Czech Republic · Department of Informatics and Statistics, Marine Research Institute, Klaipeda University, Klaipeda, Lithuania · Gran Sasso Science Institute, L’Aquila, Italy · Electronics and Communication Sciences Unit, Indian Statistical Institute, 700108 Kolkata, India · Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica, Università dell’Aquila, Via Vetoio, I-67010 Coppito, L’Aquila, Italy
Variational quantum algorithms turn choices of Hamiltonian, ansatz, and parameterization into a classical nonconvex optimization problem. We study how this objective function can be visualized and characterized in ways that help explain optimizer behavior. We distinguish two properties of the objective: the number of local minima encountered along sampled directions and the differences in quality among local-search endpoints. We then ask how a local optimizer, represented by BFGS, compares with adaptive differential evolution, represented by jSO. Rather than comparing jSO with a single local run, we allow BFGS multiple starts within the same function-evaluation budget. This gives local search repeated opportunities to explore different basins and provides a stronger baseline for asking when a global evolutionary solver is useful. We study these questions using VQE and QAOA, focusing on how frustra- tion, circuit depth, parameter tying, mixed locality, and nonlinear repa- rameterization change the Hamiltonian expectation-value objective seen by the classical optimizer. Increasing independent circuit depth raises the sampled local-minimum count without making global search more effective. Parameter tying, by contrast, produces both more repeated local structure and much larger differences in quality among local-search endpoints, and in this regime adaptive differential evolution outperforms function-evaluation-matched multistart BFGS. The comparison shows that the number of local minima alone does not determine whether global search is advantageous: the important distinction is whether different basins lead to similarly good solutions or to substantially different objective values. These results provide a practical workflow for connecting model construction, objective- function geometry, empirical diagnostics, and optimizer choice.
Figures & tables
Figure 1: Conceptual overview of a variational quantum algorithm. Parameters define a circuit that prepares a restricted set of reachable quantum states, and the Hamiltonian assigns an energy to each state. The optimizer navigates the resulting classical energy landscape over the parameters.
Figure 2: Compact construction overview. (a) Frustration on a triangle: not all antiferromagnetic preferences can be satisfied simultaneously. (b) A small frustrated spin-glass model used as a readable QAOA physical example. (c) The same physical model can be exposed through a standard parameterization with more independent controls or through parameter tying with fewer controls. (d) A nonlinear coordinate map can fold the variable seen by the optimizer.
Figure 3: A concrete reparameterization example. (a) A repeated-angle circuit block uses the same physical angle α several times. (b) The nonlinear map α(θ)=θ+asin(mθ) can stay visually close to the identity while introducing a high-frequency deviation. (c) After pullback through this map, the same one-dimensional objective can develop additional sampled minima.
Figure 4: Two exact two-dimensional restrictions of the same N=14 frustrated-Ising VQE objective. The coordinate slice is easy to compute, while the optimizer-informed plane exposes a more decision-relevant direction.
Figure 5: Three basin-focused views of the same 14-spin frustrated-Ising example. Energies and sampled minima are tied to the underlying objective, while panels (b)–(c) use display coordinates constructed from basin organization. These views emphasize global organization that a literal coordinate slice may hide.
Figure 6: Simple classical analogies. A Rastrigin-like contour shows many repeated local minima. A Schwefel-like contour shows minima with substantially different objective values. These contours provide a familiar visual reference for the quantum examples.
Diagnostic
Operational definition
What it tells the optimizer
Minima per line
Mean number of sampled local minima along random wrapped 1D lines
Directional multimodality; many local minima motivate restarts or broader exploration
Near-best rate pnear
Fraction of local starts ending within 0.01 of the best sampled endpoint
Empirical accessibility of a good basin; high values favor local search
Median endpoint gap gmed
Median loss of a local endpoint relative to the best sampled endpoint
Variation in local-minimum quality; large gaps make a poor local endpoint costly
Poor-endpoint fraction ppoor
Fraction of local starts ending more than 0.05 above the best sampled endpoint
How often local search is materially misdirected
Fourier entropy
Spectral entropy of sampled 1D objective profiles
Whether roughness is dominated by a few wavelengths or distributed across scales
Positive-curvature ratio
Ratio of retained positive Hessian eigenvalues near a selected minimum
Local anisotropy/conditioning near the selected minimum; complements basin-accessibility metrics
Table 1: Optimization diagnostics and their operational interpretation. Thresholds are expressed in normalized physical-error units from Eq. ( 3 ).
Figure 7: Matched QAOA examples. Independent depth primarily increases repeated local structure, while parameter tying and mixed-locality constructions can produce stronger local trapping or stronger competition between low-energy regions. The displayed restrictions are informative slices, not complete representations of the full objective.
Figure 8: VQE examples on transverse-field Ising model and Heisenberg model. Changes in parameter tying and ansatz structure reshape both the number of visible local minima and the spread of low-energy basin quality. Standard physical VQE controls can remain comparatively smooth even when related constructed examples are strongly multimodal along the sampled directions.
Construction
D
gmed [pp]
ppoor [%]
Min./line
jSO adv. [pp]
Standard p=3
6
2.01
4.69
12.00
−0.03
Independent p=6
12
1.79
5.47
14.75
−4.63
Parameter tying r=6
6
16.74
82.81
21.75
+1.88
Table 2: Compact MaxCut showcase. Endpoint gaps and poor-endpoint rates use the definitions in Eq. ( 6 ); “min./line” is the median sampled line-minimum count. The last column is the median per-instance advantage of jSO over MS-BFGS, so positive values favor jSO.
Figure 9: Best-so-far convergence for the two D=6 constructions. Curves show the median and interquartile range over 32 trajectories per method (four graphs × eight matched seeds). The gap is measured against the best value observed for each graph and construction across the local quenches and benchmark runs; it is not a certified global optimum. MS-BFGS rapidly reaches the best-observed level for standard p=3 . With parameter tying, jSO continues to improve late in the budget and finishes at lower error.
Figure 10: Optimizer-informed two-dimensional restrictions through distinct BFGS endpoints on one of the four MaxCut graphs. For standard p=3 , geometrically distinct endpoints can have essentially equivalent quality, and the selected contrast basin is only 3.5 pp higher. With parameter tying, the same construction exposes substantially unequal basins: the selected third basin is 6.7 pp above the reference and the contrast basin is 26.9 pp higher. The coordinates are built from endpoint-difference directions and are intended to expose basin competition within this plane. They do not summarize the full six-dimensional objective function.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 11: Analytically constructed two-parameter Fourier objectives and classical reference contours. Panels (a)–(b) provide controlled multimodal examples; panels (c)–(d) show Rastrigin- and Schwefel-like geometries for visual comparison.
Figure 12: One-dimensional scans through spin-glass-inspired constructions. Spatially weighted and parameter-tied variants can have very different sampled minima counts even when built from related ingredients.
Figure 13: One-dimensional scans through compact molecular VHA constructions.
The dynamical Lie algebraic (DLA) theory of variational quantum algorithms (VQAs) predicts commonplace exponentially vanishing loss and gradient variances for sufficiently deep parametrized circuits. In this work, we show that these predictions fail dramatically in the shallow-circuit (and particularly constant-depth) regime for the Quantum Approximate Optimization Algorithm (QAOA) applied to the maximum independent set (MIS) problem. In a large-scale numerical study across ∼23,000 problem instances, we find that barren plateaus are rare, while landscapes whose variances polynomially increase with system size---which we term "cragged terrains"---are common across graph families. This aggregate polynomial growth persists both for generic, low-symmetry random graphs and for highly symmetric vertex-transitive graphs, indicating that DLA-based variance predictions do not describe landscape scaling in this regime. As a stopgap alternative to the theory, we train empirical hardness models to predict instance-wise hardness metrics for QAOA-MIS. While these models generalize poorly, they nonetheless recover the correct landscape scaling class (barren plateau vs. cragged terrain) with high fidelity. Taken together, our results identify shallow QAOA for MIS as a prototypical setting in which asymptotic, unitary-design-centric predictions may be fundamentally insufficient to describe shallow variational quantum algorithms more broadly, emphasizing the need for more empirically-informed models of VQA loss landscapes.
Harrison Copp, Charlton Li, Anžej Margeta-Cacace +1
In low-depth implementations of the Quantum Approximate Optimization Algorithm (QAOA), the dominant cost is often the number of objective evaluations rather than circuit depth. We introduce a graph-conditioned trust-region method for reducing this query cost. A graph neural network predicts a Gaussian distribution N(mu, Sigma) over QAOA angles. The mean initializes a local optimizer, the covariance defines an ellipsoidal trust region that constrains the search, and the predicted uncertainty determines an instance-dependent evaluation budget. Thus the learned distribution defines a search policy rather than only an initial parameter estimate. Under explicit assumptions on local smoothness, curvature, calibration, and noise, we derive bounds on objective degradation within the trust region, lower bounds on gradient variance, preservation of expected objective ordering under depolarizing noise, and finite-sample coverage guarantees. We evaluate the method for MaxCut at depth p = 2 on Erdos-Renyi, 3-regular, Barabasi-Albert, and Watts-Strogatz graphs with n = 8-16 vertices. Relative to random restarts and the strongest learned point-prediction baseline, the method reduces the mean number of circuit evaluations from 343 and 85 to 45 +/- 7, while maintaining sampled approximation ratios within 3 percentage points of concentration-based heuristics. The method does not improve absolute approximation ratios; its advantage is reduced query cost at comparable solution quality. The predictive uncertainty is calibrated in the experiments, with ECE = 0.052 and Spearman correlation rho = 0.770, and the learned trust regions transfer to graph sizes not used during training. The results identify a low-depth, query-dominated regime in which graph-conditioned trust regions reduce the query cost of QAOA without modifying the ansatz.
Variational Quantum Algorithms (VQAs) potentially offer a pathway to practical quantum advantage, but their optimization is heavily hindered by barren plateaus and numerous local minima. While classically simulable Clifford circuits can warm-start VQAs to accelerate convergence, existing heuristic-based initialization methods struggle to scale within vast combinatorial search spaces. To overcome this bottleneck, we propose CRiSP (a Clifford Reinforcement Learning agent for State Preparation), a framework that formulates discrete prefix selection as a sequential decision-making problem. CRiSP utilizes Neural-Guided Monte Carlo Tree Search, driven by a Transformer-based policy trained via self-play, to insert learned Clifford gates before fixed parameterized rotations. This enables the construction of high-quality initial states entirely through polynomial-time classical stabilizer simulation without altering the underlying circuit architecture. By integrating a curriculum learning strategy that progressively expands the search horizon, the agent efficiently scales to deep circuits. Evaluated on QAOA benchmarks of up to 22 qubits and 1,370 parameters, CRiSP outperforms state-of-the-art Clifford initialization methods by a mean of 3.17× (max 45.02×) in average energy accuracy and 2.44× (max 16.01×) in best-achieved energy accuracy. Assessments on VQE tasks further demonstrate the framework's robustness and generalizability.
Gino Kwun, Dhanvi Bharadwaj, Gokul Subramanian Ravi
Computer Science and Engineering University of Michigan Ann Arbor, MI 48109, USA