{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:09:30Z","timestamp":1764688170052,"version":"build-2065373602"},"reference-count":41,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T00:00:00Z","timestamp":1760313600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Land Niedersachsen","award":["Quantum Valley Lower Saxony"],"award-info":[{"award-number":["Quantum Valley Lower Saxony"]}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["ATIQ"],"award-info":[{"award-number":["ATIQ"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"crossref","award":["QuBRA"],"award-info":[{"award-number":["QuBRA"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Despite its popularity, several empirical and theoretical studies suggest that the quantum approximate optimization algorithm (QAOA) has persistent issues in providing a substantial practical advantage. Numerical results for few qubits and shallow circuits are, at best, ambiguous, and the well-studied barren plateau phenomenon draws a rather sobering picture for deeper circuits. However, as more and more sophisticated strategies are proposed to circumvent barren plateaus, it stands to reason which issues are actually fundamental and which merely constitute \u2013 admittedly difficult \u2013 engineering tasks. By shifting the scope from the usually considered parameter landscape to the quantum state space&apos;s geometry we can distinguish between problems that are fundamentally difficult to solve, independently of the parameterization, and those for which there could at least exist a favorable parameterization. Here, we find clear evidence for a &apos;no free lunch&apos;-behavior of QAOA on a general optimization task with no further structure; individual cases have, however, to be analyzed more carefully.\nBased on our analysis, we propose and justify a performance indicator for the deep-circuit QAOA that can be accessed by solely evaluating statistical properties of the classical objective function. We further discuss the various favorable properties a generic QAOA instance has in the asymptotic regime of infinitely many gates, and elaborate on the immanent drawbacks of finite circuits. We provide several numerical examples of a deep-circuit QAOA method based on local search strategies and find that \u2013 in alignment with our performance indicator \u2013 some special function classes, like QUBOs, indeed admit a favorable optimization landscape.<\/jats:p>","DOI":"10.22331\/q-2025-10-13-1882","type":"journal-article","created":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:07:57Z","timestamp":1760346477000},"page":"1882","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":3,"title":["Deep-Circuit QAOA"],"prefix":"10.22331","volume":"9","author":[{"given":"Gereon","family":"Ko\u00dfmann","sequence":"first","affiliation":[{"name":"Institute for Quantum Information, RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lennart","family":"Binkowski","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Leibniz University Hannover"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lauritz","family":"van Luijk","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Leibniz University Hannover"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"Ziegler","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Leibniz University Hannover"},{"name":"Volkswagen AG, Berliner Ring 2, 38440 Wolfsburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ren\u00e9","family":"Schwonnek","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, Leibniz University Hannover"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,10,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles. ``Variational quantum algorithms''. Nature Reviews Physics 3, 625\u2013644 (2021).","DOI":"10.1038\/s42254-021-00348-9"},{"key":"1","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. ``A Quantum Approximate Optimization Algorithm'' (2014). arXiv:1411.4028."},{"key":"2","doi-asserted-by":"publisher","unstructured":"M. P. Harrigan et al. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332\u2013336 (2021).","DOI":"10.1038\/s41567-020-01105-y"},{"key":"3","doi-asserted-by":"publisher","unstructured":"M. Willsch, D. Willsch, F. Jin, H. De Raedt, and K. Michielsen. ``Benchmarking the quantum approximate optimization algorithm''. Quantum Information Processing 19, 197 (2020).","DOI":"10.1007\/s11128-020-02692-8"},{"key":"4","unstructured":"G. E. Crooks. ``Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem'' (2018). arXiv:1811.08419."},{"key":"5","doi-asserted-by":"publisher","unstructured":"D. Lykov, J. Wurtz, C. Poole, M. Saffman, T. Noel, and Y. Alexeev. ``Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm''. npj Quantum Information 9, 73 (2023).","DOI":"10.1038\/s41534-023-00718-4"},{"key":"6","doi-asserted-by":"publisher","unstructured":"S. Bravyi, A. Kliesch, R. Koenig, and E. Tang. ``Obstacles to variational quantum optimization from symmetry protection''. Physical Review Letters 125, 260505 (2020).","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"7","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":"8","doi-asserted-by":"publisher","unstructured":"M. Larocca, P. Czarnik, K. Sharma, G. Muraleedharan, P. J. Coles, and M. Cerezo. ``Diagnosing barren plateaus with tools from quantum optimal control''. Quantum 6, 824 (2022).","DOI":"10.22331\/q-2022-09-29-824"},{"key":"9","doi-asserted-by":"publisher","unstructured":"J. Lee, A. B. Magann, H. A. Rabitz, and C. Arenz. ``Progress toward favorable landscapes in quantum combinatorial optimization''. Physical Review A 104, 032401 (2021).","DOI":"10.1103\/PhysRevA.104.032401"},{"key":"10","doi-asserted-by":"publisher","unstructured":"B. Tan, M.-A. Lemonde, S. Thanasilp, J. Tangpanitanon, and D. G. Angelakis. ``Qubit-efficient encoding schemes for binary optimisation problems''. Quantum 5, 454 (2021).","DOI":"10.22331\/q-2021-05-04-454"},{"key":"11","doi-asserted-by":"crossref","unstructured":"I. D. Leonidas, A. Dukakis, B. Tan, and D. G. Angelakis. ``Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors'' (2023). arXiv:2306.08507.","DOI":"10.1002\/qute.202300309"},{"key":"12","doi-asserted-by":"publisher","unstructured":"S. Endo, S. C. Benjamin, and Y. Li. ``Practical quantum error mitigation for near-future applications''. Physical Review X 8, 031027 (2018).","DOI":"10.1103\/PhysRevX.8.031027"},{"key":"13","doi-asserted-by":"publisher","unstructured":"L. Egan, D. M. Debroy, C. Noel, A. Risinger, D. Zhu, D. Biswas, M. Newman, M. Li, K. R. Brown, M. Cetina, and C. Monroe. ``Fault-tolerant control of an error-corrected qubit''. Nature 598, 281\u2013286 (2021).","DOI":"10.1038\/s41586-021-03928-y"},{"key":"14","doi-asserted-by":"publisher","unstructured":"M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Biamonte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo. ``Barren plateaus in variational quantum computing''. Nature Reviews Physics 7, 174\u2013189 (2025).","DOI":"10.1038\/s42254-025-00813-9"},{"key":"15","doi-asserted-by":"publisher","unstructured":"E. Campos, A. Nasrallah, and J. D. Biamonte. ``Abrupt transitions in variational quantum circuit training''. Physical Review A 103, 032607 (2021).","DOI":"10.1103\/PhysRevA.103.032607"},{"key":"16","doi-asserted-by":"publisher","unstructured":"J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 9, 4812 (2018).","DOI":"10.1038\/s41467-018-07090-4"},{"key":"17","doi-asserted-by":"publisher","unstructured":"A. Arrasmith, M. Cerezo, P. Czarnik, L. Cincio, and P. J. Coles. ``Effect of barren plateaus on gradient-free optimization''. Quantum 5, 558 (2021).","DOI":"10.22331\/q-2021-10-05-558"},{"key":"18","doi-asserted-by":"publisher","unstructured":"S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles. ``Noise-induced barren plateaus in variational quantum algorithms''. Nature Communications 12, 6961 (2021).","DOI":"10.1038\/s41467-021-27045-6"},{"key":"19","doi-asserted-by":"publisher","unstructured":"C. Ortiz Marrero, M. Kieferov\u00e1, and N. Wiebe. ``Entanglement-induced barren plateaus''. PRX Quantum 2, 040316 (2021).","DOI":"10.1103\/PRXQuantum.2.040316"},{"key":"20","doi-asserted-by":"publisher","unstructured":"M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles. ``Cost function dependent barren plateaus in shallow parametrized quantum circuits''. Nature Communications 12, 1791 (2021).","DOI":"10.1038\/s41467-021-21728-w"},{"key":"21","doi-asserted-by":"publisher","unstructured":"N. A. Nemkov, E. O. Kiktenko, and A. K. Fedorov. ``Barren plateaus swamped with traps''. Physical Review A 111, 012441 (2025).","DOI":"10.1103\/PhysRevA.111.012441"},{"key":"22","doi-asserted-by":"publisher","unstructured":"X. Ge, R.-B. Wu, and H. Rabitz. ``The optimization landscape of hybrid quantum\u2013classical algorithms: From quantum control to nisq applications''. Annual Reviews in Control 54, 314\u2013323 (2022).","DOI":"10.1016\/j.arcontrol.2022.06.001"},{"key":"23","unstructured":"J. Allcock, M. Santha, P. Yuan, and S. Zhang. ``On the dynamical lie algebras of quantum approximate optimization algorithms'' (2024). arXiv:2407.12587."},{"key":"24","doi-asserted-by":"publisher","unstructured":"J. M. Lee. ``Introduction to smooth manifolds''. Springer. New York, NY (2003).","DOI":"10.1007\/978-1-4419-9982-5"},{"key":"25","doi-asserted-by":"publisher","unstructured":"S. Lloyd. ``Almost any quantum logic gate is universal''. Physical Review Letters 75, 346\u2013349 (1995).","DOI":"10.1103\/PhysRevLett.75.346"},{"key":"26","doi-asserted-by":"publisher","unstructured":"D. Deutsch, A. Barenco, and A. Ekert. ``Universality in quantum computation''. Proceedings: Mathematical and Physical Sciences 449, 669\u2013677 (1995).","DOI":"10.1098\/rspa.1995.0065"},{"key":"27","doi-asserted-by":"publisher","unstructured":"M. E. S. Morales, J. D. Biamonte, and Z. Zimbor\u00e1s. ``On the universality of the quantum approximate optimization algorithm''. Quantum Information Processing 19, 291 (2020).","DOI":"10.1007\/s11128-020-02748-9"},{"key":"28","doi-asserted-by":"publisher","unstructured":"C. Altafini. ``Controllability of quantum mechanical systems by root space decomposition of $su(N)$''. Journal of Mathematical Physics 43, 2051\u20132062 (2002).","DOI":"10.1063\/1.1467611"},{"key":"29","doi-asserted-by":"publisher","unstructured":"R. Zeier and T. Schulte-Herbr\u00fcggen. ``Symmetry principles in quantum systems theory''. Journal of Mathematical Physics 52, 113510 (2011).","DOI":"10.1063\/1.3657939"},{"key":"30","doi-asserted-by":"publisher","unstructured":"R. Zeier and Z. Zimbor\u00e1s. ``On squares of representations of compact lie algebras''. Journal of Mathematical Physics 56, 081702 (2015).","DOI":"10.1063\/1.4928410"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Z. Zimbor\u00e1s, R. Zeier, T. Schulte-Herbr\u00fcggen, and D. Burgarth. ``Symmetry criteria for quantum simulability of effective interactions''. Physical Review A 92, 042309 (2015).","DOI":"10.1103\/physreva.92.042309"},{"key":"32","doi-asserted-by":"publisher","unstructured":"A. A. Agrachev and Y. L. Sachkov. ``Control theory from the geometric viewpoint''. Springer Science & Business Media. (2004).","DOI":"10.1007\/978-3-662-06404-7"},{"key":"33","doi-asserted-by":"publisher","unstructured":"J. Nocedal and S. J. Wright. ``Numerical optimization''. Springer. New York, NY (2006).","DOI":"10.1007\/978-0-387-40065-5"},{"key":"34","doi-asserted-by":"publisher","unstructured":"S. Russell and P. Norvig. ``Artificial intelligence: A modern approach''. Prentice Hall Press. USA (2009).","DOI":"10.5555\/1671238"},{"key":"35","unstructured":"J. S. Baker and S. K. Radha. ``Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study'' (2022). arXiv:2202.06782."},{"key":"36","doi-asserted-by":"publisher","unstructured":"Y. Crama and P. L. Hammer. ``Boolean functions theory, algorithms, and applications''. Cambridge University Press. (2011).","DOI":"10.1017\/CBO9780511852008"},{"key":"37","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":"38","doi-asserted-by":"publisher","unstructured":"R. Hooke and T. A. Jeeves. ````direct search'' solution of numerical and statistical problems''. Journal of the ACM 8, 212\u2013229 (1961).","DOI":"10.1145\/321062.321069"},{"key":"39","doi-asserted-by":"publisher","unstructured":"R. L. Anderson. ``Recent advances in finding best operating conditions''. Journal of the American Statistical Association 48, 789\u2013798 (1953).","DOI":"10.2307\/2281072"},{"key":"40","doi-asserted-by":"publisher","unstructured":"S. H. Brooks. ``A discussion of random methods for seeking maxima''. Operations Research 6, 244\u2013251 (1958).","DOI":"10.1287\/opre.6.2.244"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-13-1882\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:08:42Z","timestamp":1760346522000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-13-1882\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,13]]},"references-count":41,"URL":"https:\/\/doi.org\/10.22331\/q-2025-10-13-1882","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,13]]},"article-number":"1882"}}