{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T02:19:44Z","timestamp":1781662784119,"version":"3.54.5"},"reference-count":20,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ARO","award":["W911NF-17-1-0433"],"award-info":[{"award-number":["W911NF-17-1-0433"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p<\/mml:mi><\/mml:math>. While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n<\/mml:mi><\/mml:math> spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within (<\/mml:mo>1<\/mml:mn>&#x2212;<\/mml:mo>&#x03F5;<\/mml:mi>)<\/mml:mo><\/mml:math> times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2<\/mml:mn>p<\/mml:mi><\/mml:math> QAOA parameters, in the infinite size limit that can be evaluated on a computer with O<\/mml:mi>(<\/mml:mo>16<\/mml:mn>p<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math> complexity. We evaluate the formula up to p<\/mml:mi>=<\/mml:mo>12<\/mml:mn><\/mml:math>, and find that the QAOA at p<\/mml:mi>=<\/mml:mo>11<\/mml:mn><\/mml:math> outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n<\/mml:mi>&#x2192;<\/mml:mo>&#x221E;<\/mml:mi><\/mml:math>, measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.<\/jats:p>","DOI":"10.22331\/q-2022-07-07-759","type":"journal-article","created":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T12:36:15Z","timestamp":1657197375000},"page":"759","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":171,"title":["The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size"],"prefix":"10.22331","volume":"6","author":[{"given":"Edward","family":"Farhi","sequence":"first","affiliation":[{"name":"Google Inc., Venice, CA 90291, USA"},{"name":"Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey","family":"Goldstone","sequence":"additional","affiliation":[{"name":"Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sam","family":"Gutmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leo","family":"Zhou","sequence":"additional","affiliation":[{"name":"Google Inc., Venice, CA 90291, USA"},{"name":"Department of Physics, Harvard University, Cambridge, MA 02138, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,7,7]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. Montanari. ``Optimization of the Sherrington-Kirkpatrick Hamiltonian''. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS '19). Pages 1417\u20131433. (2019).","DOI":"10.1109\/FOCS.2019.00087"},{"key":"1","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm'' (2014). arXiv:1411.4028."},{"key":"2","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem'' (2015). arXiv:1412.6062."},{"key":"3","unstructured":"Cedric Yen-Yu Lin and Yechao Zhu. ``Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree'' (2016). arXiv:1601.01744."},{"key":"4","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":"5","doi-asserted-by":"publisher","unstructured":"G. Parisi. ``Infinite number of order parameters for spin-glasses''. Phys. Rev. Lett. 43, 1754\u20131756 (1979).","DOI":"10.1103\/PhysRevLett.43.1754"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Dmitry Panchenko. ``The Sherrington-Kirkpatrick model''. Springer. New York (2013).","DOI":"10.1007\/978-1-4614-6289-7"},{"key":"7","doi-asserted-by":"publisher","unstructured":"A. Crisanti and T. Rizzo. ``Analysis of the ${\\infty}$-replica symmetry breaking solution of the Sherrington-Kirkpatrick model''. Phys. Rev. E 65, 046137 (2002).","DOI":"10.1103\/PhysRevE.65.046137"},{"key":"8","unstructured":"Manuel J. Schmidt. ``Replica Symmetry Breaking at Low Temperatures''. PhD thesis. Julius-Maximilians-Universit\u00e4t W\u00fcrzburg. (2008)."},{"key":"9","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).","DOI":"10.1103\/PhysRevX.10.021067"},{"key":"10","unstructured":"Gavin E. Crooks. ``Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem'' (2018). arXiv:1811.08419."},{"key":"11","unstructured":"G. Parisi. Private communication."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Michael Aizenman, Joel Lebowitz, and D. Ruelle. ``Some rigorous results on the Sherrington-Kirkpatrick spin glass model''. Commun. Math. Phys. 112, 3\u201320 (1987).","DOI":"10.1007\/BF01217677"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Andrea Montanari and Subhabrata Sen. ``Semidefinite programs on sparse random graphs and their application to community detection''. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC '16). Pages 814\u2013827. (2016). arXiv:1504.05910.","DOI":"10.1145\/2897518.2897548"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. ``Computational Hardness of Certifying Bounds on Constrained PCA Problems''. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Volume 151, pages 78:1\u201378:29. Dagstuhl, Germany (2020). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. arXiv:1902.07324.","DOI":"10.4230\/LIPIcs.ITCS.2020.78"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 9, 4812 (2018). arXiv:1803.11173.","DOI":"10.1038\/s41467-018-07090-4"},{"key":"16","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'' (2022). arXiv:2110.14206."},{"key":"17","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 47, 1587\u20131618 (2019). arXiv:1707.05386.","DOI":"10.1214\/18-AOP1291"},{"key":"18","doi-asserted-by":"publisher","unstructured":"David Gamarnik and Aukosh Jagannath. ``The overlap gap property and approximate message passing algorithms for $p$-spin models''. Annals of Probability 49, 180\u2013205 (2021). arXiv:1911.06943.","DOI":"10.1214\/20-AOP1448"},{"key":"19","unstructured":"Ahmed El Alaoui and Andrea Montanari. ``Algorithmic Thresholds in Mean Field Spin Glasses'' (2020). arXiv:2009.11481."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-07-07-759\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T12:36:22Z","timestamp":1657197382000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-07-07-759\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,7]]},"references-count":20,"URL":"https:\/\/doi.org\/10.22331\/q-2022-07-07-759","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,7]]},"article-number":"759"}}