The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

Edward Farhi1,2, Jeffrey Goldstone2, Sam Gutmann, and Leo Zhou1,3

1Google Inc., Venice, CA 90291, USA
2Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
3Department of Physics, Harvard University, Cambridge, MA 02138, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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$. 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$ 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 $(1-\epsilon)$ 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 $2p$ QAOA parameters, in the infinite size limit that can be evaluated on a computer with $O(16^p)$ complexity. We evaluate the formula up to $p=12$, and find that the QAOA at $p=11$ outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as $n\to\infty$, 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.

This work studies the performance of a general-purpose quantum algorithm for combinatorial optimization, called the QAOA, applied to the famous Sherrington-Kirkpatrick (SK) model of spin glass. This is the problem of energy minimization of all-to-all randomly coupled spins. The authors produce a formula for calculating the expected value of the energy achieved by the QAOA in the limit of infinite system size, as a function of the algorithm parameters. They also prove that typical measurements of random instances of the problem concentrates at this value. These results allow for comparisons to the state-of-the-art classical algorithms. In particular, the authors find that the QAOA with 11 layers outperforms the standard semidefinite programming algorithm on this problem. It remains an open question how the performance scaling of the QAOA compares to the currently known best classical algorithm by Montanari.

► BibTeX data

► References

[1] A. Montanari. ``Optimization of the Sherrington-Kirkpatrick Hamiltonian''. In Proceedings of the 60th Annual Symposium on Foundations of Computer Science (FOCS '19). Pages 1417–1433. (2019).
https:/​/​doi.org/​10.1109/​FOCS.2019.00087

[2] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm'' (2014). arXiv:1411.4028.
arXiv:1411.4028

[3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. ``A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem'' (2015). arXiv:1412.6062.
arXiv:1412.6062

[4] Cedric Yen-Yu Lin and Yechao Zhu. ``Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree'' (2016). arXiv:1601.01744.
arXiv:1601.01744

[5] 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

[6] G. Parisi. ``Infinite number of order parameters for spin-glasses''. Phys. Rev. Lett. 43, 1754–1756 (1979).
https:/​/​doi.org/​10.1103/​PhysRevLett.43.1754

[7] Dmitry Panchenko. ``The Sherrington-Kirkpatrick model''. Springer. New York (2013).
https:/​/​doi.org/​10.1007/​978-1-4614-6289-7

[8] A. Crisanti and T. Rizzo. ``Analysis of the ${\infty}$-replica symmetry breaking solution of the Sherrington-Kirkpatrick model''. Phys. Rev. E 65, 046137 (2002).
https:/​/​doi.org/​10.1103/​PhysRevE.65.046137

[9] Manuel J. Schmidt. ``Replica Symmetry Breaking at Low Temperatures''. PhD thesis. Julius-Maximilians-Universität Würzburg. (2008).

[10] 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).
https:/​/​doi.org/​10.1103/​PhysRevX.10.021067

[11] Gavin E. Crooks. ``Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem'' (2018). arXiv:1811.08419.
arXiv:1811.08419

[12] G. Parisi. Private communication.

[13] Michael Aizenman, Joel Lebowitz, and D. Ruelle. ``Some rigorous results on the Sherrington-Kirkpatrick spin glass model''. Commun. Math. Phys. 112, 3–20 (1987).
https:/​/​doi.org/​10.1007/​BF01217677

[14] 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–827. (2016). arXiv:1504.05910.
https:/​/​doi.org/​10.1145/​2897518.2897548
arXiv:1504.05910

[15] 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–78:29. Dagstuhl, Germany (2020). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. arXiv:1902.07324.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2020.78
arXiv:1902.07324

[16] 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.
https:/​/​doi.org/​10.1038/​s41467-018-07090-4
arXiv:1803.11173

[17] 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.
arXiv:2110.14206

[18] 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–1618 (2019). arXiv:1707.05386.
https:/​/​doi.org/​10.1214/​18-AOP1291
arXiv:1707.05386

[19] David Gamarnik and Aukosh Jagannath. ``The overlap gap property and approximate message passing algorithms for $p$-spin models''. Annals of Probability 49, 180–205 (2021). arXiv:1911.06943.
https:/​/​doi.org/​10.1214/​20-AOP1448
arXiv:1911.06943

[20] Ahmed El Alaoui and Andrea Montanari. ``Algorithmic Thresholds in Mean Field Spin Glasses'' (2020). arXiv:2009.11481.
arXiv:2009.11481

Cited by

[1] Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay, and Jacob Biamonte, "Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation", Mathematics 10 15, 2601 (2022).

[2] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[3] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Collins Ben Chiaro, William Courtney, Sean Demura, Andrew Dunsworth, Daniel Eppens, Austin Fowler, Brooks Foxen, Craig Gidney, Marissa Giustina, Rob Graff, Steve Habegger, Alan Ho, Sabrina Hong, Trent Huang, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Cody Jones, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Seon Kim, Paul V. Klimov, Alexander N. Korotkov, Fedor Kostritsa, David Landhuis, Pavel Laptev, Mike Lindmark, Martin Leib, Orion Martin, John M. Martinis, Jarrod R. McClean, Matt McEwen, Anthony Megrant, Xiao Mi, Masoud Mohseni, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Charles Neill, Florian Neukart, Murphy Yuezhen Niu, Thomas E. O'Brien, Bryan O'Gorman, Eric Ostby, Andre Petukhov, Harald Putterman, Chris Quintana, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Andrea Skolik, Vadim Smelyanskiy, Doug Strain, Michael Streif, Marco Szalay, Amit Vainsencher, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Leo Zhou, Hartmut Neven, Dave Bacon, Erik Lucero, Edward Farhi, and Ryan Babbush, "Quantum approximate optimization of non-planar graph problems on a planar superconducting processor", Nature Physics 17 3, 332 (2021).

[4] Filip B. Maciejewski, Flavio Baccari, Zoltán Zimborás, and Michał Oszmaniec, "Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm", arXiv:2101.02331.

[5] Edward Farhi, David Gamarnik, and Sam Gutmann, "The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case", arXiv:2004.09002.

[6] Thais de Lima Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", arXiv:2110.13180.

[7] Clemens Dlaska, Kilian Ender, Glen Bigan Mbeng, Andreas Kruckenhauser, Wolfgang Lechner, and Rick van Bijnen, "Quantum Optimization via Four-Body Rydberg Gates", Physical Review Letters 128 12, 120503 (2022).

[8] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França, "Limitations of variational quantum algorithms: a quantum optimal transport approach", arXiv:2204.03455.

[9] Antonio Anna Mele, Glen Bigan Mbeng, Giuseppe Ernesto Santoro, Mario Collura, and Pietro Torta, "Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz", arXiv:2206.01982.

[10] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, "Parameter concentrations in quantum approximate optimization", Physical Review A 104 1, L010401 (2021).

[11] Jason Larkin, Matías Jonsson, Daniel Justice, and Gian Giacomo Guerreschi, "Evaluation of QAOA based on the approximation ratio of individual samples", arXiv:2006.04831.

[12] Chenfeng Cao, Zheng An, Shi-Yao Hou, D. L. Zhou, and Bei Zeng, "Quantum imaginary time evolution steered by reinforcement learning", Communications Physics 5 1, 57 (2022).

[13] 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", arXiv:2110.14206.

[14] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo, Alexandre Blais, Christopher Eichler, and Andreas Wallraff, "Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets", PRX Quantum 1 2, 020304 (2020).

[15] Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, and Florian Speelman, "Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach", arXiv:2106.11672.

[16] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, "Low-Depth Mechanisms for Quantum Optimization", PRX Quantum 2 3, 030312 (2021).

[17] Hajo Leschke, Chokri Manai, Rainer Ruder, and Simone Warzel, "Existence of Replica-Symmetry Breaking in Quantum Glasses", Physical Review Letters 127 20, 207204 (2021).

[18] Pontus Vikstâl, Mattias Grönkvist, Marika Svensson, Martin Andersson, Göran Johansson, and Giulia Ferrini, "Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem", Physical Review Applied 14 3, 034009 (2020).

[19] Matteo M. Wauters, Emanuele Panizon, Glen B. Mbeng, and Giuseppe E. Santoro, "Reinforcement-learning-assisted quantum optimization", arXiv:2004.12323, Physical Review Research 2 3, 033446 (2020).

[20] Luca Lumia, Pietro Torta, Glen B. Mbeng, Giuseppe E. Santoro, Elisa Ercolessi, Michele Burrello, and Matteo M. Wauters, "Two-Dimensional Z<SUB>2</SUB> Lattice Gauge Theory on a Near-Term Quantum Simulator: Variational Quantum Optimization, Confinement, and Topological Order", PRX Quantum 3 2, 020320 (2022).

[21] Teague Tomesh, Pranav Gokhale, Victory Omole, Gokul Subramanian Ravi, Kaitlin N. Smith, Joshua Viszlai, Xin-Chuan Wu, Nikos Hardavellas, Margaret R. Martonosi, and Frederic T. Chong, "SupermarQ: A Scalable Quantum Benchmark Suite", arXiv:2202.11045.

[22] Akel Hashim, Rich Rines, Victory Omole, Ravi K. Naik, John Mark Kreikebaum, David I. Santiago, Frederic T. Chong, Irfan Siddiqi, and Pranav Gokhale, "Optimized SWAP networks with equivalent circuit averaging for QAOA", Physical Review Research 4 3, 033028 (2022).

[23] Nishant Jain, Brian Coyle, Elham Kashefi, and Niraj Kumar, "Graph neural network initialisation of quantum approximate optimisation", arXiv:2111.03016.

[24] P. Chandarana, N. N. Hegade, K. Paul, F. Albarrán-Arriagada, E. Solano, A. del Campo, and Xi Chen, "Digitized-counterdiabatic quantum approximate optimization algorithm", Physical Review Research 4 1, 013141 (2022).

[25] Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor, "Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze", arXiv:2112.07611.

[26] Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi, "Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond", arXiv:2108.06049.

[27] Dennis Willsch, Madita Willsch, Fengping Jin, Kristel Michielsen, and Hans De Raedt, "GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm", Computer Physics Communications 278, 108411 (2022).

[28] Bingzhi Zhang, Akira Sone, and Quntao Zhuang, "Quantum Computational Phase Transition in Combinatorial Problems", arXiv:2109.13346.

[29] Jahan Claes and Wim van Dam, "Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size", arXiv:2102.12043.

[30] Wei-Feng Zhuang, Ya-Nan Pu, Hong-Ze Xu, Xudan Chai, Yanwu Gu, Yunheng Ma, Shahid Qamar, Chen Qian, Peng Qian, Xiao Xiao, Meng-Jun Hu, and Dong E. Liu, "Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits", arXiv:2112.11151.

[31] Stuart Hadfield, Tad Hogg, and Eleanor G. Rieffel, "Analytical Framework for Quantum Alternating Operator Ansätze", arXiv:2105.06996.

[32] David Joseph, Antonio J. Martinez, Cong Ling, and Florian Mintert, "Quantum mean-value approximator for hard integer-value problems", Physical Review A 105 5, 052419 (2022).

[33] Laszlo Gyongyosi, "Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers", Scientific Reports 10, 4543 (2020).

[34] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, "Training Saturation in Layerwise Quantum Approximate Optimisation", arXiv:2106.13814, Physical Review A 104 3, L030401 (2021).

[35] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, Xiao-Ming Zhang, and J. Biamonte, "On Circuit Depth Scaling For Quantum Approximate Optimization", arXiv:2205.01698.

[36] Benjamin Tan, Marc-Antoine Lemonde, Supanut Thanasilp, Jirawat Tangpanitanon, and Dimitris G. Angelakis, "Qubit-efficient encoding schemes for binary optimisation problems", arXiv:2007.01774.

[37] J. -H. Bae, Paul M. Alsing, Doyeol Ahn, and Warner A. Miller, "Quantum circuit optimization using quantum Karnaugh map", Scientific Reports 10, 15651 (2020).

[38] Laszlo Gyongyosi and Sandor Imre, "Circuit Depth Reduction for Gate-Model Quantum Computers", Scientific Reports 10, 11229 (2020).

[39] Yuval R. Sanders, Dominic W. Berry, Pedro C. S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", arXiv:2007.07391.

[40] Ioannis Kolotouros and Petros Wallden, "Evolving objective function for improved variational quantum optimization", Physical Review Research 4 2, 023225 (2022).

[41] Paul M. Schindler, Tommaso Guaita, Tao Shi, Eugene Demler, and J. Ignacio Cirac, "A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model", arXiv:2204.02923.

[42] Ruslan Shaydulin, Phillip C. Lotshaw, Jeffrey Larson, James Ostrowski, and Travis S. Humble, "Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut", arXiv:2201.11785.

[43] Prasanna Date, Davis Arthur, and Lauren Pusey-Nazzaro, "QUBO formulations for training machine learning models", Scientific Reports 11, 10029 (2021).

[44] Laszlo Gyongyosi, "Objective function estimation for solving optimization problems in gate-model quantum computers", Scientific Reports 10, 14220 (2020).

[45] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou, "Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models", arXiv:2204.10306.

[46] Gabriel Matos, Sonika Johri, and Zlatko Papić, "Quantifying the efficiency of state preparation via quantum variational eigensolvers", arXiv:2007.14338.

[47] Teppei Suzuki and Michio Katouda, "Predicting toxicity by quantum machine learning", Journal of Physics Communications 4 12, 125012 (2020).

[48] Sami Boulebnane, "Improving the Quantum Approximate Optimization Algorithm with postselection", arXiv:2011.05425.

[49] Kyle Mills, Pooya Ronagh, and Isaac Tamblyn, "Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning", arXiv:2003.00011.

[50] Gregory Quiroz, Paraj Titum, Phillip Lotshaw, Pavel Lougovski, Kevin Schultz, Eugene Dumitrescu, and Itay Hen, "Quantifying the Impact of Precision Errors on Quantum Approximate Optimization Algorithms", arXiv:2109.04482.

[51] Xuchen You and Xiaodi Wu, "Exponentially Many Local Minima in Quantum Neural Networks", arXiv:2110.02479.

[52] Laszlo Gyongyosi, "Dynamics of entangled networks of the quantum Internet", Scientific Reports 10, 12909 (2020).

[53] Laszlo Gyongyosi, "Unsupervised Quantum Gate Control for Gate-Model Quantum Computers", Scientific Reports 10, 10701 (2020).

[54] Michelle Chalupnik, Hans Melo, Yuri Alexeev, and Alexey Galda, "Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer", arXiv:2205.01192.

[55] Sami Boulebnane and Ashley Montanaro, "Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit", arXiv:2110.10685.

[56] Laszlo Gyongyosi and Sandor Imre, "Routing space exploration for scalable routing in the quantum Internet", Scientific Reports 10, 11874 (2020).

[57] G. Pederiva, A. Bazavov, B. Henke, L. Hostetler, D. Lee, H. W. Lin, and A. Shindler, "Quantum State Preparation for the Schwinger Model", The 38th International Symposium on Lattice Field Theory 47 (2022).

[58] Laszlo Gyongyosi and Sandor Imre, "Scalable distributed gate-model quantum computers", Scientific Reports 11, 5172 (2021).

[59] Laszlo Gyongyosi, "Decoherence dynamics estimation for superconducting gate-model quantum computers", Quantum Information Processing 19 10, 369 (2020).

[60] Sinan Bugu, Fatih Ozaydin, and Tetsuo Kodera, "Surpassing the classical limit in magic square game with distant quantum dots coupled to optical cavities", Scientific Reports 10, 22202 (2020).

[61] Daniil Rabinovich, Soumik Adhikary, Ernesto Campos, Vishwanathan Akshay, Evgeny Anikin, Richik Sengupta, Olga Lakhmanskaya, Kiril Lakhmanskiy, and Jacob Biamonte, "Ion native variational ansatz for quantum approximate optimization", arXiv:2206.11908.

[62] Hari Krovi, "Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent", arXiv:2206.05642.

[63] Aida Ahmadzadegan, Petar Simidzija, Ming Li, and Achim Kempf, "Neural networks can learn to utilize correlated auxiliary noise", Scientific Reports 11, 21624 (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2022-08-13 16:16:53) and SAO/NASA ADS (last updated successfully 2022-08-13 16:16:54). The list may be incomplete as not all publishers provide suitable and complete citation data.