When is global evolutionary search useful for variational quantum algorithms? A landscape-first study

Vojtěch Novák; Ivan Zelinka

quant-phSep 13, 2026

When is global evolutionary search useful for variational quantum algorithms? A landscape-first study

Authors: Vojtěch Novák, Ivan Zelinka

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

Abstract

Variational quantum algorithms recast state preparation as classical nonconvex optimization, but it is often unclear when multistart local search suffices and when population-based global search justifies its evaluation cost. Using a landscape-first design, controlled QAOA experiments identify two mechanisms making local search unreliable: parameter reuse across circuit layers and competition between 2-local and 3-local cost terms. Increasing QAOA depth alone does not replicate this effect. We test these mechanisms across eight unseen spin glasses, fresh $N=10$ and $N=12$ instances, and standard MaxCut, transverse-field Ising, and Heisenberg models. On all eight unseen spin glasses, adaptive differential evolution (DE) achieves lower median error than both multistart BFGS and multistart Powell on the two difficult constructions, whereas the independent-depth control does not. The parameter-reuse effect transfers to MaxCut at both sizes, while standard VQE models remain favorable to local search. A pre-benchmark landscape score combining random-start local outcomes and 1D parameter slices is fixed from confirmation data before evaluating new optimizers. It predicts whether adaptive DE outperforms multistart BFGS by over one spectral-range percentage point on 50 new quantum objectives with 80--86% condition-level accuracy. The clearest indicator of global-search utility is that local search frequently traps in inferior basins, rather than circuit depth or curvature anisotropy. The findings motivate whether quantum circuit complexity can be traded for harder classical optimization when robust global search is available.

Figures & tables

Figure 1: Conceptual view of the landscape-first question. Classical multimodal functions provide familiar examples of landscapes with many competing basins. In a VQA, the objective landscape is instead induced jointly by the Hamiltonian

H

and parameterized circuit

U(\boldsymbol{\theta})

. We vary these ingredients in controlled ways, measure the resulting basin structure and one-dimensional slice complexity, and ask whether those measurements indicate when multistart local search is sufficient or when sustained global evolutionary search is useful. The drawing is schematic; the classical contours are illustrative reference functions rather than data from the quantum experiments.

Phase	Purpose	Main design	Role in inference
I	Mechanism discovery	One-run screen over QAOA depth, repeated parameter use, interaction locality, mixer/coupling heterogeneity, and VQE controls	Exploratory only; used to choose candidate mechanisms
II	Controlled confirmation	18 conditions, exact objectives, 15 paired runs per primary condition, five optimizers, three function-evaluation (FE) checkpoints	Establish controlled mechanism effects and landscape–performance associations
III	Generalization and prediction	50 new quantum conditions plus four classical controls, eight runs, six optimizers; eight unseen disorder instances, $N=10,12$ transfer, MaxCut, transverse-field Ising and Heisenberg VQE	Test transfer and evaluate predictions fixed before new optimizer outcomes

Table 1: Study design. The phases have different roles: discovery, controlled confirmation, and out-of-sample validation.

Method	Class / Paradigm	Benchmark rationale
MS-BFGS	Local, quasi-Newton	Smooth local baseline; tests basin accessibility via restarts.
MS-Powell	Local, derivative-free	Direction-set local baseline; controls for gradient artifacts.
MS-CMA-ES	Evolution strategy	Population baseline with adaptive Gaussian sampling (non-DE mechanism).
iL-SHADE	Adaptive DE	Standard reference with success-history adaptation and linear population-size reduction.
jSO	Adaptive DE	Tuned reference with alternative parameter adaptation schedules.
L-SRTDE	Adaptive DE	Success-rate-based adaptation reference.

Table 2: Role and inclusion rationale for the optimizer benchmark panel.

Quantity	Operational Definition	Geometric Interpretation
$p_{\rm near}$	Fraction of random BFGS starts ending within $0.01$ normalized error of the best sampled local-search endpoint.	Empirical capture frequency of near-best local-search outcomes; high values indicate that good endpoints are easy to reach from random starts.
$g_{\rm med}$	Median gap between local-search endpoints and the best sampled local-search endpoint.	Measures endpoint-quality dispersion; high values imply substantial loss when local search reaches an inferior basin.
$p_{\rm poor}$	Fraction of starts terminating $>0.05$ normalized error above the best sampled local-search endpoint.	Empirical frequency of substantially inferior local-search outcomes.
Minima per line	Mean number of sampled local minima along random wrapped 1D line segments.	Directional multimodality (corrugation density); counts crossed ridges without capturing relative well depths.
Fourier entropy (1D)	Spectral entropy of random 1D objective profiles.	Multiscale structure; low values imply dominant wavelengths, while high values reflect irregular, multi-frequency roughness.
Positive Hessian eigenvalue ratio	$\max(\lambda_{+})/\min(\lambda_{+})$ over retained positive Hessian eigenvalues at the best sampled local-search endpoint; numerically negligible modes are excluded.	Local positive-curvature anisotropy near one endpoint; does not describe distant basin quality or accessibility.

Table 3: Landscape diagnostics, operational definitions, and geometric interpretations.

Reuse	Near-best outcomes (%)	Median endpoint gap (spectral-range pp)	Minima per line	Fourier entropy	DE advantage 5k (pp)	DE advantage 30k (pp)
1	1.6	5.2	3.734	0.284	0.3	0.5
2	0.8	9.4	5.312	0.332	2.4	1.8
4	0.8	17.3	10.141	0.420	4.2	1.8
6	1.6	29.0	13.641	0.446	7.7	4.0

Table 4: Controlled tied-reuse QAOA experiment at fixed

D=6

. Landscape accessibility and adaptive-DE advantage are reported on directly interpretable scales; positive advantage means lower median error than MS-BFGS.

Figure 2: Controlled tied-reuse experiment. Repeating each of the three QAOA cost–mixer layers while tying its angle pair progressively increases the finite-budget advantage of adaptive DE over multistart BFGS. The vertical axis is expressed in spectral-range percentage points; e.g.,

4

means a normalized-error difference of

0.04

, while negative values indicate the opposite sign of advantage.

Figure 3: Controlled mixed-locality experiment. The largest early global-search advantage occurs when 2-local and 3-local structures have comparable coefficient-norm scale. The vertical axis gives the adaptive-DE improvement over MS-BFGS in spectral-range percentage points.

Landscape measurement	5k	30k
median local-search endpoint gap	0.758	0.846
poor-endpoint fraction $>0.05$	0.783	0.811
near-best local-search rate $p_{\rm near}$	-0.575	-0.495
minima per random line	0.771	0.741
line Fourier entropy	0.771	0.732
positive Hessian eigenvalue ratio	0.389	0.499

Table 5: Phase-II descriptive Spearman correlations with adaptive-DE advantage.

Figure 4: Empirical slices through four exact quantum objectives built on the same unseen

N=10

spin-glass backbone. Top: contour plots of two-dimensional slices centered at the best-found point; the star marks that best point and the circle marks a poorer local-search endpoint used to define the principal slice direction. Bottom: the corresponding one-dimensional slices along that direction. Standard

p=3

shows only a few wells along the displayed line. Independent

p=6

increases oscillatory structure but does not create equally severe basin separation. Tied reuse

r=6

produces a much more Rastrigin-like line slice with many repeated minima, whereas the mixed-locality construction creates a narrow good basin separated from clearly worse alternatives, visually closer to a Schwefel-like competing-basin picture.

Figure 5: High-corrugation empirical scan for a standard

N=10

MaxCut QAOA instance. Among six random directions through a low-energy anchor, the line with the most local minima is shown together with an orthogonal two-dimensional slice. Standard

p=3

and independent

p=6

retain only a few wells, whereas tied reuse

r=6

produces a dense repeated-well structure.

Figure 6: Out-of-sample mechanism test on eight unseen

N=10

random 3-regular spin glasses at 30,000 FEs. Each point is one independently generated Hamiltonian. Positive values mean that the descriptively best adaptive-DE median is lower than the better of the two multistart local baselines. Values are reported in spectral-range percentage points (so

+5

means a normalized-error improvement of

0.05

); horizontal segments mark medians.

QAOA variant	vs. BFGS	vs. better local	DE wins
standard $p=3$	0.98	0.98	8/8
independent $p=6$	-0.49	-0.49	2/8
tied reuse $r=6$	4.99	4.52	8/8
2+3-local, $\alpha_{3}=1$	4.00	4.00	8/8

Table 6: Out-of-sample mechanism summary at 30,000 FEs across eight unseen spin-glass instances. Advantages are reported in spectral-range percentage points. “DE wins” counts instances for which the adaptive-DE advantage over the better local baseline is positive.

Variant	Gap	Poor (%)	Near-best (%)	Min./line	Entropy
standard $p=3$	5.0	49.2	3.9	3.75	0.280
independent $p=6$	5.4	50.8	5.5	5.48	0.360
tied reuse $r=6$	20.4	90.6	2.3	13.38	0.433
2+3-local	17.1	89.8	2.3	5.55	0.327

Table 7: Median landscape measurements across the eight unseen spin-glass instances. Gap is in spectral-range percentage points.

Model	Variant	$N=10$	$N=12$
fresh spin glass	standard $p=3$	0.95	0.36
	independent $p=6$	-1.88	-1.27
	tied reuse $r=6$	5.52	2.51
	2+3-local	3.32	2.82
MaxCut QAOA	standard $p=3$	0.00	0.00
	independent $p=6$	-0.97	-0.40

Table 8: Adaptive-DE advantage over the better local baseline at 30,000 FEs on transfer conditions, reported in spectral-range percentage points. Positive values favor adaptive DE.

Figure 7: Transfer beyond the discovery instance. Positive values indicate that the descriptively best adaptive-DE method has lower median error than the better local baseline at 30,000 FEs. The standard TFIM and Heisenberg VQE models remain locally accessible, whereas tied parameter reuse shifts both spin-glass and MaxCut QAOA toward global-search advantage.

Figure 8: Prospective prediction from landscape diagnostics on 50 new quantum conditions. The score and classification threshold were fixed from Phase II before the Phase-III optimizer outcomes were evaluated. Marker shapes distinguish the four tested model classes. The horizontal dashed line marks the prespecified target of a one-percentage-point spectral-range advantage over MS-BFGS; the vertical dotted line is the Phase-II score threshold.

Figure 9: ROC curves for the frozen landscape difficulty score on the 50 Phase-III quantum conditions. AUC measures threshold-independent discrimination of the prespecified target: an adaptive-DE advantage over MS-BFGS larger than one spectral-range percentage point.

FE	Accuracy	Balanced acc.	Precision	Recall	Specificity	AUC
5,000	0.860	0.862	0.815	0.917	0.808	0.958
15,000	0.820	0.830	0.733	0.957	0.704	0.974
30,000	0.800	0.796	0.767	0.885	0.708	0.929

Table 9: Condition-level prospective prediction of a DE advantage larger than one spectral-range percentage point on 50 new quantum conditions. AUC is computed from the continuous landscape score before thresholding.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 10: Schematic one-dimensional slices through an objective landscape. A single broad basin is favorable to local search. Multiple minima are not necessarily difficult if their objective values are similar. Difficulty for local optimization increases when different minima have substantially different quality, while a highly corrugated slice raises the counted number of minima and spreads power over more Fourier frequencies. The main-text random-line diagnostics distinguish these cases statistically over many randomly oriented slices.

Figure 11: Schematic basin accessibility in two dimensions. In a common-funnel landscape (left), many random starting points descend toward solutions of similar quality, so multistart local search has a high probability of finding a good basin. With competing basins of unequal depth (right), the endpoint depends strongly on the starting point. The near-best local-search rate estimates how often random starts reach good basins, while the endpoint-gap and poor-endpoint measurements quantify differences among the basin minima.

Figure 12: Schematic local ill-conditioning. Strongly elongated contours correspond to very different curvatures in different directions. A simple steepest-descent path can make slow, alternating progress across the narrow valley, while a curvature-aware method can align its steps more effectively. This is a local property: a large local Hessian anisotropy measure says little about whether distant basins have different objective values or how often random starts reach a good basin.

Figure 13: High-corrugation scans for the standard VQE controls: TFIM and Heisenberg Hamiltonians with hardware-efficient ansatzes at

L=1,2

. Even after deliberately selecting the roughest of six random directions, all four one-dimensional slices contain a single minimum, consistent with their local-search-friendly optimizer behavior.

Method	Population / initialization	Main settings used here	Budget behavior / implementation
MS-BFGS	$x_{0}\sim\mathcal{U}[-\pi,\pi)^{D}$	SciPy BFGS; no analytic Jacobian; max. 1,800 iterations per local run; $g_{\rm tol}=10^{-8}$ ; numerical-gradient and line-search calls count as FEs.	Restart to FE limit; SciPy.
MS-Powell	$x_{0}\sim\mathcal{U}[-\pi,\pi)^{D}$	SciPy Powell; max. 1,800 iterations; $x_{\rm tol}=10^{-8}$ ; $f_{\rm tol}=10^{-10}$ .	Restart to FE limit; SciPy; Phase III only.
MS-CMA-ES	$\lambda=\min(150,4+\lfloor 3\ln(\max(D,2))\rfloor)$ ; $\lambda=9$ at $D=6$	$\sigma_{0}=1$ ; bounded box; parameter and objective tolerances $10^{-10}$ .	Restart to FE limit; supplied CMAES.py .
iL-SHADE	$NP_{\rm init}=\min(150,\max(8,4D))$ ; 24 at $D=6$	Success-history adaptation, external archive, and population reduction; remaining settings from pyade.ilshade defaults.	One adaptive trajectory; PyADE.
jSO	Native $NP_{\rm init}=\max(30,\lfloor 25\sqrt{D}\log_{10}D\rfloor)$ ; 47 at $D=6$	Streamlined jSO implementation; current-to- $p$ best-style search, adaptive $F/CR$ memories, population reduction; native internal control retained.	One adaptive trajectory; supplied jSO module.
L-SRTDE	Native scaling $NP_{\rm init}\approx 20D$ ; 120 at $D=6$	Success-rate-dependent mutation scaling, adaptive crossover control, and population reduction; wrapper requests a cap when exposed.	One adaptive trajectory; supplied L-SRTDE module.

Appendix

Table 10: Optimizer implementation settings used in the study. “Restart” means that a fresh independent run is launched while FE budget remains. Population rules listed as native are controlled inside the supplied optimizer module rather than by the common wrapper.

Condition	$D$	$A_{\mathrm{DE,BFGS}}(5k)$	$A_{\mathrm{DE,BFGS}}(15k)$	$A_{\mathrm{DE,BFGS}}(30k)$	Best DE at 30k
Ising spin-glass reference, $N=10$	10	-0.009	-0.002	-0.002	jSO
Ising spin-glass reference, $N=12$	12	-6.4e-09	-0.001	7.2e-16	jSO
hardware-efficient ansatz, reuse 3	20	-0.189	-0.038	-0.010	L-SRTDE
QAOA $p=3$	6	0.003	0.005	0.005	jSO
QAOA $p=6$	12	-0.038	-0.018	-4.4e-04	L-SRTDE
QAOA $p=3$ , reuse 2	6	0.024	0.020	0.018	jSO

Appendix

Table 11: Complete Phase-II confirmation results.

Condition	FE	Alternative	Paired advantage	95% CI	Win frac.	$p_{\rm Holm}$
QAOA $p=3$ , reuse 2	5,000	iL-SHADE	0.023	[0.010, 0.046]	0.93	2.44e-04
QAOA $p=3$ , reuse 2	30,000	jSO	0.015	[0.010, 0.022]	0.93	4.88e-04
QAOA $p=3$ , reuse 4	5,000	iL-SHADE	0.040	[0.011, 0.058]	1.00	2.44e-04
QAOA $p=3$ , reuse 4	30,000	jSO	0.015	[0.007, 0.031]	0.93	4.88e-04
QAOA $p=3$ , reuse 6	5,000	iL-SHADE	0.077	[0.066, 0.088]	1.00	2.44e-04
QAOA $p=3$ , reuse 6	30,000	L-SRTDE	0.038	[0.034, 0.042]	1.00	2.44e-04

Appendix

Table 25

Model	Instance	Variant	$D$	$A_{\mathrm{DE,BFGS}}$	$A_{\mathrm{DE,local}}$
holdout spin glass	H01	2+3-local	6	0.040	0.040
holdout spin glass	H01	independent $p=6$	12	-0.007	-0.007
holdout spin glass	H01	standard $p=3$	6	0.010	0.010
holdout spin glass	H01	tied reuse $r=6$	6	0.043	0.043
holdout spin glass	H02	2+3-local	6	0.040	0.040
holdout spin glass	H02	independent $p=6$	12	-0.001	-0.001

Appendix

Table 12: Complete Phase-III results at 30,000 FEs.

Variational Quantum Algorithms

Variational quantum algorithms use parameterized quantum circuits and classical optimization to approximate solutions to quantum and optimization problems.

See all 28 papers

Oct 4, 2026

Optimization Geometry of QAOA and Variational Quantum Algorithms

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.

Vojtěch Novák, Ivan Zelinka, Silvie Illésová +2

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 +3

Quantum Approximate Optimization Algorithm Variational Quantum Algorithms Loss Landscape Geometry

Ask PDF

Sep 19, 2026

Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

We benchmark classical optimization of a fixed low-depth Quantum Approximate Optimization Algorithm (QAOA) ansatz across four cost-Hamiltonian families at

N=12

p=3

, and

D=6

. Ten optimizers are compared over 25 independent runs under common ceilings of 10,000 and 30,000 function evaluations (FEs), first with exact statevector objectives and then with two additive observation-noise levels. Exact objectives favor multistart BFGS and multistart CMA-ES. Under noisy feedback, adaptive population methods become more competitive, but the ranking depends on whether performance is measured by the best exact point visited or by the point selected from noisy observations. A targeted extension over all three pre-screened instances per family confirms this regime change while showing that named adaptive-DE winners are instance dependent: jSO-lite leads low-noise oracle search, iL-SHADE high-noise oracle search, and L-SRTDE high-noise selected solutions in the equal-instance summaries. Bootstrap analysis quantifies a non-negligible high-noise search--selection gap, and a retrospective fixed-budget verification proxy shows that reserving a small measurement budget for final re-evaluation improves selected quality across all ten methods at 30,000 FEs. A supplementary structure-aware study further shows that QAOA cross-depth restriction and continuous basin refinement are more useful in these conditions than standalone Monte Carlo tree-search selection. Overall, optimizer choice depends jointly on landscape structure, observation noise, and final-point identification.

Vojtěch Novák, Ivan Zelinka, Swagatam Das +1

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, Lithuania +2

Stochastic Optimization Black-Box Optimization Quantum Approximate Optimization Algorithm Differential Evolution

Ask PDF

Aug 4, 2026

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

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.

Harrison Copp, Charlton Li, Anžej Margeta-Cacace +1

Yale University

Barren Plateaus Quantum Approximate Optimization Algorithm

Ask PDF

Abstract

Variational Quantum Algorithms

Explore similar work

Optimization Geometry of QAOA and Variational Quantum Algorithms

Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

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