{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T20:08:10Z","timestamp":1771618090904,"version":"3.50.1"},"reference-count":76,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T00:00:00Z","timestamp":1761091200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"\n We consider the maximum cut and maximum independent set problems on random regular graphs in the infinite-size limit, and calculate the energy densities achieved by QAOA for high degrees up to\n \n d<\/mml:mi>\n =<\/mml:mo>\n 100<\/mml:mn>\n <\/mml:math>\n . Such an analysis is possible because the reverse causal cones of the operators in the Hamiltonian are with high probability associated with tree subgraphs, for which efficient classical contraction schemes can be developed. We combine the QAOA analysis with state-of-the-art upper bounds on optimality for both problems. This yields novel and better bounds on the approximation ratios achieved by QAOA for large problem sizes. We show that the approximation ratios achieved by QAOA improve as the graph degree increases for the maximum cut problem. However, QAOA exhibits the opposite behavior for the maximum independent set problem, i.e. the achieved approximation ratios decrease when the degree of the problem is increased. This phenomenon is explainable by the overlap gap property for large\n \n d<\/mml:mi>\n <\/mml:math>\n , which restricts local algorithms (like QAOA) from reaching near-optimal solutions with high probability. In addition, we use the QAOA parameters determined on the tree subgraphs for small graph instances, and in that way outperform classical algorithms like Goemans-Williamson for the maximum cut problem and minimal greedy for the maximum independent set problem. In this way we circumvent the parameter optimization problem and are able to compute the expected approximation ratios.\n <\/jats:p>","DOI":"10.22331\/q-2025-10-22-1892","type":"journal-article","created":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T12:43:39Z","timestamp":1761137019000},"page":"1892","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm"],"prefix":"10.22331","volume":"9","author":[{"given":"Elisabeth","family":"Wybo","sequence":"first","affiliation":[{"name":"IQM Quantum Computers, Georg-Brauchle-Ring 23-25, 80992 M\u00fcnchen, Germany"}]},{"given":"Martin","family":"Leib","sequence":"additional","affiliation":[{"name":"IQM Quantum Computers, Georg-Brauchle-Ring 23-25, 80992 M\u00fcnchen, Germany"}]}],"member":"9598","published-online":{"date-parts":[[2025,10,22]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Richard P. Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467\u2013488 (1982).","DOI":"10.1007\/bf02650179"},{"key":"1","doi-asserted-by":"publisher","unstructured":"J. Ignacio Cirac and Peter Zoller. ``Goals and opportunities in quantum simulation''. Nature Physics 8, 264\u2013266 (2012).","DOI":"10.1038\/nphys2275"},{"key":"2","doi-asserted-by":"publisher","unstructured":"I. M. Georgescu, S. Ashhab, and Franco Nori. ``Quantum simulation''. Rev. Mod. Phys. 86, 153\u2013185 (2014).","DOI":"10.1103\/RevModPhys.86.153"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103, 150502 (2009).","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. ``A rigorous and robust quantum speed-up in supervised machine learning''. Nature Physics 17, 1013\u20131017 (2021).","DOI":"10.1038\/s41567-021-01287-z"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Information-theoretic bounds on quantum advantage in machine learning''. Phys. Rev. Lett. 126, 190505 (2021).","DOI":"10.1103\/PhysRevLett.126.190505"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert. ``On the Quantum versus Classical Learnability of Discrete Distributions''. Quantum 5, 417 (2021).","DOI":"10.22331\/q-2021-03-23-417"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Lov K. Grover. ``A Fast quantum mechanical algorithm for database search'' (1996). arXiv:quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas B\u00e4rtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O'Meara, Elena Pe\u00f1a Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Victor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal. ``Quantum optimization: Potential, challenges, and the path forward'' (2023). arXiv:2312.02279.","DOI":"10.1038\/s42254-024-00770-9"},{"key":"9","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018) 2, 79 (2018). arXiv:1801.00862.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"10","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028."},{"key":"11","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem'' (2014). arXiv:1412.6062."},{"key":"12","unstructured":"Edward Farhi and Aram W Harrow. ``Quantum supremacy through the quantum approximate optimization algorithm'' (2016). arXiv:1602.07674."},{"key":"13","doi-asserted-by":"publisher","unstructured":"Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. ``From the quantum approximate optimization algorithm to a quantum alternating operator ansatz''. Algorithms 12.2 (2019): 34. (Special issue \"Quantum Optimization Theory, Algorithms, and Applications\") 12, 34 (2017). arXiv:1709.03489.","DOI":"10.3390\/a12020034"},{"key":"14","unstructured":"Ehsan Zahedinejad and Arman Zaribafiyan. ``Combinatorial optimization on gate model quantum computers: A survey'' (2017). arXiv:1708.05294."},{"key":"15","doi-asserted-by":"publisher","unstructured":"Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. ``Quantum approximate optimization algorithm for maxcut: A fermionic view''. Phys. Rev. A 97, 022304 (2018).","DOI":"10.1103\/PhysRevA.97.022304"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Summer. ``A review on quantum approximate optimization algorithm and its variants''. Physics Reports 1068, 1\u201366 (2023). arXiv:2306.09198.","DOI":"10.1016\/j.physrep.2024.03.002"},{"key":"17","unstructured":"Eran Makover and Jeffrey McGowan. ``Regular trees in random regular graphs'' (2006)."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. ``The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model''. In Proceedings of the 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC '22), 7:1\u20137:21, (2022) (2021). arXiv:2110.14206.","DOI":"10.4230\/LIPICS.TQC.2022.7"},{"key":"19","unstructured":"Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. ``For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances'' (2018). arXiv:1812.04170."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Michael Streif and Martin Leib. ``Training the quantum approximate optimization algorithm without access to a quantum processing unit''. Quantum Science and Technology 5, 034008 (2020).","DOI":"10.1088\/2058-9565\/ab8c2b"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Jonathan Wurtz and Peter J. Love. ``Maxcut qaoa performance guarantees for p >1''. Phys. Rev. A 103, 042612 (2021) 103, 042612 (2020). arXiv:2010.11209.","DOI":"10.1103\/physreva.103.042612"},{"key":"22","doi-asserted-by":"crossref","unstructured":"Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. ``Transferability of optimal qaoa parameters between random graphs'' (2021). arXiv:2106.07531.","DOI":"10.1109\/QCE52317.2021.00034"},{"key":"23","doi-asserted-by":"crossref","unstructured":"Alexey Galda, Eesh Gupta, Jose Falla, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. ``Similarity-based parameter transferability in the quantum approximate optimization algorithm'' (2023). arXiv:2307.05420.","DOI":"10.3389\/frqst.2023.1200975"},{"key":"24","unstructured":"Gavin E. Crooks. ``Performance of the quantum approximate optimization algorithm on the maximum cut problem'' (2018). arXiv:1811.08419."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Jonathan Wurtz and Danylo Lykov. ``Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs''. Phys. Rev. A 104, 052419 (2021).","DOI":"10.1103\/PhysRevA.104.052419"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Michel X. Goemans and David P. Williamson. ``Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming''. Journal of the ACM 42, 1115\u20131145 (1995).","DOI":"10.1145\/227683.227684"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O\u2019Donnell. ``Optimal inapproximability results for max\u2010cut and other 2\u2010variable csps?''. SIAM Journal on Computing 37, 319\u2013357 (2007). arXiv:https:\/\/doi.org\/10.1137\/S0097539705447372.","DOI":"10.1137\/S0097539705447372"},{"key":"28","doi-asserted-by":"crossref","unstructured":"M. B. Hastings. ``Classical and quantum bounded depth approximation algorithms'' (2019). arXiv:1905.07047.","DOI":"10.26421\/QIC19.13-14-3"},{"key":"29","doi-asserted-by":"publisher","unstructured":"G. G. Guerreschi and A. Y. Matsuura. ``QAOA for max-cut requires hundreds of qubits for quantum speed-up''. Scientific Reports 9 (2019).","DOI":"10.1038\/s41598-019-43176-9"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Danylo Lykov, Jonathan Wurtz, Cody Poole, Mark Saffman, Tom Noel, and Yuri Alexeev. ``Sampling frequency thresholds for quantum advantage of quantum approximate optimization algorithm'' (2022). arXiv:2206.03579.","DOI":"10.1038\/s41534-023-00718-4"},{"key":"31","unstructured":"Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. ``Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree'' (2021). arXiv:2111.06813."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Boaz Barak and Kunal Marwaha. ``Classical algorithms and quantum limitations for maximum cut on high-girth graphs''. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022); Article No. 14 (2021). arXiv:2106.05900.","DOI":"10.4230\/LIPICS.ITCS.2022.14"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Kunal Marwaha. ``Local classical max-cut algorithm outperforms $p=2$ qaoa on high-girth regular graphs''. Quantum 5, 437 (2021) 5, 437 (2021). arXiv:2101.05513.","DOI":"10.22331\/q-2021-04-20-437"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. ``The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size''. Quantum 6, 759 (2022).","DOI":"10.22331\/q-2022-07-07-759"},{"key":"35","unstructured":"Sami Boulebnane and Ashley Montanaro. ``Predicting parameters for the quantum approximate optimization algorithm for max-cut from the infinite-size limit'' (2021). arXiv:2110.10685."},{"key":"36","unstructured":"Edward Farhi, David Gamarnik, and Sam Gutmann. ``The quantum approximate optimization algorithm needs to see the whole graph: A typical case'' (2020). arXiv:2004.09002."},{"key":"37","unstructured":"Edward Farhi, David Gamarnik, and Sam Gutmann. ``The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples'' (2020). arXiv:2005.08747."},{"key":"38","doi-asserted-by":"publisher","unstructured":"M. M\u00e9zard, T. Mora, and R. Zecchina. ``Clustering of solutions in the random satisfiability problem''. Phys. Rev. Lett. 94, 197205 (2005).","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. ``On the solution-space geometry of random constraint satisfaction problems''. Random Structures & Algorithms 38, 251\u2013268 (2011). arXiv:https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20323.","DOI":"10.1002\/rsa.20323"},{"key":"40","unstructured":"David Gamarnik and Aukosh Jagannath. ``The overlap gap property and approximate message passing algorithms for $p$-spin models'' (2019). arXiv:1911.06943."},{"key":"41","doi-asserted-by":"publisher","unstructured":"David Gamarnik. ``The overlap gap property: a geometric barrier to optimizing over random structures''. Proceedings of the National Academy of Sciences 118 (2021). arXiv:2109.14409.","DOI":"10.1073\/pnas.2108492118"},{"key":"42","unstructured":"Antares Chen, Neng Huang, and Kunal Marwaha. ``Local algorithms and the failure of log-depth quantum advantage on sparse random csps'' (2023). arXiv:2310.01563."},{"key":"43","doi-asserted-by":"publisher","unstructured":"Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. ``Suboptimality of local algorithms for a class of max-cut problems''. Annals of Probability 2019, Vol. 47, No. 3, 1587-1618 47 (2017). arXiv:1707.05386.","DOI":"10.1214\/18-aop1291"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Antonio Auffinger, Wei-Kuo Chen, and Qiang Zeng. ``The sk model is infinite step replica symmetry breaking at zero temperature''. CPAM 2020 (2017). arXiv:1703.06872.","DOI":"10.48550\/ARXIV.1703.06872"},{"key":"45","unstructured":"Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. ``Limitations of local quantum algorithms on random max-k-xor and beyond'' (2021). arXiv:2108.06049."},{"key":"46","doi-asserted-by":"publisher","unstructured":"Amir Dembo, Andrea Montanari, and Subhabrata Sen. ``Extremal cuts of sparse random graphs''. Annals of Probability, 2017, Vol 45, No. 2, 1190- 1217 45 (2015). arXiv:1503.03923.","DOI":"10.1214\/15-aop1084"},{"key":"47","unstructured":"Amin Coja-Oghlan, Philipp Loick, Bal\u00e1zs F. Mezei, and Gregory B. Sorkin. ``The ising antiferromagnet and max cut on random regular graphs'' (2020). arXiv:2009.10483."},{"key":"48","unstructured":"B. D. McKay. ``Independent sets in regular graphs of high girth''. Ars Combinatoria, 23A 179-185. (1987). url: https:\/\/users.cecs.anu.edu.au\/ bdm\/papers\/IndSetsRegGraphs.pdf."},{"key":"49","unstructured":"J\u00f3zsef Balogh, Alexandr Kostochka, and Xujun Liu. ``Cubic graphs with small independence ratio'' (2017). arXiv:1708.03996."},{"key":"50","doi-asserted-by":"crossref","unstructured":"David Gamarnik and Madhu Sudan. ``Limits of local algorithms over sparse random graphs'' (2013). arXiv:1304.1831.","DOI":"10.1145\/2554797.2554831"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. ``Obstacles to state preparation and variational optimization from symmetry protection''. Phys. Rev. Lett. 125, 260505 (2020) 125, 260505 (2019). arXiv:1910.08980.","DOI":"10.1103\/physrevlett.125.260505"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Eunok Bae and Soojoon Lee. ``Recursive qaoa outperforms the original qaoa for the max-cut problem on complete graphs''. Quantum Information Processing 23 (2022). arXiv:2211.15832.","DOI":"10.1007\/s11128-024-04286-0"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Yash J. Patel, Sofiene Jerbi, Thomas B\u00e4ck, and Vedran Dunjko. ``Reinforcement learning assisted recursive qaoa''. EPJ Quantum Technol. 11, 6 (2024) 11 (2022). arXiv:2207.06294.","DOI":"10.1140\/epjqt\/s40507-023-00214-w"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Friedrich Wagner, Jonas N\u00fc\u00dflein, and Frauke Liers. ``Enhancing quantum algorithms for quadratic unconstrained binary optimization via integer programming'' (2023). arXiv:2302.05493.","DOI":"10.1145\/3711935"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Maxime Dupont, Bram Evert, Mark J. Hodson, Bhuvanesh Sundar, Stephen Jeffrey, Yuki Yamaguchi, Dennis Feng, Filip B. Maciejewski, Stuart Hadfield, M. Sohaib Alam, Zhihui Wang, Shon Grabbe, P. Aaron Lott, Eleanor G. Rieffel, Davide Venturelli, and Matthew J. Reagor. ``Quantum-enhanced greedy combinatorial optimization solver''. Science Advances 9, 45 (2023) 9 (2023). arXiv:2303.05509.","DOI":"10.1126\/sciadv.adi0487"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Maxime Dupont and Bhuvanesh Sundar. ``Quantum relax-and-round algorithm for combinatorial optimization'' (2023). arXiv:2307.05821.","DOI":"10.1103\/PhysRevA.109.012429"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Jernej Rudi Fin\u017egar, Aron Kerschbaumer, Martin J. A. Schuetz, Christian B. Mendl, and Helmut G. Katzgraber. ``Quantum-informed recursive optimization algorithms'' (2023). arXiv:2308.13607.","DOI":"10.1103\/PRXQuantum.5.020327"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, and Claudio Chamon. ``Optimizing Variational Quantum Algorithms Using Pontryagin's Minimum Principle''. Physical Review X 7, 021027 (2017).","DOI":"10.1103\/PhysRevX.7.021027"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Lenka Zdeborov\u00e1 and Stefan Boettcher. ``Conjecture on the maximum cut and bisection width in random regular graphs''. J. Stat. Mech. (2010) P02020 2010, P02020 (2009). arXiv:0912.4861.","DOI":"10.1088\/1742-5468\/2010\/02\/p02020"},{"key":"60","unstructured":"Raffaele Marino and Scott Kirkpatrick. ``Large independent sets on random $d$-regular graphs with fixed degree $d$'' (2020). arXiv:2003.12293."},{"key":"61","doi-asserted-by":"publisher","unstructured":"Mustazee Rahman and Balint Virag. ``Local algorithms for independent sets are half-optimal''. Ann. Probab. 45 (2017), no. 3, 1543-1577 45 (2014). arXiv:1402.0485.","DOI":"10.1214\/16-aop1094"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Amin Coja-Oghlan and Charilaos Efthymiou. ``On independent sets in random graphs''. Random Structures and Algorithms 47 (2015) 436 - 486 47, 436\u2013486 (2010). arXiv:1007.1378.","DOI":"10.1002\/rsa.20550"},{"key":"63","unstructured":"Alexander S. Wein. ``Optimal low-degree hardness of maximum independent set'' (2020). arXiv:2010.06563."},{"key":"64","doi-asserted-by":"publisher","unstructured":"A.M Frieze and T \u0141uczak. ``On the independence and chromatic numbers of random regular graphs''. Journal of Combinatorial Theory, Series B 54, 123\u2013132 (1992).","DOI":"10.1016\/0095-8956(92)90070-E"},{"key":"65","unstructured":"Hamed Hatami, L\u00e1szl\u00f3 Lov\u00e1sz, and Bal\u00e1zs Szegedy. ``Limits of local-global convergent graph sequences'' (2012). arXiv:1205.4356."},{"key":"66","unstructured":"Andrea Montanari. ``Optimization of the sherrington-kirkpatrick hamiltonian'' (2018). arXiv:1812.10897."},{"key":"67","doi-asserted-by":"publisher","unstructured":"Mark Xin Hong Goh. ``The overlap gap property limits limit swapping in qaoa'' (2024). arXiv:2404.06087.","DOI":"10.2478\/qic-2025-0018"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Simon Martiel, Thomas Ayral, and Cyril Allouche. ``Benchmarking quantum coprocessors in an application-centric, hardware-agnostic, and scalable way''. IEEE Transactions on Quantum Engineering 2, 1\u201311 (2021).","DOI":"10.1109\/TQE.2021.3090207"},{"key":"69","unstructured":"Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. ``Large cuts with local algorithms on triangle-free graphs'' (2014) arXiv:1402.2543."},{"key":"70","doi-asserted-by":"publisher","unstructured":"Eran Halperin, Dror Livnat, and Uri Zwick. ``Max cut in cubic graphs''. Journal of Algorithms 53, 169\u2013185 (2004).","DOI":"10.1016\/j.jalgor.2004.06.001"},{"key":"71","doi-asserted-by":"publisher","unstructured":"M. M. Hall\u00f3rsson and J. Radhakrishnan. ``Greed is good: Approximating independent sets in sparse and bounded-degree graphs''. Algorithmica 18, 145\u2013163 (1997).","DOI":"10.1007\/bf02523693"},{"key":"72","doi-asserted-by":"publisher","unstructured":"Reuben Tate, Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta. ``Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths''. Quantum 7, 1121 (2023).","DOI":"10.22331\/q-2023-09-26-1121"},{"key":"73","unstructured":"Gian Giacomo Guerreschi and Mikhail Smelyanskiy. ``Practical optimization for hybrid quantum-classical algorithms'' (2017). arXiv:1701.01450."},{"key":"74","doi-asserted-by":"publisher","unstructured":"Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. ``Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices''. Phys. Rev. X 10, 021067 (2020) 10, 021067 (2018). arXiv:1812.01041.","DOI":"10.1103\/physrevx.10.021067"},{"key":"75","doi-asserted-by":"publisher","unstructured":"Lennart Bittel and Martin Kliesch. ``Training variational quantum algorithms is np-hard''. Phys. Rev. Lett. 127, 120502 (2021) 127, 120502 (2021). arXiv:2101.07267.","DOI":"10.1103\/physrevlett.127.120502"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-22-1892\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,22]],"date-time":"2025-10-22T12:43:43Z","timestamp":1761137023000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-22-1892\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,22]]},"references-count":76,"URL":"https:\/\/doi.org\/10.22331\/q-2025-10-22-1892","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,22]]},"article-number":"1892"}}