PaperlayerView exact revision on arXiv

Source-linked AI summary

Landscape Limits of Quantum-Inspired Evolutionary Optimization across 256 continuous functions

Rishi Govind, Ferdin Sagai Don Bosco, Kasturi Venkata Srikanth, Aman Mittal, Abhishek Singh, Aditya Singh, Abhishek Chopra

arXiv:2609.30938v1cs.NEmath.OC

TL;DR

QIEO’s single-elite rotations cannot represent covariance or keep competing basins alive, raising the question of when its optimization performance is uncompetitive. The paper compares this search mechanism with covariance-adapting CMA-ES and reports higher QIEO strict-success rates on the studied suite, with important cost and scope qualifications.

  • Problem

    QIEO’s locally applied rotation cannot represent covariance or keep two competing basins alive, motivating the question of when it fails to achieve competitive optimization performance.

    Source: §I · p. 1

  • Method

    QIEO uses probabilistic observation and repeated small rotations toward an elite, while CMA-ES adapts a full covariance matrix from successful search steps.

    Source: §I · p. 1, A. Quantum-inspired evolutionary… · p. 3, C. Covariance matrix adaptation… · p. 6

  • Results

    On this 256-function suite, real-coded QIEO’s strict success rate was 75.8%, versus 62.1% for CMA-ES and 46.5% for GA.

    Source: A. Comparison of aggregate… · p. 10, §VI · p. 17

  • Takeaways & Limitations

    The reported QIEO failure pattern centers on multimodality and dimension, while non-differentiability and discontinuity cost it nothing in this analysis.

    Source: §VII · p. 20

    The suite-specific comparison does not establish QIEO’s dominance on BBOB or CEC, whose dimension distributions, rotations, and accuracy targets differ.

    Source: A. Comparison of aggregate… · p. 10

Abstract

from arXiv · show

Quantum-inspired evolutionary optimization (QIEO) represents design variables as a set of qubits and searches a continuous, multi-dimensional landscape through rotation of the qubit's amplitude pair. Every generation rotates those amplitudes toward a single elite, which corresponds to that generation's best. The update is cheap, almost parameter-free, and well-suited for massive parallel implementation, which has encouraged its adoption in engineering, design, and planning applications. However, there are critical issues with this formulation, principally, the treatment of design variables as independent probability components which make it incapable of exploiting local curvature, anisotropy, or variable coupling. Despite this, QIEO is believed to hold promise, and has been used extensively to solve real-world problems, with significant qualitative and computational advantage over its classical counterpart, Genetic Algorithm (GA). A collection of 256 (actually 508; 256 unshifted + 252 shifted, 4 could not be shifted) continuous function are selected from the prior works, in such a way that they represent eleven landscape characteristics, namely continuity, differentiability, separability, scalability, modality, convexity, conditioning, symmetry, maximum dimensionality, dimension dependency, and the coupling pattern of the design variables. These functions are then solved by three QIEO variants, two GA encodings and Hansen's Covariance Matrix Adaptation Evolution Strategy (CMA-ES). The results are evaluated in terms of computational cost, solution precision, and specialization across landscape characteristics. They identify the conditions under which QIEO provides competitive performance, clarify where its independent-variable representation becomes limiting, and establish whether particular QIEO variants offer advantages for specific landscape characteristics.

I. INTRODUCTION

The introduction asks when QIEO ceases to be competitive, given that its coordinate-wise pull toward one elite cannot represent covariance or preserve competing basins. It motivates a landscape-stratified, budget-normalized comparison with genetic algorithms and CMA-ES.

A. Quantum-inspired evolutionary optimization

  • QIEO represents each coordinate with an amplitude pair, observes classical candidates, then rotates each pair to make the current elite's value more likely.Probabilistic observation supplies exploration, while repeated small rotations supply exploitation without explicit crossover or mutation.Source: §I · p. 1, A. Quantum-inspired evolutionary… · p. 3

I. INTRODUCTION

  • The study asks under what conditions QIEO fails to achieve competitive performance because its local rotation cannot represent covariance or sustain competing basins.CMA-ES instead adapts a full covariance matrix from successful search steps.Source: §I · p. 1
  • The benchmark comprises 256 continuous functions labelled by eleven landscape characteristics and compares three QIEO variants, two GA encodings, and CMA-ES.The functions cover properties including modality, conditioning, dimensionality, and variable coupling.Source: §I · p. 2
  • CMA-ES reaches 62.1% strict success at a median of 670 evaluations per function, while QIEO spends a median of 87003; at 10−8, CMA-ES leads 51.2% to 46.5%.Across the suite, QIEO's 49 exclusive wins are almost all two-dimensional, densely multimodal cases, while CMA-ES's 12 exclusive wins are multimodal and mostly ill-conditioned; only modality and convexity remain univariate predictors after correction.Source: §I · p. 2

II. RELATED WORK

  • Prior continuous-QIEO studies establish feasibility, but none in the cited review provides a landscape survey or budget-normalized comparison.The introduction contrasts this gap with CMA-ES's covariance adaptation and known liability on strongly multimodal landscapes, and situates the question in prior GA work on rotated separable benchmarks.Source: §II · p. 2

A. Quantum-inspired evolutionary optimization

  • Because QIEO factors its sampling by coordinate and updates toward one elite, it cannot directly represent variable correlations or maintain separate modes for competing basins.A sufficiently small rotation retains some probability of alternatives, but does not create a joint probability model over variables or preserve multiple elite basins.Source: A. Quantum-inspired evolutionary… · pp. 3–4

B. Genetic Algorithm

The GA baseline uses both real-valued and binary encodings, with selection, crossover, mutation, and elitism applied under settings matched as closely as possible to QIEO.

B. Genetic Algorithm

  • The baseline considers real-valued chromosomes containing the decision variables directly and binary chromosomes using 16 bits per variable.The binary GA and binary QIEO share a decoding rule, so they use the same discretized domain and per-variable resolution.Source: B. Genetic Algorithm · pp. 4–5
  • The GA selects parents by tournament, forms offspring through single-point crossover, and mutates 15% of genes.Tournament selection samples K individuals and chooses the best; real-coded mutation perturbs coordinates subject to bounds.Source: B. Genetic Algorithm · p. 5
  • Two elite individuals are copied unchanged into the next generation, preserving the best solution found so far.The implementation matches QIEO experiments as closely as the two algorithmic representations permit.Source: B. Genetic Algorithm · pp. 4–5

C. Covariance matrix adaptation evolution strategy

CMA-ES searches with an adaptive multivariate Gaussian distribution, updating its mean, global step size, and covariance from ranked offspring. The comparison uses Hansen's default implementation without restarts.

C. Covariance matrix adaptation evolution strategy

  • CMA-ES adapts its covariance to learn the scale and correlation of successful steps, allowing its search distribution to align with valleys, ridges, and coupled directions.The covariance's eigenvectors identify search directions and its eigenvalues set exploration scales; the loop evolves a Gaussian distribution rather than chromosomes.Source: C. Covariance matrix adaptation… · p. 6, Figure 3 · p. 7
  • The study uses Hansen's textbook defaults, disables restarts, and lets CMA-ES stop on its own internal tolerances rather than the shared cap.At D = 2 its population is six candidates per generation, compared with QIEO's one thousand.Source: C. Covariance matrix adaptation… · p. 6, Figure 3 · p. 7
  • A single CMA-ES run may converge prematurely to a local optimum on a multimodal landscape; restart strategies address this limitation.Restarts are excluded from the reported comparison.Source: C. Covariance matrix adaptation… · p. 6, Figure 3 · p. 7
  • Each generation samples λ offspring from a Gaussian, evaluates and ranks them, then updates the mean, step size, and covariance.The covariance update combines rank-one and rank-µ contributions, while cumulative step-size adaptation adjusts the global step size.Source: C. Covariance matrix adaptation… · p. 6, Figure 3 · p. 7

A. Objectives and their labels

The study labels each of 256 functions across eleven landscape characteristics, assigning labels before analyzing optimizer outcomes. The characteristics distinguish properties such as separability, conditioning, dimension dependence, and patterns of variable coupling.

A. Objectives and their labels

  • Each of the 256 functions receives eleven labels drawn from prior collections or, where needed, inspection of its coded formula, before campaign analysis.This keeps the labels independent of optimizer traces.Source: A. Objectives and their labels · p. 7
  • The labels cover continuity, differentiability, separability, scalability, modality, and convexity, distinguishing local smoothness, coordinate independence, and landscape structure.Separability means the function decomposes into independent single-variable contributions; modality concerns the number and distribution of local extrema.Source: A. Objectives and their labels · p. 7
  • The remaining labels capture conditioning, symmetry, maximum dimensionality, and whether the global optimum depends on dimension.A dimension-dependent optimum requires accounting for changing target values when comparing performance across dimensions.Source: A. Objectives and their labels · p. 8
  • Variable coupling measures how one variable's contribution or optimum depends on others, and distinguishes pairwise, aggregate, and fixed-dimension interactions.These non-separable forms present different geometries to coordinate-wise operators and behave differently in the reported data.Source: A. Objectives and their labels · p. 8

B. Shifted landscapes

The shifted campaign tests whether coordinate-wise samplers benefit from optima at familiar locations by relocating each eligible function's minimizer within its box. It is a paired robustness check, with some functions excluded because the required minimizer vector is unavailable or outside the coded bounds.

B. Shifted landscapes

  • The shifted campaign relocates each eligible minimizer within the original box while keeping the coded formula, box, and published optimum unchanged.A coordinate-wise sampler might otherwise encounter optima at the origin, box centre, or a bound by chance.Source: B. Shifted landscapes · p. 8
  • A seeded relocation is shared across solvers, and the transformed objective preserves the optimum at the new location while penalizing out-of-box preimages.The preimage maps a candidate back to the original coordinates; the penalty includes a quadratic term and a large barrier.Source: B. Shifted landscapes · p. 8
  • The shifted comparison covers 251 landscapes because five functions lack a unique in-box minimizer vector suitable for the transformation.Two lack a unique tabulated coordinate vector, while three published parameter vectors fall outside the coded box.Source: B. Shifted landscapes · p. 8

C. Termination conditions

The experiments use early stopping, so a shared nominal generation cap does not equalize actual computational expenditure. Scoring reports strict success alongside residual distributions and comparisons at multiple tolerances.

C. Termination conditions

  • QIEO and GA stop at the generation cap or after stagnation, and actual evaluations can therefore fall below the nominal budget.The production rule triggers after 40 consecutive generations without fitness change at the specified tolerance of 1e-6.Source: C. Termination conditions · pp. 8–9
  • The GA baseline and QIEO variants share population, bounds, cap, decoding, and stopping criteria, while differing in chromosome operations versus elite-directed probability rotations.The variants are fixed-angle binary, adaptive-angle binary, and real-coded QIEO.Source: C. Termination conditions · pp. 8–9

D. Implications of the imposed budget cap

  • A shared cap equalizes the permissible limit, not expenditure: QIEO's median is 87,003 evaluations, while default CMA-ES typically stops after a few hundred.QIEO's median is reported as 1.7% of the cap.Source: D. Implications of the imposed budget… · p. 9

E. Scoring

  • Strict success means Excellent or Good, corresponding to a scaled residual below roughly 10^-3, but that cutoff is a scoring choice.The study also reports residual distributions and rankings at several tolerances.Source: E. Scoring · p. 9
  • “QIEO best-of-3” and “GA best-of-2” are oracle upper bounds across encodings, not single-run outcomes.They represent the better result available if every encoding in the family were tried.Source: E. Scoring · p. 9

F. Statistical Analysis

The analysis reports success rates with uncertainty intervals, tests associations between landscape labels and QIEO success, and adjusts for correlated characteristics and dimension. These analyses describe associations rather than causal effects.

F. Statistical Analysis

  • Success rates are reported as percentages with two-sided 95% Wilson intervals, and characteristic-specific rates are k/n.Wilson intervals are used for the small and unbalanced strata produced by labeling.Source: F. Statistical Analysis · p. 9
  • For each binary label, Pearson's chi-square test with Yates' correction assesses association with real-coded QIEO success, alongside an odds ratio and interval.A 0.5 cell correction keeps the odds ratio defined for sparse tables, including those with a zero cell.Source: F. Statistical Analysis · p. 9
  • The nine tests report raw and Holm-adjusted p-values, with Holm adjustment used for claims surviving multiple comparisons.The adjustment changes which labels are called significant.Source: F. Statistical Analysis · p. 9
  • A logistic model estimates adjusted associations for five binary traits and log2 dimension across real-coded QIEO, CMA-ES, and GA best-of-2.Predictor effects are expressed as odds ratios; the joint model is not a causal claim.Source: F. Statistical Analysis · pp. 9–10

V. RESULTS

Real-coded QIEO leads on the suite’s strict-success rate, but its cost and precision profile changes the comparison: CMA-ES is far more evaluation-efficient and leads at tighter tolerances. QIEO’s landscape associations are strongest for modality and convexity, while differentiability and continuity show no association.

B. Caveat 1: Evaluation cost

  • 583.6 versus 1.79 functions solved per million evaluations favors CMA-ES over QIEO by a factor of 326.CMA-ES and QIEO occupy the two cost–quality Pareto-efficient corners; both GA encodings are dominated.Source: B. Caveat 1: Evaluation cost · p. 10, Figure 5 · p. 11

C. Caveat 2: Degree of accuracy

A. Comparison of aggregate strict-success rates

1) Univariate landscape associations:

  • After Holm correction, only multimodality and convexity remain associated with QIEO strict success; continuity and differentiability show no difference.QIEO falls from 90.9% on unimodal to 70.0% on multimodal functions, and from 94.7% on convex to 72.0% on non-convex functions.Source: 1) Univariate landscape associations · p. 12, Table IV · p. 12

2) Joint logistic model:

The joint model reduces the catalogue’s eleven landscape labels to modality and dimension as the main predictive axes, with QIEO and CMA-ES showing different sensitivities. The results also identify coupling cases where their relative performance departs from the expected pattern and show that binary QIEO’s precision is limited by encoding resolution.

2) Joint logistic model:

  • After joint adjustment, multimodality and dimension remain effective predictors, while conditioning, symmetry, separability, and non-differentiability lose significance.The authors describe the eleven-label taxonomy as a useful vocabulary but a redundant predictive basis.Source: 2) Joint logistic model · p. 12
  • Each dimension doubling multiplies QIEO’s success odds by 0.33, while CMA-ES is nearly dimension-neutral (odds ratio 1.01) and is chiefly constrained by multimodality.QIEO leads by 24 points at D ≤2, draws level at D = 3–5, and CMA-ES leads among the twelve names with D ≥6; that top-bin estimate is limited by the suite’s small sample.Source: 2) Joint logistic model · pp. 12–13, Figure 9 · p. 13

3) Coupling and conditioning:

  • QIEO is strongest on independent-coordinate, single-basin landscapes and weakest when multimodality coincides with dense coupling; CMA-ES follows the qualitative pattern at a lower level.The modality-by-coupling figure indicates degradation where basins and cross-coordinate terms coincide.Source: 3) Coupling and conditioning · p. 13, Figure 10 · p. 14
  • On fifteen adjacent-pair-coupled names, QIEO reaches 73.3% versus CMA-ES’s 53.3%, despite the geometry being expected to favor covariance adaptation.The authors attribute this result to CMA-ES’s small default population relative to QIEO’s thousand samples.Source: 3) Coupling and conditioning · pp. 13–14
  • For the nonseparable, ill-conditioned, multimodal group, QIEO’s 57.1% and CMA-ES’s 58.7% have overlapping Wilson intervals; GA reaches 31.7%.The authors interpret this as evidence that the difficulty in this region is not specific to QIEO.Source: 3) Coupling and conditioning · p. 14

E. Performance comparison of QIEO variants

  • At 10^-8, real-coded QIEO reaches 46.5% versus binary QIEO’s 21.9%, while both reach machine precision on 10.9% of names.The authors attribute the precision gap to binary quantization and point to finer encoding, local refinement, or real-coded QIEO as remedies.Source: E. Performance comparison of QIEO… · p. 14

F. QIEO versus industry-standard CMA-ES

QIEO and CMA-ES have complementary strengths, so combining them solves more functions than either alone. The remaining failures cluster in difficult problem families; shifting minima barely changes aggregate success, while several published minima are contradicted by multiple configurations.

F. QIEO versus industry-standard CMA-ES

  • QIEO’s 49 exclusive wins are mostly two-dimensional, densely multimodal problems, whereas all 12 exclusive CMA-ES wins are multimodal and mostly ill-conditioned.For curved, nearly flat regression troughs, CMA-ES’s anisotropic step-size adaptation can express search directions that coordinate-wise rotation cannot.Source: F. QIEO versus industry-standard CMA-ES · pp. 14–16
  • A QIEO–CMA-ES portfolio solves 205 of 256 names (80.1%), compared with 194 for the better single solver; adding both GA encodings raises this only to 212.CMA-ES recovers 14 of the 62 names where real-coded QIEO fails, while the GA recovers one.Source: F. QIEO versus industry-standard CMA-ES · p. 16

G. Universally unsolved functions

  • The 44 functions missed by every configuration cluster in nonlinear least-squares, table, and classical-hard families, rather than in the high-dimensional tail.Their median dimension is 2, matching the suite; the authors recommend reporting per-family results because benchmark family mix can change solver rankings.Source: G. Universally unsolved functions · p. 16

H. Shifted comparison

  • Shifting tabulated minima leaves strict-success rates nearly unchanged: real-coded QIEO moves from 75.4% to 74.5%, GA from 46.1% to 45.4%, and CMA-ES from 60.9% to 61.0%.QIEO’s 13 losses and nine gains are balanced; the authors take this as evidence against an origin-bias explanation for its lead.Source: H. Shifted comparison · p. 16

I. Suspect published minima

  • Bad labels recur across configurations for several published minima: Holder-Table 2 and Multi-Gaussian receive them from all six, while Cosine Mixture and Mishra 1 and 2 receive them from five of six.The paper says these six names remain in the reported rates, and three are Gavana additions.Source: §I · p. 17

VI. DISCUSSION

The discussion recasts the comparison as a division of labor: QIEO’s coverage and CMA-ES’s curvature adaptation suit different landscapes. It emphasizes cost, accuracy, and benchmark-reporting caveats, and concludes that their complementary strengths favor reporting or using both.

VI. DISCUSSION

  • CMA-ES terminates after a median 670 evaluations (0.0134% of QIEO’s permitted budget), versus QIEO’s median 87,003; per-evaluation yields are 583.6 versus at most 1.79 names per million, and ranking reverses at 10−7.8.Source: §VI · p. 17
  • QIEO’s exclusive wins favor low-dimensional, densely multimodal landscapes, while CMA-ES’s exclusive wins are multimodal and mostly ill-conditioned.QIEO’s coverage falls with dimension; CMA-ES is defeated by multimodality and is described as insensitive to dimension.Source: §VI · pp. 18–19
  • The joint model retains multimodality and dimension for QIEO, while dimension is statistically irrelevant for CMA-ES and multimodality is its only surviving predictor.The authors report that the two algorithms’ nearly orthogonal weaknesses explain the portfolio’s 205/256 result versus 194 for the better single solver.Source: §VI · p. 18
  • Real-coded QIEO is presented as a good choice for small-dimensional, cheap, parallel, densely multimodal problems when residuals near 10^-6 are acceptable; the authors recommend pairing it with CMA-ES.The portfolio reaches 80.1%, versus at most 75.8% for either solver alone.Source: §VI · p. 19
  • The benchmark discussion recommends reporting cost-normalized rates beside raw rates, multiple accuracy thresholds, and joint models of landscape properties.A shared evaluation cap does not equalize expenditure when population sizes differ by two orders of magnitude.Source: §VI · p. 19
  • The GA is Pareto-dominated in the reported comparison, using a median of 88,500 evaluations for a hit rate fifteen points below CMA-ES and reaching 10^-8 on 6.2% of names versus 51.2%.It recovers only one of 63 QIEO failures and is weaker in every plotted characteristic slice.Source: §VI · p. 19
  • The study uses one run per name and encoding, default CMA-ES without restarts, only twelve names above D = 5, expert-tagged landscape labels, and published minima that may be erroneous.The authors identify restart CMA-ES under the same cap as the most valuable follow-up; multimodality conclusions apply to default CMA-ES.Source: §VI · p. 19

VII. CONCLUSION

  • Real-coded QIEO has the higher hit rate on this suite at a 10^-3 gate, despite using two orders more sampling per name even when allowed to stop on stagnation; CMA-ES is more accurate wherever it works and overtakes below 10^-7.8.Forty-four catalogue names resist all tested solvers, and six have published minima contradicted by the runs.Source: §VII · p. 20

APPENDIX A PROPERTY-WISE STRICT-SUCCESS RATES

The appendices report property-wise strict-success rates, identify objectives unsolved by every solver, reproduce the coded benchmark campaigns, and document the binary-to-real coordinate mapping.

APPENDIX A PROPERTY-WISE STRICT-SUCCESS RATES

  • Table VI lists the property-wise strict-success heatmap row values, with Wilson 95% intervals for the QIEO real-coded column.Source: Appendix A · p. 20

APPENDIX B UNIVERSALLY UNSOLVED NAMES

  • The listed objectives are not strict successes for any QIEO or GA encoding or CMA-ES; Meyer, Meyer–Roth, and Osborne are poor for every solver because their published optimum lies outside the coded box.Those three functions are listed separately from the landscape core.Source: Appendix B · p. 20

APPENDIX C CODED CATALOGUE AND CAMPAIGN TABLES

  • The catalogue reprints 256 coded objectives with equations, boxes, dimensions, published optima, visualizations, and campaign tables; shifted names lacking a tabulated optimum in the box are marked skipped.Source: Appendix C · p. 20

APPENDIX D EXTRA STUFF

  • Binary QIEO interprets each coordinate substring as an unsigned integer, then maps it to a decoded real coordinate with fixed-point mapping and uniform representational resolution over the prescribed box.Source: Appendix D · p. 20

Related papers

Loading 2609.30938v1…