arXiv:2609.23180
Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization
Vojtěch Novák, Ivan Zelinka, Swagatam Das, Martin Beseda
Abstract
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.
AI Summary
The paper asks how classical optimizer performance for low-depth QAOA depends on landscape, observation noise, and final-point selection. It compares ten optimizers on four Hamiltonian families—3-regular Max-Cut, two-dimensional Edwards–Anderson, diluted three-spin glass, and Sherrington–Kirkpatrick—using exact statevector simulation at $N=12$, $p=3$, and six parameters. The main benchmark uses one screened instance per family, 25 runs per condition, and evaluation ceilings of 10,000 or 30,000. Noise is independent additive Gaussian noise with standard deviations 0.005524 and 0.044194 in normalized objective units. With exact objectives, multistart BFGS and multistart CMA-ES reach median numerical-reference accuracy on all four primary instances at 30,000 evaluations. Noisy feedback favors adaptive population methods, but rankings differ between the best exact point visited and the point selected by its lowest noisy observation. A five-method extension to three instances per family retains this regime change while changing named winners: aggregate ranks favor jSO-lite for low-noise search, iL-SHADE for high-noise search, and L-SRTDE for high-noise selected quality. Restart-bootstrap intervals quantify selection losses. A retrospective proxy reserving 200 of 30,000 evaluations for remeasurement reduces selected error across all ten methods, closing a median 35% of the search–selection gap. Supplementary tests separate cross-depth localization and continuous refinement from standalone MCTS selection. Stated limitations include small instance ensembles, fixed low optimization dimension, globally fixed rather than nested-tuned hyperparameters, numerical BFGS gradients, and synthetic rather than shot- or hardware-derived noise. Verification operates on stored query records, not guaranteed-distinct parameter candidates.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.