{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T21:10:16Z","timestamp":1759871416541,"version":"build-2065373602"},"publisher-location":"New York, NY, USA","reference-count":61,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,14]]},"DOI":"10.1145\/3712256.3726415","type":"proceedings-article","created":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T12:28:18Z","timestamp":1751977698000},"page":"443-452","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7039-4875","authenticated-orcid":false,"given":"Shuaiqun","family":"Pan","sequence":"first","affiliation":[{"name":"Leiden University, LIACS, Leiden, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3060-6950","authenticated-orcid":false,"given":"Yash J.","family":"Patel","sequence":"additional","affiliation":[{"name":"Leiden University, LIACS, Leiden, Netherlands"},{"name":"Leiden University, applied Quantum algorithms, Leiden, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0036-4782","authenticated-orcid":false,"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[{"name":"The University of Adelaide, Optimisation and Logistics School of Computer and Mathematical Sciences, Adelaide, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"The University of Adelaide, Optimisation and Logistics School of Computer and Mathematical Sciences, Adelaide, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6768-1478","authenticated-orcid":false,"given":"Thomas","family":"B\u00e4ck","sequence":"additional","affiliation":[{"name":"Leiden University, LIACS, Leiden, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4933-5181","authenticated-orcid":false,"given":"Hao","family":"Wang","sequence":"additional","affiliation":[{"name":"Leiden University, LIACS, Leiden, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2025,7,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3638529.3654181"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11128-024-04286-0"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780500139641"},{"key":"e_1_3_2_1_4_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509\u2013512."},{"key":"e_1_3_2_1_5_1","volume-title":"Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 (LIPIcs","volume":"21","author":"Barak Boaz","year":"2022","unstructured":"Boaz Barak and Kunal Marwaha. 2022. Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. In 13th Innovations in Theoretical Computer Science Conference, ITCS 2022 (LIPIcs, Vol. 215). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 14:1\u201314:21."},{"key":"e_1_3_2_1_6_1","volume-title":"Benchmarking in Optimization: Best Practice and Open Issues. CoRR abs\/2007.03488","author":"Bartz-Beielstein Thomas","year":"2020","unstructured":"Thomas Bartz-Beielstein, Carola Doerr, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, Manuel L\u00f3pez-Ib\u00e1\u00f1ez, Katherine 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. CoRR abs\/2007.03488 (2020). arXiv:2007.03488 https:\/\/arxiv.org\/abs\/2007.03488"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab4eb5"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805761"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.107.032407"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299904.3340307"},{"key":"e_1_3_2_1_11_1","volume-title":"Classical algorithms for Forrelation. arXiv preprint arXiv:2102.06963","author":"Bravyi Sergey","year":"2021","unstructured":"Sergey Bravyi, David Gosset, and Daniel Grier. 2021. Classical algorithms for Forrelation. arXiv preprint arXiv:2102.06963 (2021)."},{"key":"e_1_3_2_1_12_1","volume-title":"Obstacles to variational quantum optimization from symmetry protection. Physical review letters 125, 26","author":"Bravyi Sergey","year":"2020","unstructured":"Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 2020. Obstacles to variational quantum optimization from symmetry protection. Physical review letters 125, 26 (2020), 260505."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.22331\/Q-2022-03-30-678"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.2010.764"},{"key":"e_1_3_2_1_15_1","volume-title":"A projected gradient algorithm for solving the maxcut SDP relaxation. Optimization methods and Software 15, 3\u20134","author":"Burer Samuel","year":"2001","unstructured":"Samuel Burer and Renato DC Monteiro. 2001. A projected gradient algorithm for solving the maxcut SDP relaxation. Optimization methods and Software 15, 3\u20134 (2001), 175\u2013200."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400382467"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/IJOC.2017.0798"},{"key":"e_1_3_2_1_18_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos Paul","year":"1960","unstructured":"Paul Erdos and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17\u201361.","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3001460.3001507"},{"key":"e_1_3_2_1_20_1","volume-title":"The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. CoRR abs\/2004.09002","author":"Farhi Edward","year":"2020","unstructured":"Edward Farhi, David Gamarnik, and Sam Gutmann. 2020. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. CoRR abs\/2004.09002 (2020). arXiv:2004.09002 https:\/\/arxiv.org\/abs\/2004.09002"},{"key":"e_1_3_2_1_21_1","volume-title":"A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028","author":"Farhi Edward","year":"2014","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_A_00274"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10994-006-6226-1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-32494-1_4"},{"key":"e_1_3_2_1_26_1","volume-title":"The CMA Evolution Strategy: A Tutorial. CoRR abs\/1604.00772","author":"Hansen Nikolaus","year":"2016","unstructured":"Nikolaus Hansen. 2016. The CMA Evolution Strategy: A Tutorial. CoRR abs\/1604.00772 (2016). arXiv:1604.00772 http:\/\/arxiv.org\/abs\/1604.00772"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Nikolaus Hansen Youhei Akimoto and Petr Baudis. 2019. CMA-ES\/pycma on Github. Zenodo https:\/\/doi.org\/10.5281\/zenodo.2559634 10.5281\/zenodo.2559634","DOI":"10.5281\/zenodo.2559634"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365603321828970"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2008.924423"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365601750190398"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC19.13-14-3"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328987"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2403.04468"},{"key":"e_1_3_2_1_34_1","volume-title":"Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR","author":"Diederik","year":"2014","unstructured":"Diederik P. Kingma and Max Welling. 2014. Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014. http:\/\/arxiv.org\/abs\/1312.6114"},{"key":"e_1_3_2_1_35_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2016","unstructured":"Thomas N. Kipf and Max Welling. 2016. Variational Graph Auto-Encoders. CoRR abs\/1611.07308 (2016). https:\/\/dblp.org\/rec\/journals\/corr\/KipfW16a"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16486-3_99"},{"key":"e_1_3_2_1_37_1","volume-title":"CMA-ES for Hyperparameter Optimization of Deep Neural Networks. CoRR abs\/1604.07269","author":"Loshchilov Ilya","year":"2016","unstructured":"Ilya Loshchilov and Frank Hutter. 2016. CMA-ES for Hyperparameter Optimization of Deep Neural Networks. CoRR abs\/1604.07269 (2016). arXiv:1604.07269 http:\/\/arxiv.org\/abs\/1604.07269"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583131.3590504"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.22331\/Q-2021-04-20-437"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/ab5c5e"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aab822"},{"key":"e_1_3_2_1_42_1","volume-title":"The dual-Barab\u00e1si-Albert model. arXiv preprint arXiv:1810.10538","author":"Moshiri Niema","year":"2018","unstructured":"Niema Moshiri. 2018. The dual-Barab\u00e1si-Albert model. arXiv preprint arXiv:1810.10538 (2018)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/abb8e5"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321707.3321796"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(99)00757-4"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908812.2908918"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","unstructured":"Shuaiqun Pan Yash J. Patel Aneta Neumann Frank Neumann Thomas B\u00e4ck and Hao Wang. 2025. Evolving Hard Maximum Cut Instances for Quantum Approximate Optimization Algorithms: Supplementary Material. 10.5281\/zenodo.14757739","DOI":"10.5281\/zenodo.14757739"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjqt\/s40507-023-00214-w"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.22331\/Q-2018-08-06-79"},{"key":"e_1_3_2_1_52_1","volume-title":"Evolution Strategies as a Scalable Alternative to Reinforcement Learning. CoRR abs\/1703.03864","author":"Salimans Tim","year":"2017","unstructured":"Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. 2017. Evolution Strategies as a Scalable Alternative to Reinforcement Learning. CoRR abs\/1703.03864 (2017). arXiv:1703.03864 http:\/\/arxiv.org\/abs\/1703.03864"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3068335"},{"key":"e_1_3_2_1_54_1","volume-title":"Exphormer: Sparse Transformers for Graphs. In International Conference on Machine Learning, ICML 2023","volume":"31632","author":"Shirzad Hamed","year":"2023","unstructured":"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\u201329 July 2023, Honolulu, Hawaii, USA (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.). PMLR, 31613\u201331632. https:\/\/proceedings.mlr.press\/v202\/shirzad23a.html"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01418-6_41"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003867"},{"key":"e_1_3_2_1_57_1","volume-title":"Collective dynamics of 'smallworld'networks. Nature 393, 6684","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'smallworld'networks. Nature 393, 6684 (1998), 440\u2013442."},{"key":"e_1_3_2_1_58_1","volume-title":"Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems","author":"Winter Robin","year":"2021","unstructured":"Robin Winter, Frank No\u00e9, and Djork-Arn\u00e9 Clevert. 2021. Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021. 9559\u20139573. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/4f3d7d38d24b740c95da2b03dc3a2333-Abstract.html"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_3_2_1_60_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"You Jiaxuan","year":"2018","unstructured":"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\u00e4ssan, Stockholm, Sweden, July 10\u201315, 2018 (Proceedings of Machine Learning Research, Vol. 80), Jennifer G. Dy and Andreas Krause (Eds.). PMLR, 5694\u20135703. http:\/\/proceedings.mlr.press\/v80\/you18a.html"},{"key":"e_1_3_2_1_61_1","volume-title":"Learning on Graphs Conference, LoG 2022","volume":"47","author":"Zhu Yanqiao","year":"2022","unstructured":"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. In Learning on Graphs Conference, LoG 2022, 9\u201312 December 2022, Virtual Event (Proceedings of Machine Learning Research, Vol. 198), Bastian Rieck and Razvan Pascanu (Eds.). PMLR, 47. https:\/\/proceedings.mlr.press\/v198\/zhu22a.html"}],"event":{"name":"GECCO '25: Genetic and Evolutionary Computation Conference","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"],"location":"NH Malaga Hotel Malaga Spain","acronym":"GECCO '25"},"container-title":["Proceedings of the Genetic and Evolutionary Computation Conference"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3712256.3726415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T20:42:08Z","timestamp":1759869728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712256.3726415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,13]]},"references-count":61,"alternative-id":["10.1145\/3712256.3726415","10.1145\/3712256"],"URL":"https:\/\/doi.org\/10.1145\/3712256.3726415","relation":{},"subject":[],"published":{"date-parts":[[2025,7,13]]},"assertion":[{"value":"2025-07-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}