Document Open Access Logo

The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

Authors Joao Basso , Edward Farhi, Kunal Marwaha , Benjamin Villalonga , Leo Zhou

PDF

File

Thumbnail PDF
PDF
LIPIcs.TQC.2022.7.pdf
  • Filesize: 1.45 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Combinatorial optimization
Keywords
  • Quantum algorithm
  • Max-Cut
  • spin glass
  • approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth p. We apply the QAOA to MaxCut on large-girth D-regular graphs. We give an iterative formula to evaluate performance for any D at any depth p. Looking at random D-regular graphs, at optimal parameters and as D goes to infinity, we find that the p = 11 QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these D-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensemble-averaged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model defined on the complete graph. We also generalize our formula to Max-q-XORSAT on large-girth regular hypergraphs. Our iteration is a compact procedure, but its computational complexity grows as O(p² 4^p). This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to p = 20. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as p goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance.

Cite As Get BibTex

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 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.TQC.2022.7

Author Details

Joao Basso
  • Google Quantum AI, Venice, CA, USA
Edward Farhi
  • Google Quantum AI, Venice, CA, USA
  • Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA, USA
Kunal Marwaha
  • Department of Computer Science, University of Chicago, IL, USA
Benjamin Villalonga
  • Google Quantum AI, Venice, CA
Leo Zhou
  • Walter Burke Institute for Theoretical Physics, California Institute of Technology, Pasadena, CA, USA

Funding

  • Marwaha, Kunal: National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1746045. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Acknowledgements

The authors thank Sam Gutmann for being there and Matthew P. Harrigan for a careful read of the manuscript.

References

  1. Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.06813.
  2. Antonio Auffinger, Wei-Kuo Chen, and Qiang Zeng. The SK Model Is Infinite Step Replica Symmetry Breaking at Zero Temperature. Communications on Pure and Applied Mathematics, 73(5):921-943, 2020. URL: https://doi.org/10.1002/cpa.21886.
  3. 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), 215:14:1-14:21, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.14.
  4. 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 preprint, 2021. Full version on arXiv. URL: http://arxiv.org/abs/2110.14206.
  5. Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. Performance of the QAOA on MaxCut over Large-Girth Regular Graphs. Online, 2022. URL: https://github.com/benjaminvillalonga/large-girth-maxcut-qaoa.
  6. 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 preprint, 2022. URL: http://arxiv.org/abs/2204.10306.
  7. Claude Berge. Hypergraphs, Combinatorics of Finite Sets. North-Holland, 1989. URL: http://compalg.inf.elte.hu/~tony/Oktatas/Algoritmusok-hatekonysaga/Berge-hypergraphs.pdf.
  8. Sami Boulebnane and Ashley Montanaro. Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.10685.
  9. Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125:260505, December 2020. URL: https://doi.org/10.1103/PhysRevLett.125.260505.
  10. 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 preprint, 2021. URL: http://arxiv.org/abs/2108.06049.
  11. Leonardo Dagum and Ramesh Menon. OpenMP: an industry standard API for shared-memory programming. Computational Science & Engineering, IEEE, 5(1):46-55, 1998. URL: https://doi.org/10.1109/99.660313.
  12. Amir Dembo, Andrea Montanari, and Subhabrata Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45(2):1190-1217, 2017. URL: https://doi.org/10.1214/15-AOP1084.
  13. Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.09002.
  14. Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.08747.
  15. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv preprint, 2014. URL: http://arxiv.org/abs/1411.4028.
  16. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size. arXiv preprint, 2019. URL: http://arxiv.org/abs/1910.08187.
  17. David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 118(41), 2021. URL: https://doi.org/10.1073/pnas.2108492118.
  18. Gaël Guennebaud, Benoît Jacob, et al. Eigen v3. Online, 2010. URL: https://eigen.tuxfamily.org.
  19. Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17(3):332-336, 2021. URL: https://doi.org/10.1038/s41567-020-01105-y.
  20. Russell Lyons. Factors of iid on trees. Combinatorics, Probability and Computing, 26(2):285-300, 2017. URL: http://arxiv.org/abs/1401.4197.
  21. Kunal Marwaha. Local classical MAX-CUT algorithm outperforms p = 2 QAOA on high-girth regular graphs. Quantum, 5:437, 2021. URL: https://doi.org/10.22331/q-2021-04-20-437.
  22. Kunal Marwaha and Stuart Hadfield. Bounds on approximating Max kXOR with quantum and classical local algorithms. arXiv preprint, 2021. URL: http://arxiv.org/abs/2109.10833.
  23. 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, page 814–827, 2016. URL: https://doi.org/10.1145/2897518.2897548.
  24. Dmitry Panchenko. The Sherrington-Kirkpatrick model. Springer Science & Business Media, 2013. URL: https://doi.org/10.1007/978-1-4614-6289-7.
  25. Giorgio Parisi. Toward a mean field theory for spin glasses. Physics Letters A, 73(3):203-205, 1979. URL: https://doi.org/10.1016/0375-9601(79)90708-4.
  26. Yixuan Qiu and Dirk Toewe. LBFGS++. Online, 2020. URL: https://github.com/yixuan/LBFGSpp.
  27. Manuel J Schmidt. Replica symmetry breaking at low temperatures. PhD thesis, Universität Würzburg, 2008. URL: https://d-nb.info/991972910/34.
  28. Subhabrata Sen. Optimization on sparse random hypergraphs and spin glasses. Random Structures & Algorithms, 53(3):504-536, 2018. URL: https://doi.org/10.1002/rsa.20774.
  29. Jessica K Thompson, Ojas Parekh, and Kunal Marwaha. An explicit vector algorithm for high-girth MaxCut. Symposium on Simplicity in Algorithms (SOSA), pages 238-246, 2022. URL: https://doi.org/10.1137/1.9781611977066.17.
  30. Luca Trevisan, Gregory B Sorkin, Madhu Sudan, and David P Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6):2074-2097, 2000. URL: https://doi.org/10.1137/S0097539797328847.
  31. Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view. Phys. Rev. A, 97(2):022304, 2018. URL: https://doi.org/10.1103/PhysRevA.97.022304.
  32. Jonathan Wurtz and Peter Love. MaxCut quantum approximate optimization algorithm performance guarantees for p > 1. Phys. Rev. A, 103:042612, April 2021. URL: https://doi.org/10.1103/PhysRevA.103.042612.
  33. 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. URL: https://doi.org/10.1103/PhysRevX.10.021067.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact