Optimization Geometry of QAOA and Variational Quantum Algorithms

Vojtěch Novák; Ivan Zelinka; Silvie Illésová; Swagatam Das; Martin Beseda

quant-phOct 4, 2026

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

Abstract

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

\alpha

several times. (b) The nonlinear map

\alpha(\theta)=\theta+a\sin(m\theta)

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.

Panel of Figure 4 — 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.

Panel of Figure 5 — 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 $p_{\mathrm{near}}$	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 $g_{\mathrm{med}}$	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 $p_{\mathrm{poor}}$	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$	$g_{\mathrm{med}}$ [pp]	$p_{\mathrm{poor}}$ [%]	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

\times

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.

Explore similar work

Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models
Aug 4, 2026Harrison Copp, Charlton Li, Anžej Margeta-Cacace +1Quantum Approximate Optimization Algorithm Variational Quantum Circuits
Yale University
Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions
Apr 27, 2026Molena HuynhQuantum Approximate Optimization Algorithm Trust Region
North Carolina State University
Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
May 22, 2026Gino Kwun, Dhanvi Bharadwaj, Gokul Subramanian RaviVariational Quantum Algorithms Qubit
Computer Science and Engineering University of Michigan Ann Arbor, MI 48109, USA

Aug 4, 2026, quant-phJ/K move · Enter open · S save

Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models

Harrison Copp, Charlton Li, Anžej Margeta-Cacace, Amy Qiao

Yale University

Quantum Approximate Optimization Algorithm Variational Quantum Circuits Variational Inhomogeneous Random Graphs Empirical Study Lie Group+1

Open paper AskPDF arXiv

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

\sim

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.

Abstract

Explore similar work

Dynamical Lie Algebras Cannot Describe Shallow QAOA: Cragged Terrains, Barren Plateaus, and Empirical Hardness Models

Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions

Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning