{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T03:14:11Z","timestamp":1769742851367,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","funder":[{"name":"University of Malaga","award":["PAR 4\/2023"],"award-info":[{"award-number":["PAR 4\/2023"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,14]]},"DOI":"10.1145\/3712255.3734319","type":"proceedings-article","created":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T15:14:02Z","timestamp":1754925242000},"page":"2403-2411","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1259-2990","authenticated-orcid":false,"given":"Francisco","family":"Chicano","sequence":"first","affiliation":[{"name":"ITIS Software, University of Malaga, Malaga, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8022-4407","authenticated-orcid":false,"given":"Zakaria Abdelmoiz","family":"Dahi","sequence":"additional","affiliation":[{"name":"Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7909-1416","authenticated-orcid":false,"given":"Gabriel","family":"Luque","sequence":"additional","affiliation":[{"name":"ITIS Software, University of Malaga, Malaga, Spain"}]}],"member":"320","published-online":{"date-parts":[[2025,8,11]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_2_2_2_1","volume-title":"Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR abs\/1505.03424","author":"Barak B.","year":"2015","unstructured":"Barak, B., Moitra, A., O'Donnell, R., Raghavendra, P., Regev, O., Steurer, D., Trevisan, L., Vijayaraghavan, A., Witmer, D., and Wright, J. Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR abs\/1505.03424 (2015)."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796425"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2024.03.002"},{"key":"e_1_3_2_2_7_1","volume-title":"Solving boolean satisfiability problems with the quantum approximate optimization algorithm. PRX Quantum 5 (9","author":"Boulebnane S.","year":"2024","unstructured":"Boulebnane, S., and Montanaro, A. Solving boolean satisfiability problems with the quantum approximate optimization algorithm. PRX Quantum 5 (9 2024), 030348."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","unstructured":"Chicano F. Dahi Z. A. and Luqe G. Supplementary material of the paper entitled \"The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions\" published in the Quantum Optimization Workshop at GECCO 2025 2025. 10.5281\/zenodo.15319951","DOI":"10.5281\/zenodo.15319951"},{"key":"e_1_3_2_2_9_1","volume-title":"PPSN 2024, Hagenberg, Austria, September 14\u201318, 2024, Proceedings, Part I","volume":"15148","author":"Chicano F.","year":"2024","unstructured":"Chicano, F., Whitley, D., Ochoa, G., and Tin\u00f3s, R. Generalizing and unifying gray-box combinatorial optimization operators. In Parallel Problem Solving from Nature - PPSN XVIII - 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14\u201318, 2024, Proceedings, Part I (2024), M. Affenzeller, S. M. Winkler, A. V. Kononova, H. Trautmann, T. Tu\u0161ar, P. Machado, and T. B\u00e4ck, Eds., vol. 15148 of Lecture Notes in Computer Science, Springer, pp. 52\u201367."},{"key":"e_1_3_2_2_10_1","first-page":"553","article-title":"Rapid solution of problems by quantum computation","volume":"439","author":"Deutsch D.","year":"1907","unstructured":"Deutsch, D., and Jozsa, R. Rapid solution of problems by quantum computation. Proceedings of the Royal Society A 439, 1907 (1992), 553\u2013558.","journal-title":"Proceedings of the Royal Society A"},{"key":"e_1_3_2_2_11_1","unstructured":"Eickbusch A. McEwen M. Sivak V. Bourassa A. Atalaya J. Claes J. Kafri D. Gidney C. Warren C. W. Gross J. Opremcak A. Miao N. Z. K. C. Roberts G. Satzinger K. J. Bengtsson A. Neeley M. Livingston W. P. Greene A. Rajeev Acharya Beni L. A. Aigeldinger G. Alcaraz R. Andersen T. I. Ansmann M. Frank Arute Arya K. Asfaw A. Babbush R. Ballard B. Bardin J. C. Bilmes A. Jenna Bovaird Bowers D. Brill L. Broughton M. Browne D. A. Buchea B. Buckley B. B. Tim Burger Burkett B. Bushnell N. Cabrera A. Campero J. Chang H.-S. Chiaro B. Chih L.-Y. Cleland A. Y. Cogan J. Collins R. Conner P. Courtney W. Alexander Crook L. Curtin B. Das S. Barba A. D. T. Demura S. Lorenzo L. D. Paolo A. D. Donohoe P. Drozdov I. K. Dunsworth A. Elbag A. M. Elzouka M. Erickson C. Ferreira V. S. Burgos L. F. Forati E. Fowler A. G. Foxen B. Ganjam S. Gonzalo Garcia Gasca R. \u00c9lie Genois Giang W. Gilboa D. Gosula R. Dau A. G. Dietrich Graumann Ha T. Habegger S. Hansen M. Harrigan M. P. Harrington S. D. Heslin S. Heu P. Higgott O. Hiltermann R. Hilton J. Huang H.-Y. Huff A. Huggins W. J. Jeffrey E. Jiang Z. Jin X. Jones C. Joshi C. Juhas P. Kabel A. Kang H. Amir Karamlou H. Kechedzhi K. Khaire T. Khattar T. Khezri M. Kim S. Kobrin B. Korotkov A. N. Kostritsa F. Kreikebaum J. M. Kurilovich V. D. Landhuis D. Tiano Lange-Dei Langley B. W. Lau K.-M. Ledford J. Lee K. Lester B. J. Guevel L. L. Wing Li Y. Lill A. T. Locharla A. Lucero E. Lundahl D. Lunt A. Madhuk S. Maloney A. Mandr\u00e0 S. Martin L. S. Martin O. Maxfield C. McClean J. R. Meeks S. Anthony Megrant Molavi R. Molina S. Montazeri S. Movassagh R. Newman M. Nguyen A. Nguyen M. Ni C.-H. Oas L. Orosco R. Ottosson K. Pizzuto A. Potter R. Pritchard O. Quintana C. Ramachandran G. Reagor M. J. Rhodes D. M. Rosenberg E. Rossi E. Sankaragomathi K. Schurkus H. F. Shearn M. J. Shorter A. Shutty N. Shvarts V. Small S. Smith W. C. Springer S. Sterling G. Suchard J. Szasz A. Sztein A. Thor D. Tomita E. Torres A. Torunbalci M. M. Vaishnav A. Vargas J. Sergey Vdovichev Vidal G. Heidweiller C. V. Waltman S. Waltz J. Wang S. X. Ware B. Weidel T. White T. Wong K. Woo B. W. K. Woodson M. Xing C. Yao Z. J. Yeh P. Ying B. Yoo J. Yosri N. Young G. Zalcman A. Yaxing Zhang Zhu N. Boixo S. Kelly J. Smelyanskiy V. Neven H. Bacon D. Chen Z. Klimov P. V. Roushan P. Neill C. Chen Y. and Morvan A. Demonstrating dynamic surface codes 2024. arXiv:2412.14360."},{"key":"e_1_3_2_2_12_1","volume-title":"A quantum approximate optimization algorithm","author":"Farhi E.","year":"2014","unstructured":"Farhi, E., Goldstone, J., and Gutmann, S. A quantum approximate optimization algorithm, 2014. arXiv:1411.4028."},{"key":"e_1_3_2_2_13_1","volume-title":"Quantum supremacy through the quantum approximate optimization algorithm","author":"Farhi E.","year":"2019","unstructured":"Farhi, E., and Harrow, A. W. Quantum supremacy through the quantum approximate optimization algorithm, 2019. arXiv:1602.07674."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.140502"},{"key":"e_1_3_2_2_16_1","volume-title":"Supervised learning with quantum-enhanced feature spaces. Nature 567, 7747 (March","author":"Havl\u00ed\u010dek V.","year":"2019","unstructured":"Havl\u00ed\u010dek, V., C\u00f3rcoles, A. D., Temme, K., Harrow, A. W., Kandala, A., Chow, J. M., and Gambetta, J. M. Supervised learning with quantum-enhanced feature spaces. Nature 567, 7747 (March 2019), 209\u2013212."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3571725"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.82"},{"key":"e_1_3_2_2_19_1","first-page":"156","volume-title":"Gaussian elimination and resolution of systems of algebraic equations. In Computer Algebra (Berlin","author":"Lazard D.","year":"1983","unstructured":"Lazard, D. Gr\u00f6bner bases, Gaussian elimination and resolution of systems of algebraic equations. In Computer Algebra (Berlin, Heidelberg, 1983), J. A. van Hulzen, Ed., Springer Berlin Heidelberg, pp. 146\u2013156."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a015"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-14721-0_38"},{"key":"e_1_3_2_2_22_1","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M. A.","year":"2000","unstructured":"Nielsen, M. A., and Chuang, I. L. Quantum Computation and Quantum Information. Cambridge University Press, 2000."},{"key":"e_1_3_2_2_23_1","volume-title":"A variational eigenvalue solver on a photonic quantum processor. Nature communications 5","author":"Peruzzo A.","year":"2014","unstructured":"Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., and O'Brien, J. L. A variational eigenvalue solver on a photonic quantum processor. Nature communications 5 (2014), 4213:1\u20137."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2725494.2725497"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.10.021067"}],"event":{"name":"GECCO '25 Companion: Genetic and Evolutionary Computation Conference Companion","location":"NH Malaga Hotel Malaga Spain","acronym":"GECCO '25 Companion","sponsor":["SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation"]},"container-title":["Proceedings of the Genetic and Evolutionary Computation Conference Companion"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3712255.3734319","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T11:44:20Z","timestamp":1759837460000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712255.3734319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,14]]},"references-count":26,"alternative-id":["10.1145\/3712255.3734319","10.1145\/3712255"],"URL":"https:\/\/doi.org\/10.1145\/3712255.3734319","relation":{},"subject":[],"published":{"date-parts":[[2025,7,14]]},"assertion":[{"value":"2025-08-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}