Pith. sign in

REVIEW 4 major objections 4 minor 64 references

Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms

T0 review · 4 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Searched by a classical evolutionary optimizer, the latent space of a graph autoencoder yields maximum cut instances on which the quantum RQAOA and the classical GW algorithm diverge sharply.

desk verdict A genuine new instance-generation pipeline for quantum algorithm benchmarking, but the central 'hard instances' claim needs a baseline before it can be believed. read the letter →

arxiv 2502.12012 v3 pith:56CK22RN submitted 2025-01-30 cs.ET cs.AIcs.NEquant-ph

Shuaiqun Pan , Yash J. Patel , Aneta Neumann , Frank Neumann , Thomas Bäck , Hao Wang This is my paper · ORCID
classification cs.ETcs.AIcs.NEquant-ph MSC 68Q1290C27
keywords maximumcutRQAOAGoemans-WilliamsonalgorithmgraphautoencoderCMA-ESlatentspacesearchquantumapproximateoptimizationbenchmarkinstancegeneration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Searched by the classical optimizer CMA-ES, the latent space of a graph autoencoder yields maximum cut instances that split the recursive quantum approximate optimization algorithm (RQAOA) from the classical Goemans-Williamson (GW) algorithm. The authors found thousands of 20-node and 100-node graphs on which one algorithm clearly beats the other, and their point is that hard instances for this quantum-classical comparison can be constructed on demand by evolutionary search, not merely described by theoretical guarantees. A machine-learning analysis over 18 graph features separates RQAOA-dominant from GW-dominant instances almost perfectly, with the GW algorithm's own semidefinite-relaxation cost ratio as the single most predictive feature. The result matters because concrete hard-instance families are exactly what the literature has lacked as benchmarks for deciding when near-term quantum optimization heuristics pay off.

What carries the argument

Three components carry the argument. PIGVAE maps graphs into a continuous latent space invariant to node relabeling, which is what makes a continuous search over graphs possible. CMA-ES searches that space to maximize the fitness ratio $p_{\mathrm{GW}}(I)/p_{\mathrm{RQAOA}}(I)$ or its reciprocal, with each evaluation decoding a latent point to a graph and running both algorithms 100 times; decoded graphs that are disconnected are handled component-wise, and components below the threshold $n_c$ are solved by brute force. An evaluation block then computes 18 graph-level features ranging from density, girth, assortativity, and Laplacian eigenvalues to statistics of GW's semidefinite relaxation, and an AutoML pipeline turns those features into classifiers and partial-dependence models that show which structures drive the divergence.

What would settle it

Decode a random sample of CMA-ES final search points, solve the decoded 20-node graphs exactly by brute force, and check that the RQAOA-vs-GW performance ratios persist against the true optimum and that the decoded graphs remain connected and structurally close to the six training graph families; if the ratios collapse or the graphs are degenerate (for example, dominated by isolated nodes), the evolved hard instances are artifacts of the autoencoder's decoder rather than genuine benchmarks.

Watch

Extended reading notes

Core claim

The central claim is a constructive method that pinpoints maximum cut instances which pose significant challenges or are notably more tractable for RQAOA relative to the GW algorithm. The pipeline trains a PIGVAE (permutation-invariant variational graph autoencoder) on graphs from six standard random-graph models, then runs CMA-ES in the 64-dimensional latent space with fitness $p_{\mathrm{GW}}(I)/p_{\mathrm{RQAOA}}(I)$ to evolve hard-for-RQAOA instances and the reciprocal to evolve easy-for-RQAOA instances. Each fitness evaluation decodes a latent point into a graph and runs both algorithms 100 times, taking the median cut value. The method produced 1,519 RQAOA-favored and 1,231 GW-favored instances at 20 nodes, and 850 of each at 100 nodes; a classifier built on 18 features separates the two families with balanced accuracy $0.9988 \pm 0.0012$ at 20 nodes and perfect accuracy at 100 nodes. The dominant predictor is the expected cut value of GW's randomized rounding normalized by its semidefinite bound, followed by spectral properties of the normalized Laplacian. A secondary analysis, labeling instances where RQAOA beats GW by at least 4 percent, yields balanced accuracies of 0.9826 at 20 nodes and 0.8343 at 100 nodes, with density emerging as a key feature.

Load-bearing premise

The whole search rests on the premise that points in the PIGVAE latent space decode into valid, representative graphs, and the load-bearing evidence for that premise is the paper's own link-prediction result of macro ROC-AUC 0.611 on 100-node graphs, barely above chance.

Editorial extensions

If this is right

  • The generated 20-node and 100-node graph sets can serve directly as benchmarks for any future comparison of RQAOA against classical max-cut heuristics, filling the gap the paper identifies: existing theory named hard graph families but gave no concrete construction.
  • Once trained, the 18-feature classifiers can predict which algorithm dominates on a new graph from graph and SDP-relaxation statistics alone, without a fresh RQAOA evaluation.
  • Because RQAOA-dominant instances cluster in a narrow performance-ratio band (0.952-0.979 at 20 nodes) while GW-dominant instances span a wider band (0.720-0.990), the two algorithms fail in detectably different regimes rather than by random fluctuations.
  • The near-perfect classifier separation implies the divergence between the two algorithms is systematic and feature-detectable, so the evolved instances expose structural differences between quantum-informed recursion and classical SDP rounding, not merely stochastic noise.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the 100-node autoencoder's link-prediction score (macro ROC-AUC 0.611, barely above chance) reflects a weak decoder, the 100-node benchmark instances may be partly decoder artifacts; a natural check is to compare the performance-ratio distribution of CMA-ES's final population against randomly sampled latent points decoded by the same model.
  • The same latent-space-plus-evolution recipe should transfer to other solver pairs, such as QAOA at depth $p \ge 2$ versus GW or RQAOA versus simulated annealing, yielding a general tool for constructing contrasting benchmarks rather than a RQAOA-specific one.
  • Because only depth-1 RQAOA (classically simulable in $O(n^4)$) is evaluated, the evolved hard instances may not stay hard for deeper RQAOA; re-running the same graphs at depth $p \ge 2$ would show whether the separation survives outside the classically simulable regime.
  • The authors note in their conclusion that PIGVAE suffers severe memory bottlenecks for 400-node graphs, so the benchmark's scope is tied to the autoencoder's capacity until lighter architectures, sparse attention, or diffusion models replace it.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a pipeline for evolving maximum cut instances that are intended to be respectively hard or easy for the recursive quantum approximate optimization algorithm (RQAOA) relative to the Goemans and Williamson (GW) classical algorithm. A permutation-invariant graph variational autoencoder (PIGVAE) is trained on graphs from six random graph models, and CMA-ES is then run in the latent space to maximize the ratio p_GW(I)/p_RQAOA(I) or its inverse, where the p-values are medians over 100 stochastic trials. The authors evaluate the approach on 20-node and 100-node graphs, report feature analyses using parallel coordinate plots and TPOT classifiers, and claim that the generated instances serve as benchmarks that expose RQAOA's strengths and weaknesses. The manuscript concludes that RQAOA can offer substantial benefits over GW and that the method opens new directions for graph generation research.

Significance. If the central claim is established, the paper would provide a practical instance-generation method and a benchmark set for quantum versus classical max-cut heuristics, which is a useful contribution to both evolutionary computation and quantum optimization. The core idea of using CMA-ES over a learned graph latent space is not inherently circular, and the availability of a Zenodo repository with code and supplementary material is a strength. However, the current evidence is not sufficient to support the benchmark claim: the absence of a random-instance baseline means the observed performance ratios could be the upper tail of a noisy objective, the 100-node decoder is reported to have link-prediction ROC-AUC of only 0.611, and the feature analysis is partly circular because its top feature is derived from GW's internal relaxation performance. These issues are addressable with additional experiments and reframing, but they are load-bearing.

major comments (4)
  1. [§4 (Eq. 1) and §5.2] The claim that CMA-ES 'effectively pinpoints' instances that are hard or easy for RQAOA relative to GW is not supported without a baseline. The fitness function p_GW(I)/p_RQAOA(I) is being maximized, so even with perfectly ordinary graphs, CMA-ES will return instances with unusually high ratios simply by selecting the tail of a noisy objective. The reported 20-node RQAOA-dominant ratios are close to 1 (0.952–0.979), and the 100-node ratios are described only qualitatively. Please report the same ratio distribution for (i) random latent points drawn from the same bounded search region, (ii) random graphs from the six generators used for GAE training, matched by node count and, where feasible, edge density, and (iii) simple Erdős–Rényi graphs with the same node count. A nonparametric test such as Mann-Whitney U with effect sizes should be used to show that the evolved instances are not merely the upper tail of the background noise. Without such a control, the central benchmark contribution is an assertion rather than a demonstrated result.
  2. [§5.2, GAE evaluation] The 100-node results rest on a decoder that the paper itself reports as barely above chance at link prediction (macro ROC-AUC 0.611±0.001, versus 0.5 for random guessing). Because every CMA-ES search point is decoded through this GAE, low reconstruction fidelity means the evolved 100-node instances may be unrepresentative of any meaningful graph distribution. The smoothness evidence in Fig. 3 concerns latent-space clustering of training embeddings, not the fidelity of decoded graphs. Please add a direct validation of decoded graphs, for example by comparing feature distributions of decoded graphs against training graphs, or by reporting full-graph reconstruction metrics. If the decoder fidelity cannot be improved, the 100-node claims should be restricted or substantially softened.
  3. [§5.2, Feature analysis; §B (Table A1/A2)] The machine-learning feature analysis is partly circular. The label is defined by the ratio p_GW(I)/p_RQAOA(I) in Eq. (1), while the top predictive feature EXPECTED_COSTGW_OVER_SDP_COST is computed from GW's own average cost divided by the SDP optimum. A classifier can therefore predict the favored algorithm using GW's internal performance measure as a near-oracle, which does not establish that the discovered graphs differ in structurally meaningful ways. The permutation results are consistent with this concern: excluding the top two features leaves the 100-node accuracy unchanged (1.0000±0.0000). I recommend either removing GW-derived features from the explanatory analysis, or explicitly reframing the analysis as instance classification with algorithm-performance features and adding a structural-features-only ablation to support any claim about graph structure.
  4. [§5.2, representative case and §4, fitness evaluation] The hardness criterion is not statistically robust as reported. The manuscript states that on a representative RQAOA-favored 20-node instance, RQAOA outperforms GW in only 4 of 100 stochastic trials, with identical results in the rest. A median-based fitness can therefore label an instance as 'considerably more manageable' when the actual per-trial win probability is only 4%. Please report per-instance confidence intervals or paired tests across the 100 trials, and define 'hard' and 'easy' in terms of a statistically meaningful separation rather than a point-wise median. Without this, the benchmark instances cannot support comparative claims about algorithm behavior.
minor comments (4)
  1. [§5.2, 'RQAOA as a high-performing heuristic'] The threshold of 0.96 is selected after reporting that 0.95 and 0.98 were discarded and 0.97 gives results comparable or better in some settings. This post-hoc threshold selection should be explicitly disclosed, and the reported balanced accuracies should be framed as exploratory rather than as a confirmatory evaluation.
  2. [Fig. 4 caption] The caption states that lower values indicate cases where one algorithm significantly outperforms the other, but the color bar is not defined. Please specify exactly which ratio is plotted (p_GW/p_RQAOA or p_RQAOA/p_GW) and the direction of the color scale.
  3. [§2, Fig. 1 description] The statement that the visualization offers 'an intuitive look at the way RQAOA navigates the solution space' is presented without quantitative support; consider citing the corresponding iteration costs or expectation values, or moving the interpretative sentence to the discussion.
  4. [Appendix D/E tables] Several importance scores have negative values (e.g., EXPECTED_COSTGW_OVER_SDP_COST in Table A3). A brief explanation of what negative permutation importance means in this context would help readers interpret the tables.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the optimization objective is the reported ratio, and the feature analysis is descriptive rather than a prediction forced by construction.

full rationale

The paper's derivation chain is self-contained: a PIGVAE graph autoencoder is trained on standard random graph generators, CMA-ES searches its latent space to maximize the explicitly stated objective p_GW(I)/p_RQAOA or its inverse (Eq. 1), and the decoded graphs are reported as the resulting instances. The central claim that the method 'pinpoints' instances with contrasting RQAOA/GW performance is a direct property of the optimizer: the fitness function is exactly the ratio whose extremes are reported, so there is no hidden reuse of the output as an input. The feature-analysis component is also not circular by construction. The label used for classification is whether p_GW exceeds p_RQAOA, while the most important feature, EXPECTED_COSTGW_OVER_SDP_COST, is defined in Appendix B as GW's average cost over 1,000 random trials normalized by the SDP bound; it does not contain the RQAOA denominator of Eq. (1), so the classifier is not reading the label directly from the feature. The paper does not rely on a load-bearing self-citation: reference [49] supports the standard fact that depth-1 RQAOA is classically simulable in O(n^4), which is externally checkable and not the paper's claimed contribution. Two empirical concerns are real but not circularity: the 100-node GAE link-prediction ROC-AUC of 0.611 is low, and the evolved ratio distributions are not compared against random-graph or random-latent baselines, so the 'hard instances' could partly reflect optimizer selection on noise. These are validity and experimental-design issues, not reductions of the derivation to its own inputs.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central method does not introduce physical entities or new fitted constants; its main free parameters are algorithm and threshold choices. The load-bearing assumptions are about the latent-space representation and the extrapolation from depth-1 RQAOA to RQAOA.

free parameters (5)
  • performance threshold for RQAOA high-performing heuristic = 0.96 (primary); 0.97 (alternate)
    Chosen after 0.95 and 0.98 were discarded because they produced degenerate label sets; the choice is data-dependent.
  • RQAOA recursion cutoff n_c = 10 for 20-node graphs; 20 for 100-node graphs
    Chosen as O(1) small; affects the depth of recursion and therefore the resulting performance.
  • stochastic trials per fitness evaluation = 100
    Median of 100 runs for each algorithm; no variance or significance statistics are reported for the ratios.
  • CMA-ES population size = 64
    Fixed choice from pycma; not varied or justified.
  • PIGVAE latent dimension = 64
    Taken from the reference implementation [58]; not validated for this task.
assumptions (4)
  • standard math Semidefinite programming relaxation of MaxCut and the GW 0.878 approximation guarantee
    Used as the classical baseline in Section 2.
  • domain assumption The trained PIGVAE latent space is smooth and dense enough for CMA-ES to find valid graphs
    This is the core search-space assumption in Section 4; Fig. 3 is offered as evidence but link-prediction AUC for 100-node graphs is low.
  • domain assumption Depth-1 RQAOA behavior is representative of RQAOA more generally
    The paper only simulates depth-1 RQAOA and states the connection to higher depths is 'less clear' (Section 2), yet the conclusions are framed about RQAOA.
  • domain assumption The six random graph models used for GAE training cover the space of relevant maximum-cut instances
    The generated instances are constrained to the latent space learned from these generators (Section 5.1).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms." pith.science (2026). https://pith.science/paper/56CK22RN

@misc{pith2026250212012,
  author       = {Pith},
  title        = {Pith review of: Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/56CK22RN}},
  note         = {Machine review of arXiv:2502.12012}
}
read the original abstract

Variational quantum algorithms, such as the Recursive Quantum Approximate Optimization Algorithm (RQAOA), have become increasingly popular, offering promising avenues for employing Noisy Intermediate-Scale Quantum devices to address challenging combinatorial optimization tasks like the maximum cut problem. In this study, we utilize an evolutionary algorithm equipped with a unique fitness function. This approach targets hard maximum cut instances within the latent space of a Graph Autoencoder, identifying those that pose significant challenges or are particularly tractable for RQAOA, in contrast to the classic Goemans and Williamson algorithm. Our findings not only delineate the distinct capabilities and limitations of each algorithm but also expand our understanding of RQAOA's operational limits. Furthermore, the diverse set of graphs we have generated serves as a crucial benchmarking asset, emphasizing the need for more advanced algorithms to tackle combinatorial optimization challenges. Additionally, our results pave the way for new avenues in graph generation research, offering exciting opportunities for future explorations.

Figures

Figures reproduced from arXiv: 2502.12012 by the authors.

Figure 1
Figure 1. RQAOA decision process (𝑛𝑐 = 10) across the first four iterations on a 20-node maximum cut instance, where it surpasses the GW algorithm. Each subpanel represents one algorithm iteration, with nodes as blue dots and edges as grey lines. Edge labels show the expectation values derived from the quantum Hamiltonian (the quantum analog of the maximum cut cost function). At each step, the edge with the largest absolute e… view at source ↗
Figure 2
Figure 2. Overview of the instance generation and evaluation [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Log-transformed second-largest eigenvalues of the [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Computed features of generated 20-node (top) and [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Partial dependence plots showing the classifier’s [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

64 extracted references · 32 canonical work pages

  1. [1]

    Saba Sadeghi Ahouei, Jacob de Nobel, Aneta Neumann, Thomas Bäck, and Frank Neumann. 2024. Evolving Reliable Differentiating Constraints for the Chance- constrained Maximum Coverage Problem. InProceedings of the Genetic and Evolutionary Computation Conference, GECCO 2024, Melbourne, VIC, Australia, July 14-18, 2024, Xiaodong Li and Julia Handl (Eds.). ACM....

    doi:10.1145/3638529 2024

  2. [2]

    Eunok Bae and Soojoon Lee. 2024. Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs.Quantum Information Processing23, 3 (2024), 78. doi:10.1007/S11128-024-04286-0

    work page doi:10.1007/s11128-024-04286-0 2024

  3. [3]

    Balabhaskar Balasundaram and Sergiy Butenko. 2005. Constructing test func- tions for global optimization using continuous formulations of graph prob- lems.Optimization Methods and Software20, 4-5 (2005), 439–452. doi:10.1080/ 10556780500139641

    work page 2005

  4. [4]

    Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks.Science286, 5439 (1999), 509–512

    1999

  5. [5]

    Boaz Barak and Kunal Marwaha. 2022. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In13th Innovations in Theoretical Computer Science Conference, ITCS 2022 (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14:1–14:21

    work page 2022

  6. [6]

    Malan, Jason H

    Thomas Bartz-Beielstein, Carola Doerr, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, Manuel López-Ibáñez, Kather- ine M. Malan, Jason H. Moore, Boris Naujoks, Patryk Orzechowski, Vanessa Volz, Markus Wagner, and Thomas Weise. 2020. Benchmarking in Optimization: Best Practice and Open Issues.CoRRabs/2007.03488 (2020...

    arXiv 2020

  7. [7]

    Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. 2019. Pa- rameterized quantum circuits as machine learning models.Quantum Science and Technology4, 4 (2019), 043001

    work page 2019

  8. [8]

    Steven J Benson, Yinyu Yeb, and Xiong Zhang. 1999. Mixed linear and semidefi- nite programming for combinatorial and quadratic optimization.Optimization Methods and Software11, 1-4 (1999), 515–544

    work page 1999

Show all 64 references
  1. [9]

    Xavier Bonet-Monroig, Hao Wang, Diederick Vermetten, Bruno Senjean, Charles Moussa, Thomas Bäck, Vedran Dunjko, and Thomas E O’Brien. 2023. Performance comparison of optimization methods on variational quantum algorithms.Physical Review A107, 3 (2023), 032407

    2023

  2. [10]

    Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neu- mann, and Heike Trautmann. 2019. Evolving diverse TSP instances by means of novel and creative mutation operators. InProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA...

    2019

  3. [11]

    Sergey Bravyi, David Gosset, and Daniel Grier. 2021. Classical algorithms for Forrelation.arXiv preprint arXiv:2102.06963(2021)

    2021 arXiv

  4. [12]

    Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 2020. Obsta- cles to variational quantum optimization from symmetry protection.Physical review letters125, 26 (2020), 260505

    2020

  5. [13]

    Sergey Bravyi, Alexander Kliesch, Robert König, and Eugene Tang. 2022. Hybrid quantum-classical algorithms for approximate graph coloring.Quantum6 (2022),

    2022

  6. [14]

    Kay Henning Brodersen, Cheng Soon Ong, Klaas Enno Stephan, and Joachim M. Buhmann. 2010. The Balanced Accuracy and Its Posterior Distribution. In20th International Conference on Pattern Recognition, ICPR 2010. IEEE Computer Society, 3121–3124. doi:10.1109/ICPR.2010.764

    2010 doi

  7. [15]

    Samuel Burer and Renato DC Monteiro. 2001. A projected gradient algorithm for solving the maxcut SDP relaxation.Optimization methods and Software15, 3-4 (2001), 175–200

    2001

  8. [16]

    Samuel Burer, Renato D. C. Monteiro, and Yin Zhang. 2002. Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs.SIAM Journal on Optimization12, 2 (2002), 503–521. doi:10.1137/S1052623400382467

    2002 doi

  9. [17]

    Iain Dunning, Swati Gupta, and John Silberholz. 2018. What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO.INFORMS Journal on Computing30, 3 (2018), 608–624. doi:10.1287/IJOC.2017.0798

    2018

  10. [18]

    Paul Erdos and Alfréd Rényi. 1960. On the evolution of random graphs.Publica- tions of the Mathematical Institute of the Hungarian Academy of Sciences5 (1960), 17–61

    1960

  11. [19]

    Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A Density- Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. InProceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, Orego...

    1996

  12. [20]

    Edward Farhi, David Gamarnik, and Sam Gutmann. 2020. The Quantum Approx- imate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. CoRRabs/2004.09002 (2020). arXiv:2004.09002 https://arxiv.org/abs/2004.09002

    2020 arXiv

  13. [21]

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approxi- mate optimization algorithm.arXiv preprint arXiv:1411.4028(2014)

    2014 arXiv

  14. [22]

    Wanru Gao, Samadhi Nallaperuma, and Frank Neumann. 2021. Feature-Based Diversity Optimization for Problem Instance Classification.Evolutionary Compu- tation29, 1 (2021), 107–128. doi:10.1162/EVCO_A_00274

    2021 doi

  15. [23]

    Pierre Geurts, Damien Ernst, and Louis Wehenkel. 2006. Extremely randomized trees.Machine learning63, 1 (2006), 3–42. doi:10.1007/S10994-006-6226-1

    2006 doi

  16. [24]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. 1995. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.Journal of the ACM (JACM)42, 6 (1995), 1115–1145. doi:10.1145/ 227683.227684

    1995

  17. [25]

    Nikolaus Hansen. 2006. The CMA Evolution Strategy: A Comparing Review. In Towards a New Evolutionary Computation - Advances in the Estimation of Distri- bution Algorithms. Studies in Fuzziness and Soft Computing, Vol. 192. Springer, 75–102. doi:10.1007/3-540-32494-1_4

    2006 doi

  18. [26]

    Nikolaus Hansen. 2016. The CMA Evolution Strategy: A Tutorial.CoRR abs/1604.00772 (2016). arXiv:1604.00772 http://arxiv.org/abs/1604.00772

    2016 arXiv

  19. [27]

    Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. 2019. CMA-ES/pycma on Github. Zenodo, DOI:10.5281/zenodo.2559634. doi:10.5281/zenodo.2559634

    2019 doi

  20. [28]

    Müller, and Petros Koumoutsakos

    Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. 2003. Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES).Evolutionary Computation11, 1 (2003), 1–18. doi:10.1162/106365603321828970

    2003 doi

  21. [29]

    Nikolaus Hansen, André S. P. Niederberger, Lino Guzzella, and Petros Koumout- sakos. 2009. A Method for Handling Uncertainty in Evolutionary Optimization With an Application to Feedback Control of Combustion.IEEE Transactions on Evolutionary Computation13, 1 (2009), 180–197. d...

    2009

  22. [30]

    Nikolaus Hansen and Andreas Ostermeier. 2001. Completely Derandomized Self-Adaptation in Evolution Strategies.Evolutionary Computation9, 2 (2001), 159–195. doi:10.1162/106365601750190398

    2001 doi

  23. [31]

    Hastings

    Matthew B. Hastings. 2019. Classical and quantum bounded depth approximation algorithms.Quantum Information & Computation19, 13&14 (2019), 1116–1140. doi:10.26421/QIC19.13-14-3

    2019 doi

  24. [32]

    Christoph Helmberg and Franz Rendl. 2000. A Spectral Bundle Method for Semidefinite Programming.SIAM Journal on Optimization10, 3 (2000), 673–696. doi:10.1137/S1052623497328987

    2000 doi

  25. [33]

    Yu, and Ming Zhang

    Wei Ju, Siyu Yi, Yifan Wang, Zhiping Xiao, Zhengyang Mao, Hourun Li, Yiyang Gu, Yifang Qin, Nan Yin, Senzhang Wang, Xinwang Liu, Xiao Luo, Philip S. Yu, and Ming Zhang. 2024. A Survey of Graph Neural Networks in Real World: Imbalance, Noise, Privacy and OOD Challenges.CoRRabs/...

    2024 doi

  26. [34]

    Kingma and Max Welling

    Diederik P. Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes. In2nd International Conference on Learning Representations, ICLR 2014. http: //arxiv.org/abs/1312.6114

    2014 arXiv

  27. [35]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2016. Variational Graph Auto-Encoders.CoRR abs/1611.07308 (2016). https://dblp.org/rec/journals/corr/KipfW16a

    2016 arXiv

  28. [36]

    Ker-I Ko, Pekka Orponen, Uwe Schöning, and Osamu Watanabe. 1986. What Is a Hard Instance of a Computational Problem?. InStructure in Complexity Theory, Proceedings of the Conference hold at the University of California, Berkeley, California, USA, June 2-5, 1986 (Lecture Notes ...

    1986 doi

  29. [37]

    Ilya Loshchilov and Frank Hutter. 2016. CMA-ES for Hyperparameter Optimiza- tion of Deep Neural Networks.CoRRabs/1604.07269 (2016). arXiv:1604.07269 http://arxiv.org/abs/1604.07269

    2016 arXiv

  30. [38]

    Alejandro Marrero, Eduardo Segredo, Emma Hart, Jakob Bossek, and Aneta Neumann. 2023. Generating diverse and discriminatory knapsack instances by searching for novelty in variable dimensions of feature-space. InProceedings of the Genetic and Evolutionary Computation Conference...

    2023

  31. [39]

    Kunal Marwaha. 2021. Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs.Quantum5 (2021), 437. doi:10.22331/Q- 2021-04-20-437

    2021 doi

  32. [40]

    Alexey A Melnikov, Leonid E Fedichkin, and Alexander Alodjants. 2019. Predict- ing quantum advantage by quantum walk with convolutional neural networks. New Journal of Physics21, 12 (2019), 125002

    2019

  33. [41]

    Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al. 2018. Quantum optimization using variational algorithms on near-term quantum devices.Quantum Science and Technolo...

    2018

  34. [42]

    Niema Moshiri. 2018. The dual-Barabási-Albert model.arXiv preprint arXiv:1810.10538(2018). GECCO ’25, July 14–18, 2025, Malaga, Spain Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang

    2018 arXiv

  35. [43]

    Charles Moussa, Henri Calandra, and Vedran Dunjko. 2020. To quantum or not to quantum: towards algorithm selection in near-term quantum optimization. Quantum Science and Technology5, 4 (2020), 044009

    2020

  36. [44]

    Aneta Neumann, Wanru Gao, Markus Wagner, and Frank Neumann. 2019. Evo- lutionary diversity optimization using multi-objective indicators. InProceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019. ACM, 837–845. doi:10.1145/3321707.3321796

    2019

  37. [45]

    Mark EJ Newman and Duncan J Watts. 1999. Renormalization group analysis of the small-world network model.Physics Letters A263, 4-6 (1999), 341–346

    1999

  38. [46]

    Olson, Nathan Bartley, Ryan J

    Randal S. Olson, Nathan Bartley, Ryan J. Urbanowicz, and Jason H. Moore. 2016. Evaluation of a Tree-based Pipeline Optimization Tool for Automating Data Science. InProceedings of the 2016 on Genetic and Evolutionary Computation Conference. ACM, 485–492. doi:10.1145/2908812.2908918

    2016

  39. [47]

    Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang

    Shuaiqun Pan, Yash J. Patel, Aneta Neumann, Frank Neumann, Thomas Bäck, and Hao Wang. 2025. Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms: Supplementary Material. https://doi.org/ 10.5281/zenodo.14757739

    2025 doi

  40. [48]

    Papadimitriou and Mihalis Yannakakis

    Christos H. Papadimitriou and Mihalis Yannakakis. 1991. Optimization, Approx- imation, and Complexity Classes.J. Comput. System Sci.43, 3 (1991), 425–440. doi:10.1016/0022-0000(91)90023-X

    1991 doi

  41. [49]

    Yash J Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko. 2024. Reinforcement learning assisted recursive QAOA.EPJ Quantum Technology11, 1 (2024), 6

    2024

  42. [50]

    Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake VanderPlas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesna...

    2011

  43. [51]

    John Preskill. 2018. Quantum Computing in the NISQ era and beyond.Quantum 2 (2018), 79. doi:10.22331/Q-2018-08-06-79

    2018 doi

  44. [52]

    Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. 2017. Evolution Strate- gies as a Scalable Alternative to Reinforcement Learning.CoRRabs/1703.03864 (2017). arXiv:1703.03864 http://arxiv.org/abs/1703.03864

    2017 arXiv

  45. [53]

    Erich Schubert, Jörg Sander, Martin Ester, Hans-Peter Kriegel, and Xiaowei Xu. 2017. DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN.ACM Trans. Database Syst.42, 3 (2017), 19:1–19:21. doi:10.1145/3068335

    2017 doi

  46. [54]

    Sutherland, and Ali Kemal Sinop

    Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. 2023. Exphormer: Sparse Transformers for Graphs. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Hon- olulu, Hawaii, USA (Proceedings of Machine Learni...

    2023

  47. [55]

    Martin Simonovsky and Nikos Komodakis. 2018. GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders. InArtificial Neural Networks and Machine Learning - ICANN 2018 - 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, ...

    2018

  48. [56]

    Angelika Steger and Nicholas C. Wormald. 1999. Generating Random Regular Graphs Quickly.Combinatorics, Probability and Computing8, 4 (1999), 377–396. http://journals.cambridge.org/action/displayAbstract?aid=46711

    1999

  49. [57]

    Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ‘small- world’networks.Nature393, 6684 (1998), 440–442

    1998

  50. [58]

    Robin Winter, Frank Noé, and Djork-Arné Clevert. 2021. Permutation- Invariant Variational Autoencoder for Graph-Level Representation Learning. InAdvances in Neural Information Processing Systems 34: An- nual Conference on Neural Information Processing Systems 2021, NeurIPS

    2021

  51. [59]

    Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks.IEEE Trans. Neural Networks Learn. Syst.32, 1 (2021), 4–24. doi:10.1109/TNNLS.2020. 2978386

    2021 doi

  52. [60]

    Hamilton, and Jure Leskovec

    Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. 2018. GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July...

    2018

  53. [61]

    Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. 2022. A Survey on Deep Graph Generation: Methods and Applications. InLearning on Graphs Conference, LoG 2022, 9-12 December 2022, Virtual Event (Proceedings of Machine Learning Research, Vol. 1...

    2022

  54. [422]

    doi:10.1007/978-3-030-01418-6_41

    doi

  55. [678]

    doi:10.22331/Q-2022-03-30-678

    2022 doi

  56. [2021]

    https://proceedings.neurips.cc/paper/2021/hash/ 4f3d7d38d24b740c95da2b03dc3a2333-Abstract.html

    9559–9573. https://proceedings.neurips.cc/paper/2021/hash/ 4f3d7d38d24b740c95da2b03dc3a2333-Abstract.html

    2021

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.