References
- 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_9
- 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=inyEeSEqqtwC
- 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.1088%2F1742-5468%2Fac9cc8
- E. Farhi, J. Goldstone and S. Gutmann (2014). A Quantum Approximate Optimization Algorithm. Available at: https://arxiv.org/abs/1411.4028
- 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-759
- 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/
- 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.09002
- 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.1109%2Ffocs54457.2022. 00039
- 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-999
- 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.14618
- 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.052419
- T. Luczak (1990). “On the equivalence of two basic models of random graph”. Proceedings of Random Graphs, 87, 151–159.
- 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/S0195669880800308
- 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.1792
- 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/009
- 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.20774
- 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-AOS1628
- 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.20323
- 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 205
- 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.1073%2Fpnas.2108492118
- 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.1214%2F18-aop1291
- 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.41
- B. Huang and M. Sellke (2023). Algorithmic Threshold for Multi-Species Spherical Spin Glasses. Available at: https://arxiv.org/abs/2303.12172
- 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.021067
- 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.21886
- 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-AOP1084
- 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.01563
- A. Frieze and M. Karonski (2015). Introduction to Random Graphs. Cambridge University Press.
- 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-AOP1114
- A.E. Alaoui and A. Montanari (2020). Algorithmic Thresholds in Mean Field Spin Glasses. Available at: https://arxiv.org/abs/2009.11481
- 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 9388
- M. Goh (2024). The Overlap Gap Property Limits Limit Swapping. Available at: https://github.com/capselo/The-Overlap-Gap-Property-limits-limit-swapping
- 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-AAP2003
- 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.003
- 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:961773
- 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/4666