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

E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, “The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size,” Quantum , vol. 6, p. 759, 2022. arXiv:1910.08187v4

Original

1910

Earlier work this paper cites.

S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, “Obstacles to variational quantum optimization from symmetry protection,” Phys. Rev. Lett. , vol. 125, p. 260505, Dec 2020. arXiv:1910.08980

Original

1910

Earlier work this paper cites.

G. Parisi, “Toward a mean field theory for spin glasses,” Physics Letters A , vol. 73, no. 3, pp. 203–205, 1979. https://doi.org/10.1016/0375-9601(79)90708-4

1979

Earlier work this paper cites.

C. Berge, Hypergraphs, Combinatorics of Finite Sets . North-Holland, 1989. http://compalg.inf.elte.hu/~tony/Oktatas/Algoritmusok-hatekonysaga/Berge-hypergraphs.pdf

1989

Earlier work this paper cites.

L. Dagum and R. Menon, “OpenMP: an industry standard API for shared-memory programming,” Computational Science & Engineering, IEEE , vol. 5, no. 1, pp. 46–55, 1998. https://doi.org/10.1109/99.660313

1998

Earlier work this paper cites.

L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson, “Gadgets, approximation, and linear programming,” SIAM Journal on Computing , vol. 29, no. 6, pp. 2074–2097, 2000. https://doi.org/10.1137/S0097539797328847

2000

Earlier work this paper cites.

M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo et al. , “Quantum approximate optimization of non-planar graph problems on a planar superconducting processor,” Nature Physics , vol. 17, no. 3, pp. 332–336, 2021. arXiv:2004.04197

Original

2004

Earlier work this paper cites.

——, “The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case,” arXiv preprint , 2020. arXiv:2004.09002

Original

2004

Earlier work this paper cites.

E. Farhi, D. Gamarnik, and S. Gutmann, “The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples,” arXiv preprint , 2020. arXiv:2005.08747

Original

2005

Earlier work this paper cites.

M. J. Schmidt, “Replica symmetry breaking at low temperatures,” Ph.D. dissertation, Universität Würzburg, 2008. https://d-nb.info/991972910/34

2008

Earlier work this paper cites.

J. Wurtz and P. Love, “MaxCut quantum approximate optimization algorithm performance guarantees for p > 1 p>1 ,” Phys. Rev. A , vol. 103, p. 042612, 2021. arXiv:2010.11209

Original

2010

Earlier work this paper cites.

G. Guennebaud, B. Jacob et al. , “Eigen v3,” Online, 2010. https://eigen.tuxfamily.org

2010

Cited alongside, same era.

D. Panchenko, The Sherrington-Kirkpatrick model . Springer Science & Business Media, 2013. https://doi.org/10.1007/978-1-4614-6289-7

2013

Cited alongside, same era.

E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv preprint , 2014. arXiv:1411.4028

Original

2014

Cited alongside, same era.

A. Montanari and S. Sen, “Semidefinite programs on sparse random graphs and their application to community detection,” in Proceedings of the 48th Annual ACM Symposium on Theory of Computing , ser. STOC ’16, 2016, pp. 814–827. arXiv:1504.05910

Original

2016

Cited alongside, same era.

R. Lyons, “Factors of iid on trees,” Combinatorics, Probability and Computing , vol. 26, no. 2, pp. 285–300, 2017. arXiv:1401.4197

K. Marwaha, “Local classical MAX-CUT algorithm outperforms p = 2 p=2 QAOA on high-girth regular graphs,” Quantum , vol. 5, p. 437, 2021. arXiv:2101.05513

Original

2021

Closest in time.

A. E. Alaoui, A. Montanari, and M. Sellke, “Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree,” arXiv preprint , 2021. arXiv:2111.06813

Original

2021

Closest in time.

D. Gamarnik, “The overlap gap property: A topological barrier to optimizing over random structures,” Proceedings of the National Academy of Sciences , vol. 118, no. 41, 2021. arXiv:2109.14409

Original

2021

Closest in time.

S. Boulebnane and A. Montanaro, “Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit,” arXiv preprint , 2021. arXiv:2110.10685

Original

2021

Closest in time.