Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size

Jahan Claes1,2 and Wim van Dam1,3,4

1QC Ware Corporation, Palo Alto, CA USA
2Department of Physics and Institute for Condensed Matter Theory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
3Department of Computer Science, University of California, Santa Barbara, CA USA
4Department of Physics, University of California, Santa Barbara, CA USA

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

Abstract

This paper studies the application of the Quantum Approximate Optimization Algorithm (QAOA) to spin-glass models with random multi-body couplings in the limit of a large number of spins. We show that for such mixed-spin models the performance of depth $1$ QAOA is independent of the specific instance in the limit of infinite sized systems and we give an explicit formula for the expected performance. We also give explicit expressions for the higher moments of the expected energy, thereby proving that the expected performance of QAOA concentrates.

► BibTeX data

► References

[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL https:/​/​arxiv.org/​abs/​1411.4028.
arXiv:1411.4028

[2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187, 2019. URL https:/​/​arxiv.org/​abs/​1910.08187.
arXiv:1910.08187

[3] Andrea Montanari. Optimization of the Sherrington–Kirkpatrick hamiltonian. SIAM Journal on Computing, 0 (0): FOCS19–1, 2021. 10.1137/​20M132016X.
https:/​/​doi.org/​10.1137/​20M132016X

[4] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Optimization of mean-field spin glasses. arXiv preprint arXiv:2001.00904, 2020. URL https:/​/​arxiv.org/​abs/​2001.00904.
arXiv:2001.00904

[5] Ahmed El Alaoui and Andrea Montanari. Algorithmic thresholds in mean field spin glasses. arXiv preprint arXiv:2009.11481, 2020. URL https:/​/​arxiv.org/​abs/​2009.11481.
arXiv:2009.11481

[6] Zhang Jiang, Eleanor G Rieffel, and Zhihui Wang. Near-optimal quantum circuit for Grover's unstructured search using a transverse field. Physical Review A, 95 (6): 062317, 2017. 10.1103/​PhysRevA.95.062317.
https:/​/​doi.org/​10.1103/​PhysRevA.95.062317

[7] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approximate optimization algorithm for maxcut: A fermionic view. Physical Review A, 97 (2): 022304, 2018. 10.1103/​PhysRevA.97.022304.
https:/​/​doi.org/​10.1103/​PhysRevA.97.022304

[8] Asier Ozaeta, Wim van Dam, and Peter L. McMahon. Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems. arXiv preprint arXiv:2012.03421, 2020. URL https:/​/​arxiv.org/​abs/​2012.03421.
arXiv:2012.03421

[9] Gavin E Crooks. Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv preprint arXiv:1811.08419, 2018. URL https:/​/​arxiv.org/​abs/​1811.08419.
arXiv:1811.08419

[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. Physical Review X, 10 (2): 021067, 2020. 10.1103/​PhysRevX.10.021067.
https:/​/​doi.org/​10.1103/​PhysRevX.10.021067

[11] Fernando GSL 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. arXiv preprint arXiv:1812.04170, 2018. URL https:/​/​arxiv.org/​abs/​1812.04170.
arXiv:1812.04170

[12] David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Physical Review Letters, 35 (26): 1792, 1975. 10.1103/​PhysRevLett.35.1792.
https:/​/​doi.org/​10.1103/​PhysRevLett.35.1792

[13] Giorgio Parisi. A sequence of approximated solutions to the SK model for spin glasses. Journal of Physics A: Mathematical and General, 13 (4): L115, 1980. 10.1088/​0305-4470/​13/​4/​009.
https:/​/​doi.org/​10.1088/​0305-4470/​13/​4/​009

[14] Michel Talagrand. The Parisi formula. Annals of mathematics, pages 221–263, 2006. 10.4007/​annals.2006.163.221.
https:/​/​doi.org/​10.4007/​annals.2006.163.221

[15] Dmitry Panchenko. The Sherrington-Kirkpatrick model: an overview. Journal of Statistical Physics, 149 (2): 362–383, 2012. 10.1007/​s10955-012-0586-7.
https:/​/​doi.org/​10.1007/​s10955-012-0586-7

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

[17] Antonio Auffinger, Wei-Kuo Chen, et al. Parisi formula for the ground state energy in the mixed $ p $-spin model. Annals of Probability, 45 (6B): 4617–4631, 2017. 10.1214/​16-AOP1173.
https:/​/​doi.org/​10.1214/​16-AOP1173

[18] Dmitry Panchenko et al. The Parisi formula for mixed $p$-spin models. Annals of Probability, 42 (3): 946–958, 2014. 10.1214/​12-AOP800.
https:/​/​doi.org/​10.1214/​12-AOP800

[19] Leo Zhou, Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. The quantum approximate optimization algorithm and the Sherrington-Kirkpatrick model at infinite size. Talk presented at QIP, 2021. URL https:/​/​youtu.be/​UP-Zuke7IUg.
https:/​/​youtu.be/​UP-Zuke7IUg

Cited by

[1] Joao Basso, David Gamarnik, Song Mei, and Leo Zhou, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 335 (2022) ISBN:978-1-6654-5519-0.

[2] David Headley and Frank K. Wilhelm, "Problem-size-independent angles for a Grover-driven quantum approximate optimization algorithm", Physical Review A 107 1, 012412 (2023).

[3] 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", Quantum 6, 687 (2022).

[4] Pietro Torta, Glen B. Mbeng, Carlo Baldassi, Riccardo Zecchina, and Giuseppe E. Santoro, "Quantum approximate optimization algorithm applied to the binary perceptron", Physical Review B 107 9, 094202 (2023).

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

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

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

[8] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, "Training saturation in layerwise quantum approximate optimization", Physical Review A 104 3, L030401 (2021).

[9] Daniil Rabinovich, Ernesto Campos, Soumik Adhikary, Ekaterina Pankovets, Dmitry Vinichenko, and Jacob Biamonte, "On the gate-error robustness of variational quantum algorithms", arXiv:2301.00048, (2022).

[10] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, "Training Saturation in Layerwise Quantum Approximate Optimisation", arXiv:2106.13814, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 08:19:28) and SAO/NASA ADS (last updated successfully 2024-03-28 08:19:30). The list may be incomplete as not all publishers provide suitable and complete citation data.