Quantum Information & Computation
Volume 25, Issue 4
RESEARCH ARTICLE Open access

The Overlap Gap Property Limits Limit Swapping in the QAOA

Mark Goh

Author affiliations
  1. Institute for Frontier Materials on Earth and in Space, German Aerospace Center, Linder Höhe, Cologne, Germany; Institute for Theoretical Physics, University of Cologne, Zülpicher Str . Cologne, Germany

pp. 329-343 · 10.2478/qic-2025-0018

Read PDF View on Reference Global
On this page

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös-Renyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even q ≥ 4, Max- q -XORSAT is bounded away from optimality when optimized using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth p ≤ ϵ log n, providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max- q -XORSAT problems. We also provide some numerical evidence that the limitation should be extended to odd q by showing that the OGP exists for the Max-3-XORSAT on random regular graphs.
Open accessCC BY-NC-ND 4.0

Keywords

  • QAO
  • overlap gap property
  • combinatorial optimization
  • spin glass

Suggested citation

Mark Goh (2025). The Overlap Gap Property Limits Limit Swapping in the QAOA. Quantum Information & Computation, 25(4), 329-343. https://doi.org/10.2478/qic-2025-0018

Download BibTeX

References (36)

  1. R.M. Karp (1972). Reducibility among Combinatorial Problems. Boston, MA: Springer US, pp. 85–103. Available at: https://doi.org/10.1007/978-1-4684-2001-2_9DOI: 10.1007/978-1-4684-2001-2_9Google Scholar
  2. J. Steele (1997). Probability Theory and Combinatorial Optimization, ser. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics. Available at: https://books.google.de/books?id=inyEeSEqqtwCGoogle Scholar
  3. D. Gamarnik, C. Moore and L. Zdeborová (November 2022). “Disordered systems insights on computational hardness,” Journal of Statistical Mechanics: Theory and Experiment, 2022: 11, 114015. Available at: https://doi.org/10.10882F1742-54682Fac9cc8DOI: 10.1088/1742-5468/ac9cc8Google Scholar
  4. E. Farhi, J. Goldstone and S. Gutmann (2014). A Quantum Approximate Optimization Algorithm. Available at: https://arxiv.org/abs/1411.4028Google Scholar
  5. E. Farhi, J. Goldstone, S. Gutmann and L. Zhou (July 2022). “The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size”. Quantum, 6, 759. Available at: https://doi.org/10.22331/q-2022-07-07-759DOI: 10.22331/q-2022-07-07-759Google Scholar
  6. J. Basso, E. Farhi, K. Marwaha, B. Villalonga and L. Zhou (2022). “The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the Sherrington-Kirkpatrick model.” Schloss Dagstuhl -Leibniz-Zentrum für Informatik. Available at: https://drops.dagstuhl.de/opus/volltexte/2022/165 14/Google Scholar
  7. E. Farhi, D. Gamarnik and S. Gutmann (2020). “The quantum approximate optimization algorithm needs to see the whole graph: A typical case”, 4. Available at: https://arxiv.org/abs/2004.09002Google Scholar
  8. J. Basso, D. Gamarnik, S. Mei and L. Zhou (October 2022). “Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models,” in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. [Online]. Available at: https://doi.org/10.11092Ffocs54457.2022. 00039DOI: 10.1109/FOCS54457.2022.00039Google Scholar
  9. A. Anshu and T. Metger (May 2023). “Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations”. Quantum, 7, 999. Available at: https://doi.org/10.223 31/q-2023-05-11-999DOI: 10.22331/q-2023-05-11-999Google Scholar
  10. E. Wybo and M. Leib (2024). Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm. Available at: https://arxiv.org/abs/2406.14618DOI: 10.22331/q-2025-10-22-1892Google Scholar
  11. J. Wurtz and D. Lykov (November 2021). “Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs”. Physical Review A, 104, 052419. Available at: https://link.aps.org/doi/10.1 103/PhysRevA.104.052419DOI: 10.1103/PhysRevA.104.052419Google Scholar
  12. T. Luczak (1990). “On the equivalence of two basic models of random graph”. Proceedings of Random Graphs, 87, 151–159.Google Scholar
  13. B. Bollobás (1980). “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”. European Journal of Combinatorics, 1: 4, 311–316. Available at: https://www.sciencedirect.com/science/article/pii/S0195669880800308DOI: 10.1016/S0195-6698(80)80030-8Google Scholar
  14. D. Sherrington and S. Kirkpatrick (December 1975). “Solvable model of a spin-glass”. Physical Reviews Letters, 35, 1792–1796. Available at: https://link.aps.org/doi/10.1103/PhysRevLett.35.1792DOI: 10.1103/PhysRevLett.35.1792Google Scholar
  15. G. Parisi (1980). “A sequence of approximated solutions to the S-K model for spin glasses”. Journal of Physics A: Mathematical and General, 13: 4, 115. Available at: https://dx.doi.org/10.1088/0305-4470/13/4/009DOI: 10.1088/0305-4470/13/4/009Google Scholar
  16. S. Sen (2018). “Optimization on sparse random hypergraphs and spin glasses”. Random Structures & Algorithms, 53: 3, 504–536. Available at: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20774DOI: 10.1002/rsa.20774Google Scholar
  17. D. Gamarnik and Q. Li (2018). “Finding a large submatrix of a Gaussian random matrix”. The Annals of Statistics, 46: 6A, 2511–2561. Available at: https://doi.org/10.1214/17-AOS1628DOI: 10.1214/17-AOS1628Google Scholar
  18. D. Achlioptas, A. Coja-Oghlan and F. Ricci-Tersenghi (2011). “On the solution-space geometry of random constraint satisfaction problems”. Random Structures & Algorithms, 38: 3, 251–268. Available at: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20323DOI: 10.1002/rsa.20323Google Scholar
  19. M. Mézard, T Mora, and R. Zecchina (May 2005). “Clustering of solutions in the random satisfiability problem”. Physical Review Letters, 94: 19. Available at: http://dx.doi.org/10.1103/PhysRevLett.94.197 205DOI: 10.1103/PhysRevLett.94.197205Google Scholar
  20. D. Gamarnik (October 2021). “The overlap gap property: A topological barrier to optimizing over random structures”. Proceedings of the National Academy of Sciences, 118: 41. Available at: https://doi.org/10.10732Fpnas.2108492118DOI: 10.1073/pnas.2108492118Google Scholar
  21. W.-K. Chen, D. Gamarnik, D. Panchenko and M. Rahman (May 2019). “Suboptimality of local algorithms For a class of max-cut problems”. The Annals of Probability, 47: 3. Available at: https://doi.org/10.12142F18-aop1291DOI: 10.1214/18-AOP1291Google Scholar
  22. C.-N. Chou, P.J. Love, J.S. Sandhu and J. Shi (2022). “Limitations of local quantum algorithms on random MAX-k-XOR and beyond,” in M. Bojanczyk, E. Merelli, and D. P. Woodruff (eds), 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 229. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 41:1–41:20. Available at: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.41Google Scholar
  23. B. Huang and M. Sellke (2023). Algorithmic Threshold for Multi-Species Spherical Spin Glasses. Available at: https://arxiv.org/abs/2303.12172Google Scholar
  24. L. Zhou, S.-T. Wang, S. Choi, H. Pichler and M.D. Lukin (June 2020). “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices”. Physical Review X, 10: 2. [Online]. Available at: http://dx.doi.org/10.1103/PhysRevX.10.021067DOI: 10.1103/PhysRevX.10.021067Google Scholar
  25. A. Auffinger, W.-K. Chen, and Q. Zeng (2020). “The sk model is infinite step replica symmetry breaking at zero temperature”. Communications on Pure and Applied Mathematics, 73:5, 921–943. Available at: https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.21886DOI: 10.1002/cpa.21886Google Scholar
  26. A. Dembo, A. Montanari and S. Sen (March 2017), “Extremal cuts of sparse random graphs”. The Annals of Probability, 45: 2. Available at: http://dx.doi.org/10.1214/15-AOP1084DOI: 10.1214/15-AOP1084Google Scholar
  27. A. Chen, N. Huang and K. Marwaha (2023). “Local algorithms and the failure of log-depth quantum advantage on sparse random csps”. Available at: https://arxiv.org/abs/2310.01563Google Scholar
  28. A. Frieze and M. Karonski (2015). Introduction to Random Graphs. Cambridge University Press.DOI: 10.1017/CBO9781316339831Google Scholar
  29. D. Gamarnik and M. Sudan (2017). “Limits of local algorithms over sparse random graphs”. The Annals of Probability, 45: 4, 2353–2376. Available at: https://doi.org/10.1214/16-AOP1114DOI: 10.1214/16-AOP1114Google Scholar
  30. A.E. Alaoui and A. Montanari (2020). Algorithmic Thresholds in Mean Field Spin Glasses. Available at: https://arxiv.org/abs/2009.11481Google Scholar
  31. T. Müller, A. Singh, F.K. Wilhelm, and T. Bode (2024). Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems. Available at: https://arxiv.org/abs/2411.1 9388Google Scholar
  32. M. Goh (2024). The Overlap Gap Property Limits Limit Swapping. Available at: https://github.com/capselo/The-Overlap-Gap-Property-limits-limit-swappingDOI: 10.2478/qic-2025-0018Google Scholar
  33. D. Gamarnik and I. Zadik (2024). “The landscape of the planted clique problem: Dense subgraphs and the overlap gap property”. The Annals of Applied Probability, 34: 4, 3375–3434. Available at: https://doi.org/10.1214/23-AAP2003DOI: 10.1214/23-AAP2003Google Scholar
  34. A. Dudek, A. Frieze, A. Rucinski and M. Šileikis (January 2017). “Embedding the erdős-rényi hypergraph into the random regular hypergraph and hamiltonicity”. Journal of Combinatorial Theory, Series B, 122, 719–740. Available at: http://dx.doi.org/10.1016/j.jctb.2016.09.003DOI: 10.1016/j.jctb.2016.09.003Google Scholar
  35. D. Ellis and N. Linial (2013). “On regular hypergraphs of high girth”. Electronic Journal of Combinatorics, 21, 1. Available at: https://api.semanticscholar.org/CorpusID:961773DOI: 10.37236/3851Google Scholar
  36. D.J. Poole (2015). “On the strength of connectedness of a random hypergraph,” Electronic Journal of Combinatorics, 22: 1, 1. Available at: https://doi.org/10.37236/4666DOI: 10.37236/4666Google Scholar