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] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, “Parameter concentrations in quantum approximate optimization”, Physical Review A 104 1, L010401 (2021).
[2] E. Campos, D. Rabinovich, V. Akshay, and J. Biamonte, “Training Saturation in Layerwise Quantum Approximate Optimisation”, arXiv:2106.13814.
[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”, arXiv:2106.11672.
The above citations are from SAO/NASA ADS (last updated successfully 2021-09-15 16:50:26). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-09-15 16:50:24: Could not fetch cited-by data for 10.22331/q-2021-09-15-542 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-09-15-542/
