Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
IQM Quantum Computers, Georg-Brauchle-Ring 23-25, 80992 München, Germany
| Published: | 2025-10-22, volume 9, page 1892 |
| Editor: | Daniel McNulty |
| Eprint: | arXiv:2406.14618v2 |
| Doi: | https://doi.org/10.22331/q-2025-10-22-1892 |
| Citation: | Quantum 9, 1892 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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 $d=100$. 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 $d$, 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.
Featured image: We study the performance of the Quantum Approximate Optimization Algorithm (QAOA) on random $d$-regular graphs for two paradigmatic problems: MaxCut and Maximum Independent Set. Both problems can be unified as Ising models. The light cones corresponding to local observables are with high probability trees.
Popular summary
A clear picture emerges. For MaxCut, the expected approximation ratio of QAOA improves as the graphs get denser. For Maximum Independent Set, the trend reverses: as the degree increases, the expected approximation ratio drops. We argue that this aligns with the “overlap-gap” phenomenon of Maximum Independent set, which tends to block local or low-depth methods (such as shallow QAOA) from reliably reaching near-optimal solutions.
Beyond these asymptotics, we also illustrate a practical shortcut for Maximum Independent Set which was already well known for MaxCut: parameters optimized on trees transfer well to finite-size random graphs. Using those fixed angles—so, no expensive per-instance tuning—we demonstrate that QAOA beats standard classical baselines such as Goemans–Williamson for MaxCut and a minimal greedy heuristic for Maximum Independent Set.
In short, our work analyzes where QAOA is expected to shine and where it struggles on random regular graphs, and it provides a fast, parameter-free way to deploy it that performs competitively in practice on these ensembles.
► BibTeX data
► References
[1] Richard P. Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982).
https://doi.org/10.1007/bf02650179
[2] J. Ignacio Cirac and Peter Zoller. ``Goals and opportunities in quantum simulation''. Nature Physics 8, 264–266 (2012).
https://doi.org/10.1038/nphys2275
[3] I. M. Georgescu, S. Ashhab, and Franco Nori. ``Quantum simulation''. Rev. Mod. Phys. 86, 153–185 (2014).
https://doi.org/10.1103/RevModPhys.86.153
[4] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Phys. Rev. Lett. 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[5] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. ``A rigorous and robust quantum speed-up in supervised machine learning''. Nature Physics 17, 1013–1017 (2021).
https://doi.org/10.1038/s41567-021-01287-z
[6] Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Information-theoretic bounds on quantum advantage in machine learning''. Phys. Rev. Lett. 126, 190505 (2021).
https://doi.org/10.1103/PhysRevLett.126.190505
[7] Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert. ``On the Quantum versus Classical Learnability of Discrete Distributions''. Quantum 5, 417 (2021).
https://doi.org/10.22331/q-2021-03-23-417
[8] Lov K. Grover. ``A Fast quantum mechanical algorithm for database search'' (1996). arXiv:quant-ph/9605043.
arXiv:quant-ph/9605043
[9] Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, 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ña 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.
https://doi.org/10.1038/s42254-024-00770-9
arXiv:2312.02279
[10] John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018) 2, 79 (2018). arXiv:1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv:1801.00862
[11] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028
[12] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem'' (2014). arXiv:1412.6062.
arXiv:1412.6062
[13] Edward Farhi and Aram W Harrow. ``Quantum supremacy through the quantum approximate optimization algorithm'' (2016). arXiv:1602.07674.
arXiv:1602.07674
[14] 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.
https://doi.org/10.3390/a12020034
arXiv:1709.03489
[15] Ehsan Zahedinejad and Arman Zaribafiyan. ``Combinatorial optimization on gate model quantum computers: A survey'' (2017). arXiv:1708.05294.
arXiv:1708.05294
[16] 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).
https://doi.org/10.1103/PhysRevA.97.022304
[17] 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–66 (2023). arXiv:2306.09198.
https://doi.org/10.1016/j.physrep.2024.03.002
arXiv:2306.09198
[18] Eran Makover and Jeffrey McGowan. ``Regular trees in random regular graphs'' (2006).
[19] 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–7:21, (2022) (2021). arXiv:2110.14206.
https://doi.org/10.4230/LIPICS.TQC.2022.7
arXiv:2110.14206
[20] 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.
arXiv:1812.04170
[21] 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).
https://doi.org/10.1088/2058-9565/ab8c2b
[22] 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.
https://doi.org/10.1103/physreva.103.042612
arXiv:2010.11209
[23] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. ``Transferability of optimal qaoa parameters between random graphs'' (2021). arXiv:2106.07531.
arXiv:2106.07531
[24] 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.
arXiv:2307.05420
[25] Gavin E. Crooks. ``Performance of the quantum approximate optimization algorithm on the maximum cut problem'' (2018). arXiv:1811.08419.
arXiv:1811.08419
[26] Jonathan Wurtz and Danylo Lykov. ``Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs''. Phys. Rev. A 104, 052419 (2021).
https://doi.org/10.1103/PhysRevA.104.052419
[27] 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–1145 (1995).
https://doi.org/10.1145/227683.227684
[28] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. ``Optimal inapproximability results for max‐cut and other 2‐variable csps?''. SIAM Journal on Computing 37, 319–357 (2007). arXiv:https://doi.org/10.1137/S0097539705447372.
https://doi.org/10.1137/S0097539705447372
arXiv:https://doi.org/10.1137/S0097539705447372
[29] M. B. Hastings. ``Classical and quantum bounded depth approximation algorithms'' (2019). arXiv:1905.07047.
arXiv:1905.07047
[30] G. G. Guerreschi and A. Y. Matsuura. ``QAOA for max-cut requires hundreds of qubits for quantum speed-up''. Scientific Reports 9 (2019).
https://doi.org/10.1038/s41598-019-43176-9
[31] 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.
https://doi.org/10.1038/s41534-023-00718-4
arXiv:2206.03579
[32] 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.
arXiv:2111.06813
[33] 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.
https://doi.org/10.4230/LIPICS.ITCS.2022.14
arXiv:2106.05900
[34] 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.
https://doi.org/10.22331/q-2021-04-20-437
arXiv:2101.05513
[35] 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).
https://doi.org/10.22331/q-2022-07-07-759
[36] 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.
arXiv:2110.10685
[37] 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.
arXiv:2004.09002
[38] 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.
arXiv:2005.08747
[39] M. Mézard, T. Mora, and R. Zecchina. ``Clustering of solutions in the random satisfiability problem''. Phys. Rev. Lett. 94, 197205 (2005).
https://doi.org/10.1103/PhysRevLett.94.197205
[40] Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi. ``On the solution-space geometry of random constraint satisfaction problems''. Random Structures & Algorithms 38, 251–268 (2011). arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20323.
https://doi.org/10.1002/rsa.20323
arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20323
[41] David Gamarnik and Aukosh Jagannath. ``The overlap gap property and approximate message passing algorithms for $p$-spin models'' (2019). arXiv:1911.06943.
arXiv:1911.06943
[42] 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.
https://doi.org/10.1073/pnas.2108492118
arXiv:2109.14409
[43] 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.
arXiv:2310.01563
[44] 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.
https://doi.org/10.1214/18-aop1291
arXiv:1707.05386
[45] 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.
https://doi.org/10.48550/ARXIV.1703.06872
arXiv:1703.06872
[46] 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.
arXiv:2108.06049
[47] 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.
https://doi.org/10.1214/15-aop1084
arXiv:1503.03923
[48] Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, and Gregory B. Sorkin. ``The ising antiferromagnet and max cut on random regular graphs'' (2020). arXiv:2009.10483.
arXiv:2009.10483
[49] 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.
https://users.cecs.anu.edu.au/~bdm/papers/IndSetsRegGraphs.pdf
[50] József Balogh, Alexandr Kostochka, and Xujun Liu. ``Cubic graphs with small independence ratio'' (2017). arXiv:1708.03996.
arXiv:1708.03996
[51] David Gamarnik and Madhu Sudan. ``Limits of local algorithms over sparse random graphs'' (2013). arXiv:1304.1831.
arXiv:1304.1831
[52] 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.
https://doi.org/10.1103/physrevlett.125.260505
arXiv:1910.08980
[53] 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.
https://doi.org/10.1007/s11128-024-04286-0
arXiv:2211.15832
[54] Yash J. Patel, Sofiene Jerbi, Thomas Bäck, and Vedran Dunjko. ``Reinforcement learning assisted recursive qaoa''. EPJ Quantum Technol. 11, 6 (2024) 11 (2022). arXiv:2207.06294.
https://doi.org/10.1140/epjqt/s40507-023-00214-w
arXiv:2207.06294
[55] Friedrich Wagner, Jonas Nüßlein, and Frauke Liers. ``Enhancing quantum algorithms for quadratic unconstrained binary optimization via integer programming'' (2023). arXiv:2302.05493.
https://doi.org/10.1145/3711935
arXiv:2302.05493
[56] 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.
https://doi.org/10.1126/sciadv.adi0487
arXiv:2303.05509
[57] Maxime Dupont and Bhuvanesh Sundar. ``Quantum relax-and-round algorithm for combinatorial optimization'' (2023). arXiv:2307.05821.
https://doi.org/10.1103/PhysRevA.109.012429
arXiv:2307.05821
[58] Jernej Rudi Finžgar, Aron Kerschbaumer, Martin J. A. Schuetz, Christian B. Mendl, and Helmut G. Katzgraber. ``Quantum-informed recursive optimization algorithms'' (2023). arXiv:2308.13607.
https://doi.org/10.1103/PRXQuantum.5.020327
arXiv:2308.13607
[59] 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).
https://doi.org/10.1103/PhysRevX.7.021027
[60] Lenka Zdeborová 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.
https://doi.org/10.1088/1742-5468/2010/02/p02020
arXiv:0912.4861
[61] Raffaele Marino and Scott Kirkpatrick. ``Large independent sets on random $d$-regular graphs with fixed degree $d$'' (2020). arXiv:2003.12293.
arXiv:2003.12293
[62] 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.
https://doi.org/10.1214/16-aop1094
arXiv:1402.0485
[63] Amin Coja-Oghlan and Charilaos Efthymiou. ``On independent sets in random graphs''. Random Structures and Algorithms 47 (2015) 436 - 486 47, 436–486 (2010). arXiv:1007.1378.
https://doi.org/10.1002/rsa.20550
arXiv:1007.1378
[64] Alexander S. Wein. ``Optimal low-degree hardness of maximum independent set'' (2020). arXiv:2010.06563.
arXiv:2010.06563
[65] A.M Frieze and T Łuczak. ``On the independence and chromatic numbers of random regular graphs''. Journal of Combinatorial Theory, Series B 54, 123–132 (1992).
https://doi.org/10.1016/0095-8956(92)90070-E
[66] Hamed Hatami, László Lovász, and Balázs Szegedy. ``Limits of local-global convergent graph sequences'' (2012). arXiv:1205.4356.
arXiv:1205.4356
[67] Andrea Montanari. ``Optimization of the sherrington-kirkpatrick hamiltonian'' (2018). arXiv:1812.10897.
arXiv:1812.10897
[68] Mark Xin Hong Goh. ``The overlap gap property limits limit swapping in qaoa'' (2024). arXiv:2404.06087.
https://doi.org/10.2478/qic-2025-0018
arXiv:2404.06087
[69] 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–11 (2021).
https://doi.org/10.1109/TQE.2021.3090207
[70] Juho Hirvonen, Joel Rybicki, Stefan Schmid, and Jukka Suomela. ``Large cuts with local algorithms on triangle-free graphs'' (2014) arXiv:1402.2543.
arXiv:1402.2543
[71] Eran Halperin, Dror Livnat, and Uri Zwick. ``Max cut in cubic graphs''. Journal of Algorithms 53, 169–185 (2004).
https://doi.org/10.1016/j.jalgor.2004.06.001
[72] M. M. Hallórsson and J. Radhakrishnan. ``Greed is good: Approximating independent sets in sparse and bounded-degree graphs''. Algorithmica 18, 145–163 (1997).
https://doi.org/10.1007/bf02523693
[73] 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).
https://doi.org/10.22331/q-2023-09-26-1121
[74] Gian Giacomo Guerreschi and Mikhail Smelyanskiy. ``Practical optimization for hybrid quantum-classical algorithms'' (2017). arXiv:1701.01450.
arXiv:1701.01450
[75] 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.
https://doi.org/10.1103/physrevx.10.021067
arXiv:1812.01041
[76] Lennart Bittel and Martin Kliesch. ``Training variational quantum algorithms is np-hard''. Phys. Rev. Lett. 127, 120502 (2021) 127, 120502 (2021). arXiv:2101.07267.
https://doi.org/10.1103/physrevlett.127.120502
arXiv:2101.07267
Cited by
[1] Hasan Kanaker, Essam Alhroob, Hammoudeh Alamri, Maher Abuhamdeh, and Samar Al-Saqqa, "Enhanced Puzzle Optimization Algorithmfor Complex Engineering Design Problems", Eng 7 5, 217 (2026).
[2] Florian Geissler, Eric Stopfer, Christian Ufrecht, Nico Meyer, Daniel D. Scherer, Friedrich Wagner, Johannes M. Oberreuter, Zao Chen, Alessandro Farace, Daria Gutina, Ulrich Schwenk, Kimberly Lange, Vanessa Junk, Thomas Husslein, Marvin Erdmann, Florian Kiwit, Benjamin Decker, Greshma Shaji, Etienne Granet, Henrik Dreyer, Theodora-Augustina Drǎgan, and Jeanette Miriam Lorenz, Communications in Computer and Information Science 2743, 207 (2026) ISBN:978-3-032-13851-4.
[3] Mark Goh, "The Overlap Gap Property Limits Limit Swapping in the QAOA", Quantum Information & Computation 25 4, 329 (2025).
[4] Edward Farhi, Sam Gutmann, Daniel Ranard, and Benjamin Villalonga, "Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA", arXiv:2503.12789, (2025).
[5] Florian Geissler, Eric Stopfer, Christian Ufrecht, Nico Meyer, Daniel D. Scherer, Friedrich Wagner, Johannes M. Oberreuter, Zao Chen, Alessandro Farace, Daria Gutina, Ulrich Schwenk, Kimberly Lange, Vanessa Junk, Thomas Husslein, Marvin Erdmann, Florian Kiwit, Benjamin Decker, Greshma Shaji, Etienne Granet, Henrik Dreyer, Theodora-Augustina Dragan, and Jeanette Miriam Lorenz, "BenchQC -- Scalable and modular benchmarking of industrial quantum computing applications", arXiv:2504.11204, (2025).
[6] Isak Lyngfelt and Laura García-Álvarez, "Symmetry-informed transferability of optimal parameters in the quantum approximate optimization algorithm", Physical Review A 111 2, 022418 (2025).
[7] Chuixiong Wu, Jianan Wang, and Fen Zuo, "From Maximum Cut to Maximum Independent Set", arXiv:2408.06758, (2024).
[8] Tom Krüger and Wolfgang Mauerer, "Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation", Quantum 9, 1903 (2025).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 12:39:46) and SAO/NASA ADS (last updated successfully 2026-08-13 12:39:47). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.